정렬 알고리즘 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] = ..
다이나믹 프로그래밍 알고리즘 Q www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net A 입력조건만 조심해서 풀면 된다. 코드 n = int(input()) d = [0] * 21 d[0] = 0 d[1] = 1 d[2] = 1 for i in range(3, n+1): d[i] = d[i-1] + d[i-2] print(d[n])
다이나믹 프로그래밍 알고리즘 Q www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net A 다이나믹 프로그래밍을 이용하여 풀었다. 코드 n = int(input()) d = [0] * 91 d[1] = 1 d[2] = 1 for i in range(3, n+1): d[i] = d[i-1] + d[i-2] print(d[n])
정렬 알고리즘 Q www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net A 시간초과에 주의해서 풀어야 한다. 코드 import sys #input하면 시간초과 발생하므로 sys 라이브러리 사용한다. n = int(input()) array = list(int(sys.stdin.rstrip()) for _ in range(n)) array.sort() for i in array: print(i)