다이나믹 프로그래밍 Q www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net A 다이나믹 프로그래밍을 이용할 경우, 규칙을 찾는 것이 중요하다. 밑에 메모리 초과한 코드를 보면, 그냥 DP 테이블 초기화한 다음 거기에 다 저장하려 했어서 메모리 초과가 일어났다. 그리고 중요한 점은 N은 40보다 작은 자연수 또는 0 이라는 점이다. DP 테이블을 n + 1 의 크기로 만드는 것이 아니라 41의 크기로 만들어야 하며, 점화식을 위한 반복문 또한 마찬가지이다. 0과 1의 갯수가 각각 피보나치 수열을 따르고 있으므로 DP 테이블을 두개 만들어서 문제를 해결했다. 코..
최단 경로 알고리즘 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][..
최단 경로(Shortest Path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 여러 유형이 있는데, 그 중 다익스트라 알고리즘과 플로이드 워셜 알고리즘을 공부하겠다. 1. 다익스트라 알고리즘 (1) 이론 다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다. '음의 간선'이 없을 때 정상적으로 동작한다. 동작원리는 다음과 같다. 1) 출발 노드를 설정한다. 2) 최단 거리 테이블을 초기화한다. 3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5) 3, 4번을 ..
정렬 알고리즘 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좌표 순으로 오름차순..
