문제 www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 풀이 간단하게 딕셔너리 형태로 트리를 구현했다. 예제 입력으로 생성된 트리는 다음의 형태를 보인다. tree = {'A' : ['B', 'C'], 'B' : ['D', '.'], 'C' : ['E', 'F'], 'E' : ['.', '.'], 'F' : ['.', 'G'], 'D' : ['.', '.'], 'G' : ['.', '.']} 순회는 모두 재귀 형식으로 구현했으며, print문의 위치에 주..
문제 www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n의 범위가 크므로(최대 100,000) O(n)시간 안에 문제를 해결하는 것이 중요하다. 따라서 동적계획법을 적용하여 풀 수 있다. 최적해는 아래의 두 가지 상황을 고려하여 구할 수 있다. 1) 계속해서 더해간다: 이전 연속합에서 현재 정수를 더한다. 2) 초기화한다: 현재 정수부터 연속합을 다시 구한다. 점화식은 dp[n] = max(dp[n-1]+dp[n], dp[n])이 된다. 그림으로 표현하면 다음과 ..
문제 www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 정점을 탐색하는 건 어렵지 않지만, 경로를 기록하는 것이 까다롭다. 이차원 리스트에 경로를 저장하면 수월하게 해결할 수 있다. DFS/BFS 탐색 시 탐색을 시작하는 정점(start)을 매개변수로 넘겨주고 방문하는 정점마다 경로에 추가하면 된다. 즉, 현재 정점(cur)을 방문하면 path[start][cur] = 1이 된다. 이때 탐색하는 과정에서 사이클이 존재하는지 여부를 확인해줘야 한다. 코드 import sys sys.setrecurs..
문제 www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 풀이 먹이(단어)를 하나의 노드로 간략하게 트라이(Trie)를 구현한다. 처음엔 스택을 이용해서 탐색하려 했으나 백트래킹하는 과정에서 재귀를 사용하는 것이 더 나을 것 같아서 변경했다. 이해를 돕기 위해 아래에 트라이 구현 코드까지 올렸다. 코드 문제풀이 import sys class Trie: def __init__(self): self.root = {} # children def add(..
