문제LCS는 두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 알고리즘이다.예를 들어 ACAYKP와 CAPCAK의 LCS는 ACSK가 된다.입력첫째 줄과 둘째 줄에 문자열이 주어짐출력두 문자열의 LCS의 길이를 출력(1) 마지막 원소가 다른 경우ACAY와 CAPC의 LCS를 구해보자이때, ACA-CAP, ACAY-CAP, ACA-CAPC의 LCS는 알고 있다고 가정한다.여기에서 ACA-CAP의 부분수열 집합은ACAP-CAP의 부분수열 집합에 완전히 포함되고, ACA-CAPC의 부분수열 집합에도 완전히 포함된다.그러므로 ACAP-CAPC의 LCS를 구하기 위해서 ACA-CAPC의 LCS와 ACAP-CAP의 LCS 중 더 큰 값을 선택하면 된다.(2) 마지막 원소가 같은 경우AC..

문제n개의 도시, m개의 단방향 도로가 존재모든 도로의 거리는 1이다. 이때, 특정한 도시 x에서 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 k인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오.입력첫째 줄에 n, m, k, x가 주어짐둘째 줄부터 m개의 줄에 걸쳐서 두 개의 자연수 a, b가 공백을 기준으로 주어짐 이는 a에서 b로 이동하는 단방향 도로가 존재한다는 의미출력x에서 출발하여 도달할 수 있는 도시 중에서 최단 거리가 k인 모든 도시의 번호를 오름차순으로 출력하나도 존재하지 않다면 -1을 출력다익스트라로 풀리는 문제는 bfs로, bfs로 풀리는 문제는 다익스트라로 풀리는 경우가 많다!(1) 다익스트라 알고리즘을 이용한 풀이# dijkstra 풀이import sys,..

(1) naive한 구현# (1) naive한 구현def find_parent(parent, x): if parent[x] != x: return find_parent(parent, parent[x]) return parent[x]def union(parent, a, b): pa = find_parent(parent, a) pb = find_parent(parent, b) if pa > pb: parent[pa] = pb else: parent[pb] = paimport sysn, m = map(int, sys.stdin.readline().split())parent = [x for x in range(n+1)]for _ in range(m): a, b ..

슬라이딩 윈도우 기법창틀에 붙어있는 창문을 밀듯이 특정 범위를 이동시키며(밀면서) 변화하는 내부 값들을 처리하는 기법위와 같은 [1,3,2,6,-1,4,1,8,2]의 배열에서 연속된 수 5개의 합의 최댓값을 구한다고 할 때 슬라이딩 윈도우 기법을 이용하면 효율적으로 처리할 수 있다.첫번째 window 1+3+2+6+(-1) = 11 에서 두번째 window로 넘어 갈 때는 1을 빼주고 4를 더해주기만 하면 되므로 3+2+6+(-1)+4를 쌩으로 할 때보다 들어가는 연산의 수가 적어 훨씬 효율적으로 최댓값을 구할 수 있다.boj_2096 : 내려가기 문제숫자표가 주어져 있을때, 얻을 수 있는 최대 점수, 최소 점수를 구할 수 있는 프로그램을 작성하시오, 점수는 원룡이가 위치한 곳의 수의 합이다.입력첫째 줄..

문제정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. - 2를 곱한다. - 1을 수의 가장 오른쪽에 추가한다.A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.입력첫째 줄에 A, B (1출력A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다.만들 수 없는 경우에는 -1을 출력한다.겉보기에는 BFS의 전형적인 문제처럼 보이지만이 문제는 다른 일반적인 BFS 문제와 한 가지 차이점이 있다.입력값의 범위가 1 ~ 10^9로 매우 넓다는 점이다.visited를 리스트로 선언할 경우, 0이 저장되어 쓸 데 없이 낭비되는 메모리가 너무 많아 비효율적인 코드가 된다.그런데 이 문제는 graph가 주어지지 않기 때문에,굳이 visited(graph)를 리스트로 선언할 필요가 없..

문제상근이는 나무 M미터가 필요하다. 목재절단기의 높이 H를 지정하면 톱날이 땅으로 부터 H미터 만큼위로 올라간 다음, 한 줄에 연속해 있는 나무를 모두 절단해 버린다.따라서 높이가 H보다 큰 나무는 H 위 부분이 잘릴 것이고,낮은 나무는 잘리지 않을 것이다. 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.상근이가 적어도 M미터의 나무를 집으로 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.입력첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다.둘째 줄에는 나무의 높이가 주어진다. 나무 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다.출력적어도 M미터의 나무를 집에 가져가기 ..

문제00타일 과 1타일을 붙여서 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세시오.지원이는 N=1일 때 1만 만들 수 있고, N=2일 때 00, 11을 만들 수 있다.(01, 10은 만들 수 없다)또한 N=4일 때는 0011,0000,1001,1100,1111등 총 5개의 2진 수열을 만들 수 있다.입력 첫 번째 줄에 자연수 N이 주어진다.(1 출력첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다. 이 문제에서 지원이가 길이가 N인 이진 수열을 만들 때.마지막 타일을 00으로 선택하여 N-1번째와 N번째에 0이 오는 경우와 마지막 타일을 1로 선택하여 N번째에 1이 오는 경우는 교집합이 존재하지 않는 배반사건이므로지원이가 마지막..

(1) 최대 공약수def gcd(a, b): while a != 0 and b != 0: if a >= b: a %= b else: b %= a return a if b == 0 else b(2) 최소 공배수def lcm(a, b): def gcd(a, b): while a != 0 and b != 0: if a >= b: a %= b else: b %= a return a if b == 0 else b x = gcd(a, b) return int(a*b/x)