1. 최단거리 알고리즘이란? 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 주로 그래프를 이용하여 표현하며 각 지점은 노드, 지점 간 연결선은 간선으로 표현한다. 이번 포스트에서는 대표적인 최단거리 알고리즘인 다익스트라 알고리즘과 플로이드 워셜 알고리즘에 대해 소개하겠다. 2. 다익스트라 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 음의 간선이 없을 때 정상적으로 동작하며, 매번 가장 비용이 적은 노드를 선택하기 때문에 그리디 알고리즘으로 분류된다. 음의 간선 - 0보다 작은 값을 구하는 간선 음의 간선이 포함되었을 경우에는 벨만 포드 알고리즘을 사용해야 한다. 다익스트라 알고리즘의 구현 🍥 각 노드에 대해 현재까..

2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 1. 문제 설명 이번 문제는 일반적인 구간 합 문제와 달리 수의 변경이 빈번하게 일어나는 것이 핵심적인 차이점이다. 간단한 구간 합 문제는 누적 합의 차로 쉽게 구할 수 있지만, 중간에 계속 수가 변경된다면 누적 합이 일정하지 않으므로 해당 방법을 사용할 수 없다. 이렇게 원소가 변경될 때 구간 합을 구할 때 사용할 수 있는 방법이 세그먼트 트리이다. 자세한 개념 설명은 따로 정리해두었으니 아래 링크를 ..

1. 세그먼트 트리란? 여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등 ...)을 구하는데 사용하는 자료 구조이다. 트리 종류 중 하나로 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다는 장점이 있다. → O(logN) 세그먼트 트리는 이진 트리 중에서도 전 이진트리(Full Binary Tree)에 해당한다. 전 이진 트리: 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리 2. 세그먼트 트리의 구성 먼저 이진 트리를 구성할 때 루트 노드는 1부터 시작한다. (0부터 시작하면 인덱스 관리가 어렵다) 그 아래부터는 부모 노드의 인덱스를 i라고 할 때 왼쪽 자식 노드는 2i, 오른쪽 자식 노드는 2i+1이 된다. 아래는 A={ 1, 2, 3, 4, 5 }라는 ..

7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 1. 문제 설명 2. 예제 설명 3. 구현 아이디어 1 - 틀렸습니다. C++의 priority_queue에서는 가장 위(top)의 원소만 반환할 수 있다. 매 연산마다 우선순위 큐를 뒤집는 것은 비효율적이기 때문에 최댓값과 최솟값 둘 다 접근하기 위해서는 우선순위 큐를 2개 만들어야 한다. 그리고 중요한 것이 2개의 우선순위 큐를 동기화해주는 것이다. 최댓값 또는 최솟값을 삭제할 때 하나의 큐에서만 삭제하면 다음 연산을 진행할 때 연산이 원하는대로 이루어지..

9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 1. 문제 설명 예제 입력 1에서 첫 번째 테스트 케이스는 문제 속 예시와 동일하고, 두 번째 테스트 케이스는 하늘색 박스를 친 스티커를 골랐을 때가 점수가 최대가 된다. 2. 구현 아이디어 처음 봤을 때 백준 1149번: RGB 거리와 비슷하게 풀면 될 것 같다는 생각이 들었다. 그래서 점화식을 아래와 같이 세웠다. 🍙 점화식 dp[0][i] = dp[1][i-1] + board[0][i] dp[1][i] = dp[0][i-1] + board[1][..

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 문제 각 예제별 트리의 모습을 입력 오른쪽에 그림으로 표현하였다. 2. 구현 아이디어 1 - 틀렸습니다 그래프를 표현하는 방법에는 인접 행렬과 인접 리스트가 있는데, 인접 리스트 방식을 사용하였다. map 자료구조를 사용하여 key는 부모 노드, value는 자식 노드의 배열로 하였다. 재귀(DFS)를 사용하여 자식 노드가 없을 때를 종료 조건으로 하고 종료 조건일 때마다 리프 노드의 개수를 +1하도록 재귀 함수를 구현하였다. 만약 제거할 노드가 루트..