[자료구조] 펜윅 트리 (Fenwick Tree) - Binary Indexed Tree

목 차 펜윅 트리(Fenwick Tree) 펜윅 트리와 세그먼트 트리 펜윅 트리를 구현하며 배운 것들 구현 방법 펜윅 트리(Fenwick Tree) Binary Indexed Tree 라고도 불리는 펜윅트리는 수열의 특정 구간의 합을 빠르게 계산하고, 요소를 빠르게 변경 할 수 있는 자료구조 이다. 특징 시간 복잡도: update 와 sum 메서드 모두 O(log n)의 시간 복잡도를 가진다. 공간 복잡도: O(n) 만큼의 공간을 사용한다. 작동 원리 SUM 함수: 구간 합을 구하는 함수 UPDATE 함수: 특정 요소가 변경되면 그 요소에 영향을 받는 인덱스를 타고 올라가며 변경한다. 펜윅 트리와 세그먼트 트리 세그먼트 트리 펜윅 트리 구조 이진 트리 기반 배열 기반 시간 복잡도 업데이트 & 구간 합 모..

Algorithm 2023.12.06

[알고리즘] 위상 정렬 (Topology Sort)

목 차 위상정렬(Topological Sorting) 기본 개념 및 조건 위상정렬을 구현하며 배운 것들 구현 방법 위상정렬(Topological Sorting) 위상정렬은 방향이 있는 그래프에서 유효하다. 예를 들면, 여러 작업이 서로 의존 관계를 가질 때, 어떤 순서로 작업을 진행해야 하는지를 결정할 때 유용하다. 위상정렬은 결과가 매 번 다를 수 있다. 예를 들면, 4는 2의 앞에 있어야 하고, 3은 1의 앞에 있어야 한다고 가정할 때 예상되는 경우의 수는 4231, 4321, 4312 등 여러 개가 될 수 있다. 기본 개념 및 조건 방향성 그래프: 각 간선에 방향이 있는 그래프여야 한다. 단방향 그래프: 각 간선에 방향이 있되 양방향이지 않아야 한다. 위상정렬을 구현하며 배운 것들 최적화 전 더보기..

Algorithm 2023.11.29

[자료구조] 세그먼트 트리 (Segment Tree)

목 차 세그먼트 트리 개념 세그먼트 트리를 하며 배운 것들 세그먼트 트리 코드 세그먼트 트리 개념 세그먼트 트리는 구간 쿼리와 업데이트를 최적으로 수행할 수 있는 유연한 자료구조이다. 주로 구간 합, 또는 구간 내 최솟값이나 최댓값을 찾는 문제에 사용된다. 기본 구조 트리 구조: 세그먼트 트리는 이진 트리 구조이며, 각 노드는 배열의 특정 구간(Segment)을 대표한다. 리프 노드: 트리 구조에서 자식 노드가 없는 노드를 말한다. 즉 트리 가장 아래에 위치한 노드들을 말한다. 내부 노드: 자식 노드들의 값을 합치거나 비교하여 해당 구간의 값을 저장한 노드들을 말한다. 작동 원리 트리 초기화: 주어진 배열로 완전 이진 트리를 만든다. O(N) SUM함수: 구간합을 구하는 함수 O(log N) UPDATE..

Algorithm 2023.11.21

[알고리즘] 다익스트라(Dijkstra algorithm)와 우선순위 큐(MinHeap)

목 차 최소 힙 (MinHeap) 다익스트라 알고리즘 기본 개념 다익스트라 알고리즘 구현 최소 힙 (MinHeap) 다익스트라 알고리즘은 우선순위 큐(MinHeap)를 사용하는 것이 일반적이다. 최소 힙(MinHeap)의 정의 최소힙은 부모 노드가 자식 노드 보다 작거나 같은 값을 가지고 있는 이진 트리이다. 힙의 루트에는 트리에서 가장 작은 값이 위치한다. 최소 힙(MinHeap)의 연산 - 삽입: 새로운 요소를 힙의 마지막에 추가한 후, 부모 노드와 비교하며 위치를 조정하여 힙 속성을 만족시킨다. - 추출: 힙의 루트노드를 제거하고 마지막 노드를 루트로 이동시킨 다음, 자식들과 비교하며 위치를 조정하여 힙 속성을 만족시킨다. 여기서 추출할 때 JS 기준으로 shift() 메서드를 사용하면 앞에 노드를..

