http://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net # 조건 NxM 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. (1,1)에서 (N, M)의 위치까지 이동하려 하는데, 이 때 최단 경로로 이동하려 한다. 최단 경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약 이동하는 도중 한 개의 벽을 부..

http://www.acmicpc.net/problem/14552 14552번: Mahjong 첫 번째 예제에서는, 7이 들어오면, 머리가 55, 몸통이 111/222/789/789 형태로 완성 될 수 있다. 두 번째 예제에서는, 모든 패가 대기패이다. 세 번째 예제에서는, 2가 들어오면 머리가 11/22/33/44/66/88/9 www.acmicpc.net # 조건 마작을 연습하기 위해 프로그램을 만든다. 136개의 패를 가지고 하는 게임이지만 우리는 단순화 시켜서 삭수패 9종류 (1~9삭)를 4개씩, 총 36개의 패만 가지고 만든다. 머리는 같은 패 2개의 조합을 말하고, 몸통은 연속된 패 3개 혹은 같은 패 3개의 조합을 말한다. (2삭): 패가 하나이므로, 머리도 몸통도 될 수 없다. (3삭, 3..

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/23083 23083번: 꿀벌 승연이 첫째 줄에 $N$, $M$이 공백으로 구분되어 주어진다. 다음 줄에는 구멍 칸의 개수 $K$가 주어진다. 이어서 $K$개 줄에 구멍 칸의 정보 $x_i$, $y_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 www.acmicpc.net # 조건 승연이가 사는 벌집은 조금 특이한 구조로 되어있다. 벌집은 N행 M열의 격자로 이루어져 있고, 각 칸은 정육각형 모양 같은 행에 위치한 두 칸을 비교했을 때, 짝수번째 열의 칸은 홀수 번째 열의 칸보다 반 칸 아래에 위치 두 육각형 칸이 하나의 변을 공유하고 있다면 서로 인접하다. 벌집 내에서는 아래쪽, 오른쪽 위, 오른쪽 아래 칸으로만 이동..

http://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net # 조건 수빈이는 동생과 숨바꼭질하고 있다. 현재 점 N에 있고, 동생은 점 K에 있다. 수빈이는 걷거나 순간이동을 하는데 걷는다면 1초 후에 X-1 또는 X+1로 이동 순간이동을 하면 0초 후에 2 * X로 이동 수빈이와 동생의 위치가 주어질 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하여라 # 접근 방법 및 Solution 현재 점 N..

http://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net # 조건 동생 N명과 숨바꼭질 수빈이는 현재 점 S에 있고, 동생은 A1, A2 .. An 수빈이는 걸어서 이동을 할 수 있는데, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X+D나 X-D로 이동 가능 수빈이의 위치가 동생이 있는 위치와 같다면 동생을 찾았다고 한다. 모든 동생을 찾기 위해 D의 값을 정하는데 가능한 D의 최댓값을 구하여라. # 접근 방법 동생들의 ..

최대 공약수 숫자 a,b가 주어졌을 때, 공통되는 약수 중 최대 값을 의미한다. 구하는 방법 a,b 각각의 약수를 구해서 공통되는 약수 중 가장 큰 값을 찾는 방법 찾지 않아도 되는 약수들까지 구해야하기 때문에 비효율적이다. 유클리드 호제법 숫자 a,b가 있을 때, a를 b로 나눈 나머지와 b의 최대 공약수는 a와 b의 최대 공약수가 같다는 것을 의미한다. 따라서, a를 b로 계속 나누어서 b에 a로 나눈 나머지를 대입시켜서 b가 0이 될 때까지 반복을 하면, 남는 a의 값이 바로 최대 공약수이다. def gcd(a, b): while b > 0: a, b = b, a % b return a 최소 공배수 서로 다른 수 a,b의 배수 중에서 공통되는 배수 중 가장 작은 값을 의미 최소 공배수는 a,b의 곱..

http://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net # 조건 트리는 사이클이 없는 무방향 그래프 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있다. 이 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하면 트리에 존재하는..