📌최단 경로가장 짧은 경로길 찾기 문제라고도 불림보통 그래프를 이용해 표현 최단 거리 알고리즘 3가지: 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용 📌다익스트라 최단 경로 알고리즘그래프에서 여러 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘매번 가장 비용이 적은 노드를 선택해서 다음 과정을 반복1. 출발 노드 설정2. 최단 거리 테이블 초기화3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신5. 3, 4번 반복 각 노드에 대한 현재까지의 최단 거리 정보..
📌문제N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 각 몇개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 📌풀이적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾음 📌코드n, m = map(int, input().split())array = []for i in range(n): array.append(int(input()))# 한번 계산된 결과를 저장하기 위한 DP 테이블 초기화d = [10001] * (m + 1)# 다이나믹 프로그래밍(보텀업)d[0] = 0for i in range(n): for j in range(array..
📌문제가로가 N 세로가 2인 직사각형 형태의 바닥이 있다. 이 얇은 바닥을 1x2, 2x1, 2x2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 📌풀이1. 왼쪽부터 (i-1)까지의 길이가 덮개로 채워져있다면 2x1의 덮개를 채우는 하나의 경우2. 왼쪽부터 (i-2)까지의 길이가 덮개로 채워져있다면 1x2 덮개 2개를 넣는 경우 2x2 덮개 하나를 넣는 경우 📌코드n = int(input())# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화d = [0] * 1001# 다이나믹 프로그래밍(보텀업)d[1] = 1d[2] = 3for i in range(3, n + 1): d[i] = (d[i - 1] + 2 * d[i - 2]) % ..
📌문제개미 전사는 메뚜기 마을의 식량창고를 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량 창고가 있고 일직선으로 이어져있다. 개미 전사는 식량 창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 메뚜기 정찰병들은 일직선상에 존재하는 식량 창고 중 서로 인접한 식량 창고가 공격받으면 바로 알 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오. 📌풀이1. (i-1)번째 식량창고를 턴다면 현재의 식량창고를 털 수 없다.2. (i-2)번째 식량창고를 턴다면 현재의 식량창고를 털 수 있다.1과 2 중에서 더..
📌문제정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음 4가지이다.1. X가 5로 나누어 떨어지면, 5로 나눈다.2. X가 3으로 나누어 떨어지면, 3으로 나눈다.3. X가 2로 나누어 떨어지면, 2로 나눈다.4. X에서 1을 뺀다. 정수 X가 주어졌을 때 연산 4개를 적절히 사용해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 📌풀이만약 x=6일 때f(6) -> f(5), f(3), f(2) f(5) -> f(4), f(1)f(3) -> f(2), f(1)f(2) -> f(1), f(1)같은 함수들이 동일하게 여러번 호출되고 있으므로 다이나믹 프로그래밍으로 해결 📌코드x = int(input())# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화d = [0] ..
📌다이내믹 프로그래밍큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 컴퓨터는 연산 속도에 한계, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이기 때문에 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘 작성해야 함 하지만 다이나믹 프로그래밍 기법을 통해 메모리 공간을 약간 더 사용하면 연산 속도 비약적으로 증가 시킬 수 있는 문제도 존재 📌다이내믹 프로그래밍 사용 조건1. 큰 문제를 작은 문제로 나눌 수 있다.2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 📌메모이제이션 기법다이나믹 프로그래밍을 구현하는 방법 중 하나한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대..
📌문제한 봉지 안에 들어가는 떡볶이 떡의 총 길이를 절단기로 잘라서 맞춰준다.절단기에 높이 H를 지정하면 줄지어진 떡을 한 번에 절단한다.예를 들어 높이가 19, 14, 10, 16cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다.손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오. 📌풀이적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정'현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에 조건의 만족 여부(예 혹은 아니오..
📌문제동빈이네 전자매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 📌풀이다량의 데이터 검색은 이진 탐색 알고리즘을 이용해 효과적으로 처리 N개의 부품을 번호 기준으로 정렬이후 M개의 찾고자 하는 부품이 정렬한 리스트에 존재하는지 확인 이진 탐색은 정렬 되어 있어야만 사용 가능 📌코드def binary_search(array, target, start, end): while start target: en..
📌이진 탐색배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘배열이 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징 위치를 나타내는 변수 3개 사용시작점, 끝점, 중간점 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾음 한번 확인할 때마다 확인하는 원소가 절반씩 줄어든다는 점에서 시간 복잡도 O(logN) 📌재귀 함수로 구현한 이진 탐색def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if ar..
📌문제동빈이는 두 개의 배열 A, B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다.최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.N, K 그리고 배열 A, B가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최대값을 출력하는 프로그램을 작성하시오. 📌풀이배열 A에서 가장 작은 원소를 골라서 배열 B에서 가장 큰 원소와 교체단, 배열 A에서 가장 작은 원소가 배열 B에서 가장 큰 원소보다 작을 때에만 교체를 수행해야 함이 ..