최단 경로 알고리즘 Q www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net A 플로이드 워셜 알고리즘을 이용하여 풀었다. 코드 INF = int(1e9) n, m = map(int, input().split()) graph = [[INF] * (n + 1) for _ in range(n + 1)] for a in range(n + 1): for b in range(n + 1): if a == b: graph[a][..
정렬 알고리즘 Q www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net A sort()를 사용하여 풀었다. 입력받는 것만 잘 처리하면 어렵지 않은 문제이다. 코드 n = int(input()) array = [0] * n for i in range(n): #여러 데이터의 여러 줄 입력받기 array[i] = list(map(int, input().split())) array.sort() #x좌표 순으로 오름차순..
다이나믹 프로그래밍 알고리즘 Q www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net A 다이나믹 프로그래밍을 이용하여 풀었다. 피보나치 수열인 것을 파악하면 쉽다. 코드 n = int(input()) d = [0] * 81 d[0] = 4 d[1] = 6 for i in range(2, n+1): d[i] = d[i-1] + d[i-2] print(d[i - 1])
다이나믹 프로그래밍 알고리즘 Q www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net A 다이나믹 프로그래밍을 이용하여 풀었다. 주의할 점은 문자열이기 때문에 단순히 풀면 메모리초과가 일어날 수 있다. A와 B가 각자 피보나치 수열을 따른다는 것을 이용하여 풀어야 한다. 코드 k = int(input()) #정수 입력 d = [0] * 46 #DP 테이블 초기화 d[0] = 0 d[1] = 1 c = [0] * 46 #DP 테이블 초기화 c[0] = 0 c[1] = ..
