사부작사부작해요

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

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