문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 DP를 이용하여 풉니다. 문제에 주어진 예제를 2차원 DP 테이블에 나타내면 다음과 같습니다. - C A P C A K - 0 0 0 0 0 0 0 A 0 0 1 1 1 1 1 C 0 1 1 1 2 2 2 A 0 1 2 2 2 3 3 Y 0 1 2 2 2 3 3 K 0 1 2 2 2 3 4 P 0 1 2 3 3 3 4 입력받은 두 문자열을 순..

문제 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 풀이 간선의 비용이 전부 1로 같기 때문에 BFS를 사용했습니다. 딕셔너리 타입의 edges 변수에 (현재 노드: 연결된 다음 노드)의 형태로 값을 push합니다. BFS로 사이클의 갯수를 셉니다. 사이클을 찾으면 사이클 안에 포함된 노드들을 cycle_components 리스트에 넣어서 다음 사이클 탐색시 이미 사이클..

문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 각 도시에서 시작하여 모든 도시를 방문하고 다시 처음 도시로 돌아오는 한붓그리기 문제다. 간선의 비용이 다르고 경로의 정보를 저장해야하기 때문에 DFS를 사용한다. 외판원 최소 순회 비용인 min_value는 10억으로 초기화 한다. start: 시작 노드, current: 현재 노드, value: 현재 노드까지 쓴 비용, visited: 경..

문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 n - 1 번 순회하는 반복문으로 푼다. 매 반복마다 리터당 가격의 최소 값을 전역 변수(min_cost)에 저장하고, min_cost와 이동거리(road[i])의 곱을 전역 변수(total)에 누적해나간다. 코드 import sys n = int(sys.stdin.readline().rstrip()) roads = list(map(int, sys.stdin.readlin..

문제 https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 풀이 A와 B의 최대 길이는 50이기 때문에, A와 B의 최소 차이인 answer는 50으로 설정한다. A와 B를 비교할 때 A의 시작 지점을 기준으로 탐색한다. 경우의 수는 (len(B) - len(A) + 1)이다. 문제의 예제를 예를 들면, (A: adaabcX, B: aababbc)와 (A: Xadaabc, B: aababbc)인 두 가지 경우의..

문제 https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 풀이 입력으로 받은 지민의 번호와 임한수의 번호를 jimin과 hansu라는 변수에 저장한다. while 반복문으로 jimin과 hansu가 같아질 때 까지 반복문을 돌고, 한번 반복할 때마다 jimin과 hansu는 각각 jimin // 2, hansu // 2 만큼 작아지고 라운드 수(cnt)를 1만큼 더해준다. 코드 import sys n, jimin, hansu = map(int, sys.s..