흙금이네 블로그

아이디어 버블 소트는 1회전마다 바로 뒤의 수보다 큰 앞의 수가 한 칸씩 뒤로 이동하며 정렬된다. 따라서 정렬 후 수들이 뒤로 이동한 거리의 최댓값을 구한다. 풀이 딕셔너리 A에 순서를 키로, 수를 값으로 저장하고, 수가 작은 순으로 그 순서를 정렬한다. for문에서 정렬 전의 순서에서 정렬 후의 순서를 뺀 값의 최댓값을 res에 저장한 후, 1 증가시킨 res를 출력한다. import sys input = sys.stdin.readline def solution(): N = int(input()) A = dict() for i in range(N): A[i] = int(input()) A = sorted(A, key=lambda i: A[i]) res = 0 for i in range(N): res =..

아이디어 플로이드-워셜 알고리즘으로 모든 건물 간 거리를 구한 후, 왕복 시간을 최소로 하는 두 건물의 조합을 찾는다. 풀이 #1 (Python) 건물 개수 N은 100 이하이므로 모든 건물 간 거리를 저장하는 2차원 리스트 D를 생성하여 100으로 채운다. 같은 건물 간 거리는 0으로 저장하고, 입력 받은 도로 정보를 D에 반영한다. 플로이드-워셜로 건물 i에서 j로 가는 시간을 건물 k를 경유하여 가는 시간과 비교해 최솟값으로 갱신해 나간다. 양방향 도로이므로 건물 j에서 건물 i에서 가는 시간도 같은 값으로 저장하며, j는 i보다 큰 번호부터 시작하도록 한다. 모든 건물 간 거리를 구한 후, 이중 for문에서 건물 i와 j를 선택했을 때의 왕복 시간 합을 구해 결과값을 갱신한다. import sys..

아이디어 #1 동적 계획법으로 사용하는 동전의 최소 개수를 구한다. 풀이 #1 k+1로 초기화된 k+1 길이의 리스트를 dp를 생성한다. 차례로 입력 받은 동전의 가치 c가 k보다 크거나 중복되는 동전인 경우 continue로 건너뛰고, 아니면 dp[c]에 1을 저장한다. c보다 큰 가치 합들에서 각각 c를 뺀 가치 합의 사용 동전 최소 개수보다 1 큰 값과 비교해 dp의 최솟값을 갱신한다. 가치 합을 k로 만들 수 있으면 사용하는 동전의 최소 개수를 출력하고, 그렇지 않으면 -1을 출력한다. import sys input = sys.stdin.readline def solution(): n, k = map(int, input().split()) dp = [k+1]*(k+1) for _ in range(..