사부작사부작해요

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는 패턴에 공통 문자열이 많을수록 효과적인..

도서 '이것이 취업을 위한 코딩테스트다 with 파이썬'의 Chapter 9에 수록된 문제는 플로이드 워셜로 풀이된다. 물론 노드와 간선의 개수가 각각 100개 이하이므로 플로이드 워셜로 풀어도 문제 없다. 하지만 BFS로 풀 수도 있으며, 더 빠르게 동작한다. 노드의 개수 V, 간선의 개수 E인 그래프가 주어진다고 가정하자. 플로이드 워셜로 풀면 시간 복잡도가 O(V^3)이지만 BFS로 풀면 O(E) = O(V^2)이다. 어떻게 BFS로 풀이될 수 있지? 간선의 가중치가 모두 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까지 존재하며, 가능한 모든 경우는 리프..