[알고리즘] 퀵 정렬 (Quick Sort)

목 차 퀵 정렬(Quick Sort) 기본 개념 퀵 정렬을 구현하며 배운 것들 구현 방법 퀵 정렬(Quick Sort) 기본 개념 퀵 정렬은 분할 정복 전략(Divide and Conquer)을 사용한다. 평균 O(n log n)의 시간 복잡도를 가지고, 최악의 경우(정렬된 배열) O(n^2)의 시간 복잡도를 가진다. pivot 을 먼저 선택하고 그 pivot을 기준으로 더 큰 값과 더 작은 값을 분류한다. 이 것을 '파티셔닝'이라고 하며, 재귀적으로 정렬을 한다. pivot 의 중요성 퀵 정렬에서 pivot 은 시간 복잡도에 큰 영향을 끼친다. 일반적으로 첫 번째 인덱스, 중간 인덱스, 마지막 인덱스를 pivot 으로 설정한다. 퀵 정렬을 구현하며 배운 것들 내가 알고 있던 개념들을 사용하였기에 기술적..

Algorithm 2023.12.26

[알고리즘] CounterClockWise(CCW)

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

Algorithm 2023.12.14

[백준] 2042: 구간 합 구하기 - JS (펜윅트리(BIT))

목 차 문제 접근 방식 풀이 문제 접근 방식 펜윅 트리는 구간 합을 구하는 것에 특화되어 있는 자료구조 이다. 펜윅 트리를 구성하는 메서드는 update 와 sum 메서드 이다. update // x: 업데이트 하는 인덱스, diff: 원래 값과 바뀐 값의 차이 인자: x, diff 조건: x 0 동작: 인자로 들어온 x 에서 x & -x 를 빼주고 반복하면 1 부터 x 까지의 합을 구할 수 있다. 구간 합은 sum(b) - sum(a - 1) 을 해주면 구할 수 있다. 세그먼트 트리 보다는 구현이 쉬웠는데 범용성이 아쉽다. 구간 합 문제에서 편하게 사용할 수 있을 것 같다. 펜윅 트리를 구현하며 배운 것들 펜윅 트리를 위한 글에서 캡쳐하였다. 풀이 class FenwickTree { // N: 요소 개..

Algorithm 2023.12.07

[백준] 2042: 구간 합 구하기 - JS (세그먼트 트리)

목 차 문제 접근 방식 풀이 문제 접근 방식 세그먼트 트리를 구성하는 3가지 메서드는 initTree, update, sum 메서드이다. initTree 메서드: for문을 사용해서 구현했다. 아직 재귀를 사용하기보다는 for 반복문이 더 편하기 때문이다. 트리를 처음에 초기화 하는 메서드이다. 원본 배열을 가져와서 마지막 레벨 트리에 붙여 넣고, 그리고 하나씩 내려가며 자식들을 더한 값을 저장한다. update 메서드: 변경 된 리프노드를 시작으로 부모를 타고 올라가며 전체적인 트리를 업데이트한다. 세그먼트 트리에서 가장 간단하게 구현할 수 있는 메서드라고 생각한다. sum 메서드: 구간 합을 구하는 메서드이다. 재귀를 이용해서 구현한다. sum 메서드를 구현할 때 참고하면 좋은 3가지가 있다. 구해야..

Algorithm 2023.12.07

[자료구조] 펜윅 트리 (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