오예 !!!

다익스트라 최단 경로 알고리즘 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 '음의 간선' 즉, 0보다 작은 값을 가지는 간선이 없을 때 정상적으로 동작 기본적으로 그리디 알고리즘 매번 가장 비용이 적은 노드를 선택 알고리즘 동작 원리 출발 노드를 설정한다 최단 거리 테이블을 초기화한다 방문하지 않은 노드들 중에서 최단 거리가 가장 짧은 노드를 선택한다 해당 노드를 거쳐 다른 노드로 가는 비용을 계산한 후, 기존 비용과 비교하여 더 작은 값으로 최단 거리 테이블을 갱신한다 3번과 4번 과정을 반복한다 항상 '각 노드에 대한 현재까지의 최단 거리' 정보를 1차원 리스트인 최단 거리 테이블에 저장하며 리스트를 계속 갱신함 2가지 구현 방법 존재 ..

최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 '길찾기' 문제 다양한 유형의 문제 존재 ex) 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우, 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우 등 실제 코테에서는 주로 전자를 요구하는 문제가 많이 출제됨 그래프를 이용하여 표현함 각 지점은 그래프의 노드 지점 간 연결된 도로는 그래프의 간선 주요 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘 플로이드 워셜 벨만 포드 알고리즘 1, 2가 코테에서 주로 출제 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 적용됨

이코테 p.226 실전 문제 - 효율적인 화폐 구성 입력 예시 3 7 2 3 5 출력 예시 2 내 소스코드 점화식 a(i) = min(a(i - money[0]), a(i - money[1]), a(i - money[2]), ...) + 1 최솟값을 구하기 위해 DP 리스트를 INF로 초기화 # 입력 받기 n, m = map(int, input().split()) money_list = list(map(int, input().split())) INF = 10001 dp = [INF] * (m + 1) # 자기 자신에 대해서는 최소 화폐 개수 1개 for money in money_list: dp[money] = 1 for i in range(min(money_list), m + 1): min_money ..

이코테 p.223 실전 문제 - 바닥 공사 입력 예시 3 출력 예시 5 교재 소스코드 다이나믹 프로그래밍 기초 예제 중 하나인 타일링 문제 유형 N = 3 일 경우 바닥을 덮개로 채울 수 있는 모든 경우의 수는 다음과 같음 왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 다음과 같은 점화식을 세울 수 있음 왼쪽부터 (i - 1)까지의 길이가 덮개로 이미 채워져 있으면 2 x 1 덮개를 채우는 하나의 경우만 존재 왼쪽부터 (i - 2)까지의 길이가 덮개로 이미 채워져 있으면 2 x 2 덮개를 채우는 경우와 1 x 2 덮개를 채우는 경우 총 2가지 존재 따라서 점화식은 a(i) = a(i - 1) + a(i - 2) x 2 이를 DP 구현하면 다음과 같음 # 점수 N 입력받기 n = int(input())..

이코테 p.220 실전 문제 - 개미 전사 입력 예시 4 1 3 1 5 출력 예시 8 교재 소스코드 왼쪽 식량 창고부터 차례대로 털지 안 털지를 결정하는데, 특정한 i번째 식량 창고를 털지 안 털지를 결정하는 경우의 수는 2가지 존재 (i - 1)번째 식량 창고를 턴다면 현재 식량 창고는 털 수 없음 (i - 2)번째 식량 창고를 턴다면 현재 식량 창고를 털 수 있음 참고로 (i - 3)번째 이하의 식량 창고는 항상 털 수 있기 때문에 고려할 필요 없음 따라서 이 두가지 중에서 더 많은 식량을 털 수 있는 경우 선택 구체적인 과정 예시: n = 4, 리스트는 [1, 3, 1, 5]로 주어졌을 때, 왼쪽부터 턴다고 가정 첫 번째 식량 창고에서 털 수 있는 최대 식량은 1 두 번째 식량 창고에서 털 수 있는..

이코테 p.217 실전 문제 - 1로 만들기 입력 예시 26 출력 예시 3 교재 소스코드 해당 문제는 잘 알려진 DP 문제 함수가 호출되는 과정을 도식화해보면 동일한 값을 구하는 동일한 함수가 중복으로 호출되는 것을 알 수 있음 ➡️ DP 적용 바텀업 방식으로 구현 2부터 X까지 차근차근 해당 수를 만들 수 있는 최소 연산 횟수를 기록해 나가는 방식 1을 뺐을 때, 2로 나누었을 때, 3으로 나누었을 때, 5로 나누었을 때 중에서 최소가 되는 연산 횟수를 현재의 연산 횟수로 기록해야 함 dp[i]는 숫자 i를 만들 수 있는 최소 연산 횟수를 의미 점화식으로 표현하자면, a(i) = min(a(i - 1), a(i / 2), a(i / 3), a(i / 5)) + 1 +1을 해주는 이유는 연산의 횟수를 구..

다이나믹 프로그래밍 개요 주요 컨셉: 중복되는 연산을 줄이자! 컴퓨터 연산 속도에는 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적임 ➡️ 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘 작성 필요 다이나믹 프로그래밍과 같은 방법을 적용하면 메모리 공간을 약간 더 사용함으로써 연산 속도를 비약적으로 증가시켜 시간을 단축할 수 있음 대표적인 예시 - 피보나치 수열 피보나치 수열 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열 점화식으로 표현하면 a(n) = a(n - 1) + a(n - 2), a(1) = 1, a(2) =1 즉, n번째 피보나치 수 = (n - 1)번째 피보나치 수 + (n - 2)번째 피보나치 수 단, 1번째 피보나치 수 = 1, 2번..

이코테 p.201 실전 문제 - 떡볶이 떡 만들기 입력 예시 4 6 19 15 10 17 출력 예시 15 내 소스코드 주어진 떡 길이 중에서 가장 긴 떡의 길이를 기준으로 1씩 감소시켜 가며 조건을 만족시키는지 확인하는 방식으로 구현함 ex) 가장 긴 떡이 19라면 18, 17, 16, ... 처럼 1씩 감소시켜 나가면서 해당 길이로 떡을 잘랐을 경우 조건을 만족하는지 확인 순차 탐색이라 데이터가 많을 수록 비효율적. 해당 문제에 적합하지 않음. # 입력 받기 n, m = map(int, input().split()) array = list(map(int, input().split())) array.sort() # 이진 탐색을 통해 탐색 범위 좁기 def binary_search(array, target..