http://www.acmicpc.net/problem/11719 11719번: 그대로 출력하기 2 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄이 주어질 수도 있고, 각 줄의 앞 뒤에 공백이 www.acmicpc.net # 조건 n(1

http://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net # 조건 월드나라에는 N개의 지점이 존재하고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀 도로는 무방향, 웜홀은 방향이 존재 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 도착을 하게 되면 시작 하였을 때보다 시간이 뒤로 가게 된다. 한 지점에서 출발하여 시간여행을 하기 시작하여서 다시 출발을 하였던 취로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있..

http://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 대표적인 백트래킹 문제 다른 알고리즘 사이트에서 통과 코드가 시간초과가 발생하여 pypy로만 통과되었다. 따라서 다른 사람의 코드 참고하여 공부가 필요할듯!! # 조건 N x N 크기의 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다 N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. # 접근 방법 전형적인 백트래킹 문제이다. 모든 경우의 수를 살펴보는 브루트포스를 기반으로 이후의 ..

http://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net # 조건 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매 스티커는 아래 그림과 같이 2행 n열로 배치 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져 사용 불가 점수의 합이 최대가 되도록 스티커를 붙여라 # 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 ..

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