본문 바로가기

알고리즘60

[Python] 백준 20040번: 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 1. 플레이어 순서는 중요하지 않고 사이클이 발생하는 시점이 중요하다. 2. 사이클이 발생한다는것은 즉 두 노드의 부모가 같다는 뜻이다. 3. 이미 정답이 나왔으면 더이상 실행할 필요가 없다. ans = 0 n, m = map(int, input().split()) unf = [i for i in range(n)] def find(x): if x == unf[x]: return x unf[x.. 2021. 10. 6.
[Python] 백준 9084 동전 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 1. 배낭 문제이다. 점화식은 현재까지 가능한 개수에 현재 동전을빼준값에 가능한 개수를 더한다. dp[i] = dp [i] + dp [j-x]이다. T = int(input()) while T: T -= 1 n = int(input()) coin = [0] + list(map(int, input().split())) goal = int(input()) dp = [0 for _ in.. 2021. 10. 5.
[Python] 백준 7579: 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 0 1 2 3 4 5 6 0 0 0 0 0 0 0 (30, 3) 0 0 0 30 30 30 30 (10, 0) (20, 3) (35, 5) (40, 4) 0 1 2 3 4 5 6 0 0 0 0 0 0 0 (30, 3) 0 0 0 30 30 30 30 (10, 0) 0 10 10 40 40 40 40 (20, 3) (35, 5) (40, 4) 0 1 2 3 4 5 6 0 0 0 0 0 0 0 (30, 3).. 2021. 10. 4.
[Python] 백준 5582: 공통 부분 문자열 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net E C A D A D A B R A 0 0 1 0 1 0 1 0 0 B R A C A D A B E C A D A D A B R A 0 0 1 0 1 0 1 0 0 B 0 0 0 0 0 0 0 2 0 R A C A D A B E C A D A D A B R A 0 0 1 0 1 0 1 0 0 B 0 0 0 0 0 0 0 2 0 R 0 0 0 0 0 0 0 0 3 A C A D A B E.. 2021. 10. 4.

티스토리툴바