[알고리즘] CounterClockWise(CCW)

목 차CCW 개요CCW의 기본 원리BOJ - CCW 알고리즘 문제 풀이CCW를 활용한 알고리즘 문제 CCW 개요 CCW 알고리즘은 주어진 점들이 시계 반대 방향으로 정렬이 되어 있는지를 판단하는 알고리즘이다. 이 방법은 기하학적 알고리즘에서 중요한 역할을 하는데, 예를 들면, A, B, C가 순서대로 주어졌을 때 선분AB에 대해서 C가 시계 반대 방향에 위치해 있는지, 시계 방향인지, 아니면 같은 선상에 있는지를 판별하는 방법이다. CCW의 기본 원리 벡터의 외적을 사용해서 외적의 결과가 양수일 경우는 반시계, 음수일 경우 시계 방향에 있다는 의미이다. 외적 공식은 다음과 같다. BOJ - CCW 알고리즘 문제 풀이: 11758 CCW는 공식만 알면 굉장히 쉽기 때문에 CCW 자체는 어렵지 않다. let..

Algorithm/Concept 2023.12.14

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

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

Algorithm/Data Structure 2023.12.06

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

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

Algorithm/Data Structure 2023.10.26

[백준] 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/BackJun 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/BackJun 2023.10.17

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

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

Algorithm/Data Structure 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/BackJun 2023.10.12

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

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

Algorithm/Concept 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/BackJun 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/BackJun 2023.09.30

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

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

Algorithm/BackJun 2023.09.03

[백준] 2748: 피보나치 수 2 - JS (재귀, DP)

목 차 문제 접근 방식 풀이 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 접근 방식 이 문제는 대표적인 DP 문제이다. 그냥 재귀함수를 통해서 문제를 푼다면 시간이 초과되어 실패할 것이다. >> DP란? 백준에서 입력은 첫째 줄에 n이 주어진다. n은 90보다 작거..

Algorithm/BackJun 2023.07.30

[Algorithm] 다이나믹 프로그래밍(DP) 개념 및 적용

목 차 개요 DP를 사용하는 이유 DP 적용하기 DP 체감하기 개요 Dynamic Programmin(DP) 또는 동적 프로그래밍이라고도 하는데, DP는 복잡한 문제를 간단한 여러개의 문제로 나눠서 푸는 방식이다. DP는 작은 문제가 반복하여 발생하고 이에 대한 해답을 저장해두고 재사용 하는 특징이 있다. 이렇게 함으로써 계산 속도를 크게 향상시킬 수 있다. DP를 사용하는 이유 DP는 주로 다음 두 가지 속성을 가진 문제에 적용된다. 1. 중복되는 문제 해결: 대표적으로 피보나치 수열의 예시가 있는데, 이 피보나치 수열을 재귀함수로 풀어본다면 코드는 아래 코드와 비슷할 것이다. Fn 을 계산하기 위해서 F(n-1) 과 F(n-2)을 계산해야 하지만, 이들 역시 F(n-3)과 F(n-4)를 필요로 한다...

Algorithm/Concept 2023.07.29