📌문제방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시에는 1번~N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다.연결된 두개의 회사는 양방향으로 이동할 수 있고 특정 회사와 다른 회사가 도로로 연결되어 있다면 1만큼의 시간으로 이동할 수 있다.또한 방문 판매원 A는 기대하던 소개팅에도 참석하고자 한다. 소개팅 상대는 K번 회사에 존재한다. A는 X번 회사에 가서 물건을 판매하기 전에 먼저 소개팅 상대의 회사에 찾아가서 함께 커피를 마실 예정이다. 따라서 A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표이다. 방문 판매원..
📌플로이드 워셜 알고리즘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용(다익스트라 알고리즘: 한 지점에서 다른 특정 지점까지의 최단 경로 구하는 경우 사용) 시간복잡도: O(N³) 다이나믹 프로그래밍노드의 개수 N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 갱신 📌플로이드 워셜 알고리즘 소스 코드INF = int(1e9) # 무한, 10억# 노드의 개수와 간선의 개수 입력받기n = int(input())m = int(input())# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화graph = [[INF] * (n + 1) for _ in rang..
📌방법 2. 개선된 다익스트라 알고리즘 시간 복잡도: O(ElogV), V=노드의 개수, E=간선의 개수힙 자료구조 사용특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있음(로그 시간) 방법 1에서 최단 거리가 가장 짧은 노드를 선택하는 과정을 우선순위 큐를 이용하는 방식으로 대체 📌개선된 다익스트라 알고리즘 소스 코드import heapqimport sysinput = sys.stdin.readlineINF = int(1e9) # 무한, 10억# 노드의 개수, 간선의 개수 입력받기n, m = map(int, input().split())# 시작 노드 번호 입력받기start = int(input())# 각 노드에 연결되어..
📌최단 경로가장 짧은 경로길 찾기 문제라고도 불림보통 그래프를 이용해 표현 최단 거리 알고리즘 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를 반복해서 조정'현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에 조건의 만족 여부(예 혹은 아니오..