http://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net # 조건 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개..

http://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net # 조건 문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하여라 부분 문자열은 S에서 연속된 일부분을 말하며, 1보다 크거나 같아야 된다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다. # 접근 방법 S를 1에서 길이수만큼 부분 집합을 구해준다. 이 때, 서로 다른 것들을 구해야되므로 SET에 담아준 ..

http://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net # 조건 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중 집합 S에 포함되어 있는 것이 총 몇 개인지 구하여라. # 접근 방법 딕셔너리를 이용하여 집합 S에 포함되는 문자열들을 기록해준다. 이후 M개의 줄을 돌며 딕셔너리에 있다면 +1을 해준다. import sys sys.stdin = open('input.txt') input ..

http://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net # 조건 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐진다. 폭발은 아래와 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우, 모든 폭발 문자열이 폭발하게 되고 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 잇다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 모든 ..

http://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net # 조건 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리 오더를 구하여라 # 접근 방법 중위 순회와 후위 순회가 주어진다. 중위의 경우 -> LVR 후위의 경우 -> LRV 왼쪽 자식 노드부터 시작한다. 후위 순회의 가장 마지막 수 -> 루트 노드 루트 노드를 중위 순회에서 살펴보면 left tree와 right tree를..

http://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net # 조건 각 직원은 자유롭게 출퇴근을 할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 ..

http://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net # 조건 이진 트리를 입력받아 전위 순회, 중위 순회, 후위 순회 한 결과를 출력하여라 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 입력 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ ..

http://www.acmicpc.net/problem/1918 # 조건 수식은 일반적으로 중위 표기법, 전위 표기법, 후위 표기법으로 나타낼 수 있다. 이 문제에서는 후위 표기법으로 나타내는데 연산자가 피연산자 뒤에 위치하는 방법 예를 들어 a+b c를 후위 표기식으로 바꾸면 abc +가 된다. 바꾸는 방법 주어진 중위 표기식을 연산자의 우선 순위에 따라 괄호로 묶어준다. 그런 다음 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다. # 접근 방법 문제에 나와있는 방식을 스택을 이용해서 구현해주면 된다. 입력받은 표기식에서 토큰을 읽는다. 토큰이 피연산자이면 토큰 출력 토큰이 괄호를 포함한 연산자일 때, 토큰이 스택의 TOP에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 PUSH 하고, 그렇지 ..

http://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net # 조건 이진 검색 트리는 아래와 같은 조건을 만족하는 이진 트리 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽) 후위 순회 (왼쪽-오른쪽-루트) 아래 이진 검색 트리의 전위 순회 결과 50 30 24 5 28 45 98..