[자료구조] 우선순위 큐(Priority Queue)

목 차 우선순위 큐 최소 힙 시간 복잡도 작동 원리 구현 코드 우선순위 큐 우선순위 큐(Priority Queue)는 말 그대로 우선순위를 가진 요소들을 저장하는 자료구조이다. 우선순위가 가장 높은 요소를 먼저 꺼낼 수 있게 한다. 대표적으로 최소 힙, 최대 힙이 있다. 최소 힙 다익스트라 알고리즘(Dijkstra Algorithm)을 학습하기 전에 우선순위 큐를 배우고 그중에서 최소 힙을 배우기에 이 번에는 최소 힙만 다룰 예정이다. 시간 복잡도 우선순위 큐를 구현하는 방법에는 여러 가지 있지만, 힙(Heap) 자료구조를 사용하는 것이 가장 효율적이고 우선순위가 가장 높은 데이터를 꺼내는데 O(log N) 만큼 걸린다. 작동 원리 1. 삽입(Insert): 새로운 요소는 항상 배열의 마지막에 들어간다(..

Algorithm 2023.10.26

[백준] 2579: 계단 오르기 - JS (DP)

목 차 문제 접근 방식 풀이 문제 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오. 접근 방식 dp 배열에는 각 계단으로 갈 때 까지의 최대 점수를 저장한다. 예를 들어, 점수가 stairs = [10, 20, 15, 25, 10, 20]인 계단이 존재한다면 dp[1] = 10, dp[2] = 30, dp[3] = 35 ... ... 이렇게 저장하는 것이다. 규칙을 정리해 본다면, n번 째 계단으로 가는 방식은 두 가지 존재한다. dp[n-2] + stairs[n - 1] (두 계단을 오른 경우) dp[n-3] + stairs[n - 2] + stairs[n - 1] (두 계단을 오르고 한 계단을 올랐을 경우) 그리고 우리는 이 두 가지 ..

Algorithm 2023.10.21

[백준] 9095: 1, 2, 3 더하기 - JS (DP)

목 차 문제 접근 방식 풀이 문제 접근 방식 규칙을 먼저 찾아보자. 1의 경우: 1 2의 경우: 2 3의 경우: 4 4의 경우: 7 5의 경우: 13 6의 경우: 24 4의 경우를 살펴보면 앞에 3개를 더한 값이다. 5의 경우도 직전 3개를 더한 값이다. 만약 저 숫자들이 dp 배열에 있다고 한다면, dp[n] = dp[n-1] + dp[n-2] + dp[n-3]이 된다는 의미이다. 반복문의 조건식은 i

Algorithm 2023.10.19

[백준] 1717: 집합의 표현 - JS (Union-Find)

목 차 문제 접근 방식 answer 배열이 필요하다! 풀이 문제 접근 방식 이 문제는 Union-Find / Disjoint-Set문제이다. 이 문제에서는 parent 배열과 rank 배열(최적화), 그리고 *answer 배열(JS만 필요한 듯)이 필요하다. answer 배열이 필요한 이유는 접근 방식 챕터의 가장 마지막에 작성하도록 하겠다. 랭크 시스템을 적용하지 않은 Union-Find 알고리즘은 구현하기 쉬운데 Find와 Union 함수를 구현하면 된다. Find: 숫자를 받아오고 계속 타고 올라간다. 올라가면서 num과 parent[num]이 같지 않다면 가장 조상의 인덱스 번호로 바꿔준다. function find(num){ if(num !== parent[num]){ parent[num] = ..

Algorithm 2023.10.17

[자료구조] Union Find / Disjoint-Set 알고리즘 개념 및 최적화

목 차 Union-Find Algorithm 기본 개념 최적화 Union-Find Algorithm 기본적으로 Union-Find는 자료구조이다. 하지만 이 자료구조를 지원하는 Union과 Find는 알고리즘이다. 여러 노드가 서로 중복되지 않는 집합 여러 개로 나뉘어 있을 때, 각 집합을 대표하는 노드를 찾거나 두 집합을 합치는 연산을 하는 자료구조이다. 기본 개념 1. Union: 두 개의 원소가 포함된 집합을 하나로 합친다. 2. Find: 주어진 원소가 속한 집합의 대표 노드를 반환한다. 최적화 대표적인 최적화는 '경로압축' 인데, 바로 Find 연산을 수행할 때, 방문한 노드를 모두 그 집합의 대표 노드로 바꾸는 것이다. 여기에 'Rank' 시스템을 도입하면 시간 복잡도가 눈에 띄게 줄어드는데,..

Algorithm 2023.10.16

[백준] 1697: 숨바꼭질 - JS (그래프 탐색(DFS&BFS))

목 차 문제 접근 방식 풀이 문제 접근 방식 이번에는 BFS로 풀려고 한다. 구현 전에 설정한 조건은 다음과 같다. 방식: BFS (queue) 이동: -1, +1, *2 방문 체크: push 후 해당 요소를 1로 바꿈 범위: 100000 while문 조건: queue.length queue 에는 [item(이동), time]이 한 노드임 item과 K가 같다면 출력 후 반복문 종료 push 조건 - 1: item - 1 >= 0 && arr[item - 1] == 0 + 1: item + 1

Algorithm 2023.10.12

[Algorithm] 그래프 탐색 알고리즘(DFS, BFS)

목 차 DFS와 BFS 구현 방법 대표 문제 유형 DFS와 BFS DFS: 깊이 우선 탐색, 재귀 함수를 사용하여 구현하는 것이 일반적이다. 재귀를 타고타고 탈출 조건에 도달하고, 그 다음에 파라미터를 하나씩 바꿔 가면서 정답을 찾는 방식. BFS: 너비 우선 탐색, Queue나 LinkedList를 사용하는 것이 일반적이다. DFS와 BFS의 장단점 DFS 장점 현재 경로상의 노드만 기억하므로 적은 메모리를 사용한다. 재귀함수를 사용하여 구현이 BFS 보다 간편하며, 코드 검증이 쉽다. 단점 비효율적인 경로를 탐색하는 경우가 있다. 가장 먼저 찾은 경로가 최단 경로라는 보장이 없다. BFS 장점 시작노드에서 가장 가까운 노드부터 탐색하기 때문에 최단 경로를 보장한다. 단점 모든 노드를 큐에 저장하므로 ..

Algorithm 2023.10.12

[백준] 1463: 1로 만들기 - JS (DP)

목 차 문제 접근 방식 풀이 문제 접근 방식 알고리즘 문제를 풀 때, 1초에 CPU가 계산하는 양은대략적으로 10^6~ 10^8 정도이다. 이 문제에서 입력은 최대 10^6 이므로 시간 복잡도가 O(N)인 알고리즘으로 풀 수 있다는 얘기이다. 나는 이 꼼수?를 이용하여 풀어봤다. dp = [0, 0] 초기 설정을 해주고 for문으로 2부터 10^6 까지 다 dp 배열에 넣어버리는 것이다. for(let i = 2; i

Algorithm 2023.10.05