honey_pot

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용 다익스트라처럼 단계마다 '거쳐 가는 노드'를 기준으로 수행되지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다. 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2) 의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. ➡ 총시간 복잡도 O(N^3) 다익스트라 플로이드-워셜 최단 거리 테이블 1차원 리스트 2차원리스트 방법 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾음 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾지 않음 전체 시간 복잡도 O..

최단 경로 ( Shortest Path) 가장 짧은 경로를 찾는 알고리즘 ➡ 길 찾기 문제 다익스트라 최단 경로 알고리즘 플로이드 워셜 최단 경로 알고리즘 다익스트라(Dijkstra) 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘 '음의 간선' 이 없을 때 정상적으로 동작 ( 음의 간선 ➡ 0보다 작은 값을 가지는 간선을 의미) GPS 소프트웨어의 기본 알고리즘 '가장 비용이 적은 노드'를 선택해서 과정을 반복 ➡ 기본적으로 그리디 알고리즘으로 분류 알고리즘 원리 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로..

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 한다. 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. 입력 조건 첫째 줄에 N,M이 주어진다. (1

바닥을 세 종류의 덮개로 채우는 모든 경우의 수를 구하는 프로그램을 작성하라. 예를 들어 2 x 3 크기의 바닥을 채우는 경우의 수는 5가지이다. 입력 조건 첫째 줄에 N이 주어진다. (1

정해진 수의 식량을 저장한 식량창고에서 개미 전사는 선택적으로 약탈하여 식량을 빼앗는다. 정찰병에게 들키지 않고 약탈하기 위해서 는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 {1, 3, 1, 5} 의 식량 창고가 있을 때 개미 전사는 두번째, 네번째 식량창고를 선택했을 때 최댓값인 8개의 식량을 빼앗을 수 있다. 식량창고 N개에 대한 정보가 주어졌을 때, 얻을 수 있는 식량의 최댓값을 구하는 프로그랭램을 작성하시오 입력 조건 첫째 줄은 식량창고의 개수 N이 주어진다. (3

정수 X가 주어질 때 정수 X에 사용할 수 있는 연사능ㄴ 다음과 같이 4가지이다. X가 5로 나누어 떨어지면, 5로 나눈다. X가 3으로 나누어 떨어지면, 3로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. X에서 1을 뺀다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 조건 첫째 줄에 정수 X가 주어진다.(1

다이나믹 프로그래밍 (Dynamic Progamming) 동적 계획법 탐다운 / 보텀업 메모이제이션 ➡ 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 ➡ 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다. DP 사용 조건 큰 문제를 작은 문제로 나눌 수 있다. ➡ 탑다운 방식(하향식) ( 분할정복Divide and Conquer 인 퀵정렬과 달리 DP는 문제들이 서로 영향을 미침) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. ➡ 보텀업(상향식) 방식(반복문을 이용해 작은 문제부터 답을 도출) DP 문제를 푸는 방법 DP 유형임을 파악한다. 문제에서 부분 문제들의 중복 여부를 확인한다. 탑다운 방식으로 재귀함수로 구..

절단기에 높이(H)를 지정해 줄지어진 떡을 한 번에 절단한다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 4, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. ( 1