알고리즘
다익스트라 알고리즘 플로우 요약 반복문 이전 출발 노드에서 각 노드로의 최단 거리를 갱신,기록하는 배열 선언 더 적은 이동거리를 우선하는 우선순위 큐를 선언 우선순위 큐에 초기 상태 삽입 반복문 이후 큐에서 꺼낸 상태가 현재 최소 경로인지 검사 및 갱신 다음 방문 가능한 노드에 대하여 큐에 삽입 다익스트라의 꽃은 최적 상태 검사 다익스트라 알고리즘은 출발 노드로 부터 각 모든 도착 노드까지 최소 비용의 경로로 방문하게 되는 알고리즘이다. 따라서 최적으로 이동하고있지 않은 상태는 유망하지 않은 상태가 되며 더 이상 탐색하지 않아도 된다. 예를 들어 a 노드에서 c 노드까지 가는데 이미 5라는 비용으로 방문하는 방법을 알았다면, 7이라는 비용이 발생하는 동일 경로는 버려버리면 된다. 이 때 현재 상태가 최적..
문제 링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단..
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 나무들의 길이 배열과 절단할 높이 H 가 있을 때, 나무 길이 배열을 순회하며 H보다 높은 나무들은 잘리게 되고, 이때 잘린 부분의 총합을 X라고 한다. X의 값이 M보다 크거나 같기 위한 절단할 높이 H의 최댓값을 구하라. 입력 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, ..
문제 링크 : https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 큐를 활용한 풀이 x : 삭제 연산 b : 뒤로 보내기 연산 이라고 했을 때 N=5인 경우는 아래와 같이 진행된다. Iter 1 12345 xbooo (1을 삭제 2를 뒤로 보내기) Iter 2 3452 xboo Iter 3 524 xbo Iter 4 42 xb 남은 2가 정답! 데이터의 흐름이 앞 - 12345 - 뒤 라고 생각했을 때 앞에서 뒤로만 이동한다. queue를 사용해야..
