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 ..

14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net # 조건 바이러스의 확산을 막기 위해서 연구소에 벽을 세운다. 연구소는 크기가 N x M 연구소는 빈 칸, 벽으로 이루어져 있다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 수는 3개이며, 꼭 3개여야만 한다. 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하시오 # 접근 방법 브루트포스와 bfs..

http://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net # 조건 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2 * X의 위치로 이동하게 된다...

http://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net # 조건 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을..

http://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net # 조건 크기가 N * N 인 행렬 A가 주어진다. 이 때, A의 B제곱을 구하는 프로그램을 작성 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다 입력 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이..

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

http://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net # 조건 N줄에 0이상 9이하의 숫자가 세 개씩 적혀 있다. 첫 줄에서 시작하여 마지막 줄에서 끝나게 되는 놀이이다. 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 아래와 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어있는 수로만 이동할 수 있다. 별표는 현재 위치, 파란 동그라미가 내려갈 수 있는 위치 ..

http://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net # 조건 정수 A를 B로 바꾸려고하는데 가능한 연산은 아래 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. # 접근 방법 만들 수 없는 경우에는 -1을 출력한다. B+1만큼의 빈 리스트를 만들어서 BFS 탐색해준다. A에서 2를 곱한 수와 1을 오른쪽에 추가한 수에 현재 카운트를 기록해주며 B를 만난 경우 종료 해준다. 메모리 초과 모든 숫자에 대해 리스트에 기록해주니 입력이 커서 메모리초과 import sys sys.stdin = open('input...

http://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net # 조건 루트 없는 트리가 주어진다. 이 때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램 작성 입력 첫 줄에 노드의 개수 N (2 방문한 것 dfs 풀이 import sys sys.stdin = open('input.txt') input = sys.stdin.readline def dfs(start): parent=[0] * (N+1) parent[start] = 1 stack = [start] while stack: node = st..