Algorithm 2023.11.14

[자료구조] 우선순위 큐(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

[백준] 1644: 소수의 연속합 - JS(투포인터)

목 차 문제 접근 방식 풀이 문제 단, 20은 0인데, 20은 소수가 아니기 때문에 0이 나와야 한다. 접근 방식 2~N까지의 소수를 모두 구해야 하기 때문에 이전에 '소수 구하기'에서 구현했던 코드를 가져와 M부터 N 이였던 것을 처음부터 N 까지로 변경했다. 그리고 이 문제를 읽으면서 두 포인터 기법을 사용해야 겠다고 생각했다. 먼저 소수를 배열에 넣는다. 그리고 start와 end가 있는데 먼저 가장 첫 번째 요소를 가리키게 해 준다. 만약 N과 같거나 작다면 end를 하나 올려준다. start와 end가 1 이상 차이 나게 되면 그 요소들을 더해준다. 그리고 똑같이 N과 같거나 작다면 end를 하나 올려주고, N 보다 크다면 start를 하나 올려주어 결과적으로 맨 앞에 있는 요소를 빼는 역할을 ..

Algorithm 2023.09.30

[백준] 1929: 소수 구하기 - JS (에라토스테네스의 체)

목 차 문제 접근 방식 풀이 문제 접근 방식 에라토스테네스의 체 알고리즘은 큰 범위 내에 있는 모든 소수를 빠르게 찾을 때 효율적이다. 기본 원리는 다음과 같다. - 2부터 원하는 숫자 N 까지의 모든 숫자를 나열한다. - 2는 소수이므로, 2의 배수를 모두 제거한다. - 다음 남아있는 숫자인 3의 배수를 모두 제거한다. - 다음 남아있는 숫자인 5의 배수를 모두 제거한다. - 다음 남아있는 숫자인 7의 배수를 모두 제거한다. - 다음 남아있는 숫자인 ... ... 이런 방식으로 N 까지 한다. 남아 있는 숫자들이 2 부터 N 까지의 소수이다. 그리고 다른 방식은 숫자 N을 2 부터 루트N 까지 나누어 보는 것이다. 이 두 방식의 차이점은 메모리 제한, 시간 복잡도 이다. 에라토스테네스의 체 알고리즘은 ..

Algorithm 2023.09.30

[백준] 1654: 랜선 자르기 - JS (이분 탐색)

목 차 문제 접근 방식 풀이 문제 예시로 const 랜선: number[] = [802, 743, 457, 539] 이렇게 랜선 4개가 있다면 여기서 랜선 11개를 가져가야 할 때 최대로 자를 수 있는 길이를 구하라는 것이다. 접근 방식 일단 나무 자르기와 비슷한 방식으로 접근하기로 했다. 아래는 코드 설계 전 내가 설계할 코드의 큰 틀을 설계한 것들이다. 최댓값 = max 최솟값 = min 반 값 = half for문: 전체적인 계산 처리를 하는 코드 result = for문에서 계산된 결과가 N과 같다면 result 변수에 저장한다. 단, result 변수의 초기값은 0으로 시작하고, 최대의 값을 구해야 하므로 result의 값 보다 큰 경우 갱신하도록 한다. 풀이 tamp >= N 일 때 resul..

Algorithm 2023.09.05

[백준] 2805: 나무 자르기 - JS (이분 탐색)

목 차 문제 접근 방식 풀이 문제 나무의 수 N과 필요한 나무의 길이 M이 주어진다. 두 번째 줄에는 나무의 높이가 주어진다. ex) [20, 15, 10, 17] 접근 방식 아직 퀵 정렬을 배우지 않은 초보개발자로, 미비한 점이 많을 것이다. 나중에 되돌아보며 더 나은 코드로 수정할 예정이다. 먼저 나는 재귀 함수를 사용하기 보다는 그냥 변수에 할당해서 사용하기로 했다. (메모리 문제) 전체적인 풀이 방법은 단순하다. 값을 할당할 변수를 선언하고, 최대한 반복을 하지않기 위해 가장 큰 값을 highest 변수에 할당하고 계속 업데이트 해주려고 한다. 그리고 H 값은 커터의 높이이므로 퀵 서치 방식으로 한다. 디버깅을 하다가 보니 저 종료 조건에서 for문이 제대로 작동하지 않는 현상을 발견했다. 그래서..

Algorithm 2023.09.03