http://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net # 조건 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제 예 ACAYKP와 CAPCAK의 LCS는 ACAK # 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져있으며, 최대 1000글자로 이루어져 있다. ..

LCS (Longest Common Subsequence) 란? 2개 이상의 문자열에서 공통으로 나타나는 부분 문자열 중 가장 긴 문자열을 의미 대표적으로 DNA의 공통 염기서열을 찾아 데이터를 압축하거나 무선 서명을 통해 휴대폰에서 사용자를 인증할 때 사용 풀이 방법 분할정복이 아닌 DP를 이용하여 풀이해준다. 1. Top-down 방법 (재귀적 풀이) 문자열 X, Y 가 X = [x1, x2, x3, .... , xm], Y = [y1, y2, y3, ... , yn] 일 때, 아래와 같은 과정을 반복한다. LCS(X, Y): #수열 X와 Y의 최장 공통 부분 수열(LCS)의 길이 m, n = len(X), len(Y) if m == 0 or n == 0: return 0 else: if X[-1] ..

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