For Programmer

다익스트라 알고리즘을 사용하기 위해서는 우선 우선순위 큐라는 알고리즘을 사용해야한다. 다익스트라 알고리즘 소스코드 import heapq import sys input = sys.stdin.readline INF = int(1e9) #무한을 의미하는 값으로 10억을 설정 #노드의 개수, 간선의 개수를 입력 받기 n,m = map(int,sys.stdin.readline().split()) #시작 노드 번호를 입력 받기 start = int(sys.stdin.readline()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for i in range(n+1)] #최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n+1) #모든 간선 ..

정답 코드 #정수 N,M을 입력 받기 n,m = map(int, input().split()) #N개의 화페 단위 정보를 입력받기 array = [] for i in range(n): array.append(int(input())) #한번 계산된 결과를 저장하기 위한 DP테이블 초기화 d = [10001] * (m+1) #다이나믹 프로그래밍 진행(바텀업) d[0] = 0 for i in range(n): for j in range(array[i], m+1): if d[j - array[i]] != 10001: #(i-k)원을 만드는 방법이 존재하는 경우 d[j] = min(d[j],d[j-array[i]]+1) #계산된 결과 출력 if d[m] == 10001: #최종적으로 M원을 만드는 방법이 없는 경..

1. 개미전사 문제 정답코드 #정수 N을 입력 받기 n = int(input()) #모든 식량 정보 입력 받기 array = list(map(int,input().split())) #앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 100 #DP진행(바텀업) d[0] = array[0] d[1] = max(array[0],array[1]) for i in range(2,n): d[i] = max(d[i-1],d[i-2]+array[i]) print(d[n-1]) 2. 1로 만들기 문제 정답 코드 x = int(input()) #앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 30001 #DP진행(바텀업) for i in range(2,x+1): #현재의 수에서..

DP의 대표적인 예 : 피보나치 수열 피보나치 수열 단순 재귀 코드 #피보나치 함수를 재귀함수로 구현 def fibo(x): if x ==1 or x==2: return 1 return fibo(x-1) + fibo(x-2) print(fibo(6)) 8 탑다운 소스 코드(메모이제이션) #한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화 d = [0] * 100 #피보나치 함수를 재귀함수로 구현(탑다운 DP) def fibo(x): #종료 조건(1혹은 2일때 1을 반환) if x == 1 or x ==2: return 1 #이미 계산한 적 있는 문제라면 그대로 반환 if d[x] != 0: return d[x] #아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환 d[x] = fibo..

1. 떡볶이 떡 만들기 문제 정답 코드 #떡의 개수(N)와 요청한 떡의 길이(M)을 입력 n,m = list(map(int,input().split())) #각 떡의 개별 높이 정보를 입력 array = list(map(int,input().split())) #이진 탐색을 위한 시작점과 끝점 설정 start = 0 end = max(array) result = 0 #이진 탐색 수행(반복적) while(start mid: total += x - mid #떡의 양이 부족할 경우 더 많이 자르기(왼쪽 부분 탐색) if total < m: end = mid -1 #떡의 양이 충분할 경우 덜 자르기(오른쪽 부분 탐색) else: result = mid #최대한 덜 잘랐을 때가 정답이므로, 여기서 result 기록..

이진탐색 알고리즘 소스코드 이진탐색 재귀적 구현 #이진 탐색 소스코드 구현(재귀함수) def binary_search(array,target,start,end): if start > end: return None mid = (start + end) // 2 #찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: return binary_search(array,target,start,mid-1) #중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else: return binary_search(array,target,mid+1,end) #n(원소의 개수)과..

소스코드 나의 코드 n,k = map(int,input().split()) arrayA = list(map(int,input().split())) arrayB = list(map(int,input().split())) arrayA.sort() arrayB.sort(reverse=True) for i in range(k): if(arrayA[i] break 문을 빼먹음 정답 코드 import builtins n,k = map(int,input().split()) a = list(map(int,input().split())) b = list(map(int,input()...

1. 선택정렬 선택정렬 코드 선택정렬 시간복잡도 삽입정렬 삽입 정렬 소스코드 array = [7,5,9,0,3,1,6,2,4,8] for i in range(1,len(array)): for j in range(i,0,-1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법 if array[j] < array[j-1]: #한 칸씩 왼쪽으로 이동 array[j],array[j-1] = array[j-1],array[j] else: #앞쪽은 이미 정렬이 되어있기 때문에 자기보다 작은 데이터 만나면 그자리에서 멈춤 break print(array) 삽입정렬 시간 복잡도 퀵 정렬 소스코드 array = [5,7,9,0,3,1,6,2,4,8] def quick_sort(array,start,end): if ..