사부작사부작해요

GitHub - yuna1212/coteto: 알고리즘 문제 풀이 파일 관리 - 파일 생성 및 시간 기록 알고리즘 문제 풀이 파일 관리 - 파일 생성 및 시간 기록. Contribute to yuna1212/coteto development by creating an account on GitHub. github.com 코테 알고리즘 문제를 풀 때, 나만의 기록용 주석을 파일의 맨 앞에 작성한다. 기록용 주석은 시작 시간, 소요 시간, 풀이 방법을 정해둔 양식으로 작성한다. 근데 이걸 매번 작성하기 귀찮아서, 양식에 맞게 파일을 생성·수정해주는 bash 쉘 스크립트를 작성하고 환경 변수에 등록해줬다. 지금까지 작성한 기록을 보니, 소요 시간(풀이 시간)은 대개 10분을 단위로 계산했었다. 시작 시간과 소..

주어진 문자열에서, 패턴(=폭발 문자열)과 일치하는 부분 문자열을 모두 삭제하는 문제이다. 문자열에 일치하는 패턴이 없을 때 까지 계속 반복한다. KMP로 풀어서 제출하면 시간초과로 통과하지 못한다. 패턴에 반복/공통되는 문자열이 없기 때문이다. 다른분들 풀이를 확인했는데, 스택을 많이 사용하더라. 폭발 후 문자열을 연속해서 폭발시킬 수 있어 논리가 단순해 스택을 많이 사용하는 것 같다. 왜 KMP가 안되는지, 왜 스택을 사용했는지, 특히 str 타입이 아니라 list 타입을 써서 해결한 이유는 뭔지 알아보자. KMP로 풀었을 때 문제를 다시 읽다보니, 조건에서 KMP로 풀지 말라고 알려주고 있었다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. KMP는 패턴에 공통 문자열이 많을수록 효과적인..

백준 11725번 트리의 부모 찾기, 1167 트리의 지름 문제를 풀었다. 정점과 간선 정보가 주어지고 이를 트리 구조로 나타내고 싶었다. 트리를 어떻게 만들지 고민했다. 트리 구조는 클래스 선언해서 필드에 연결된 자식을 저장하는 형식으로 종종 구현했다. 이번에는 인접리스트 형식으로 구현했다. 왜냐하면 각 노드에 인덱스로 바로 접근할 수 있는 구조를 사용하고 싶었기 때문이다. N개의 노드를 가진 트리의 노드 번호는 1부터 N까지 있다고 가정했을 때, 노드 번호를 통해 자식이 누구인지 확인할 수 있게 구현했다. 노드와 간선 정보는 변수 connection에 인접리스트로 주어진다. def make_tree(connection): children_of = [[] for _ in range(len(connect..

도서 '이것이 취업을 위한 코딩테스트다 with 파이썬'의 Chapter 9에 수록된 문제는 플로이드 워셜로 풀이된다. 물론 노드와 간선의 개수가 각각 100개 이하이므로 플로이드 워셜로 풀어도 문제 없다. 하지만 BFS로 풀 수도 있으며, 더 빠르게 동작한다. 노드의 개수 V, 간선의 개수 E인 그래프가 주어진다고 가정하자. 플로이드 워셜로 풀면 시간 복잡도가 O(V^3)이지만 BFS로 풀면 O(E) = O(V^2)이다. 어떻게 BFS로 풀이될 수 있지? 간선의 가중치가 모두 1이기 때문이다. 즉, 노드간 이동 횟수가 이동 거리이다. 특정 노드에서 다른 노드로 이동할 때 마다 큐에 넣으면, 자연히 이동 거리가 짧은 노드들이 큐의 앞에 위치하게 된다. 목적 노드를 꺼낼 때 까지 과정을 반복하면 된다. 간..

O(E)는 O(V^2)때문에 무시할 수 있다. 그래서 O(V^2)로 나타낸다. 목차 다익스트라 최단 경로 알고리즘 예시 시간 복잡도 1. 다익스트라 최단 경로 알고리즘 특정 노드에서 다른 각각의 노드까지 최단 경로를 구하는 알고리즘이다. 단, 간선은 음이 아닌 가중치를 가져야 한다. 단순하게, 최단 경로의 거리를 구하는 방법을 살펴보자. 시작 노드에서 각 노드들까지의 최단 거리를 저장하는 테이블에서, 최소의 최단 거리를 가진 노드를 방문했다고 표시한다. 방문하는 노드와 연결된 다른 노드까지의 거리와, 그 노드를 거치지 않은 거리를 비교하여 최솟값으로 최단 거리 테이블을 업데이트한다. 이 과정을 모든 노드에 대해 최단 경로 거리를 구할 때 까지 반복한다. 이 때 방문한 노드는 더이상 방문하지 않고 거리를 ..

백준 12865 평범한 배낭 - 파이썬 배낭문제 계속 메모리초과가 난다. 어떤부분이 잘못됐는지 모르겠어서 알아보려고 한다. 1. 문제 정의 배낭에 넣는 물품은 무게 w와 가치 v를 갖는다. n개의 물품에서 총 v의 합이 최대가 되도록 sabujak.tistory.com 메모리 초과로 통과하지 못했다. 메모리를 얼마나 많이 사용하게 되는지, 다들 적용하는 다이나믹 프로그래밍 알고리즘의 공간복잡도를 비교해보자. 1. 내 코드의 공간복잡도 가장 메모리를 많이 차지하는 부분은 각 노드를 구하는 부분이다. 코드에서 볼 수 있듯, k번째 물품을 포함/불포함 하는 경우를 모두 살펴보기 위해 previous와 now 모두 저장할 공간이 필요하다. k는 0이상, n 미만이므로 내 코드의 공간복잡도는 다음과 같다. 2. ..

배낭문제 계속 메모리초과가 난다. 어떤부분이 잘못됐는지 모르겠어서 알아보려고 한다. 1. 문제 정의 배낭에 넣는 물품은 무게 w와 가치 v를 갖는다. n개의 물품에서 총 v의 합이 최대가 되도록 선택하여 배낭을 채운다. 배낭은 weight_possible만큼의 무게를 견딜 수 있다. 물품을 중복해서 선택할 수 없다. 2. 아이디어 Full binary tree로 표현할 수 있다. 각 노드는 배낭에 담긴 물품의 총 w와 v를 저장하며 왼쪽 자식은 각 물품을 포함하는 경우, 오른쪽 자식은 포함하지 않는 경우로 나타낼 수 있다. 물품의 무게를 배열 w에, 가치를 배열 v에 저장할 때 레벨 k와 k+1의 노드는 다음 그림과 같이 표현한다. 트리의 레벨은 0부터 시작하여 n까지 존재하며, 가능한 모든 경우는 리프..