백준 21606번 : 아침 산책 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 주어진 조건을 만족하는 서로 다른 산책 경로의 개수를 찾는 문제이다. 문제 조건을 요약하면 다음과 같다. 시작점과 끝점은 모두 실내 장소 산책 경로 위에 시작점과 끝점을 제외하고 실내 장소가 있으면 안됨 실내 → 실외 → 실내로 이동하는 경우와 실내 → 실내로 이동하는 경우 두 가지를 고려해야 한다. 실내 → 실외 → 실내 먼저 하나의 실외 노드에 4개의 실내 노드가 인접해 있다고 가정해보자. 산책 경로의 수는 ..

백준 5639 이진 검색 트리 이진 검색 트리의 전위 순회 결과를 토대로 후위 순회 결과를 출력하는 프로그램을 만드는 문제이다. 이진 검색 트리의 조건은 다음과 같으며, 이를 이용해 문제를 풀 수 있다. 이진 검색 트리(binary search tree)는 모든 노드가 다음 조건을 만족해야 한다. 왼쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 한다. 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 한다. 처음에는 전위 순회 결과를 토대로 트리를 복구한 다음, 후위 순회 결과를 출력하는 방식으로 풀이를 시도 했으나, 시간 초과와 메모리 초과가 발생하였다. 전위 순회 결과의 첫번째 요소는 이진 검색 트리의 루트 노드이다. 이를 시작점으로 하여 각 노드들과의 대소 관계 비교를 통해 트리의..

백준 5094번 Moo 게임 문제에서 정의된 Moo 수열의 N번째 글자를 구하는 문제다. 해당 문제를 접했을 때, 아래처럼 Moo 수열 자체를 구하다보니 메모리 초과가 발생하였다. def moo(k) : if k == 0 : return "moo" tmp = "m" + "o" * (k + 2) return moo(k-1) + tmp + moo(k-1) 문제 조건에서 Moo 수열의 길이는 '무한대'라고 했기 때문에 수열 자체를 출력할 수 없다고 생각했다. 또한, \(1 \leq N \leq 10^{9}\) 인 것을 고려했을 때 다른 방법으로 풀이하도록 유도하는 것 같았다. Moo 수열은 아래와 같이 나타낼 수 있다. moo(n) = moo(n-1) + "m" + "o" * (n+2) + moo(n-1) 이..