반응형 알고리즘 썸네일형 리스트형 외적 (CCW 알고리즘) 외적 이 게시글에서는 '기하 알고리즘'에서 이용되는 벡터의 외적 개념에 대해서 간단하게 살펴볼 예정이다. (기본적으로 벡터에 대한 개념이 숙지되어 있어야 이해하기가 쉬울 것 같다....) 외적은 두 벡터에 동시에 수직인 벡터 (이하 수직벡터)를 구하는 연산으로, 기호로는 를 이용한다. 이 때, 두 벡터가 평행하지 않은 경우, 수직벡터는 아래와 같이 두 경우로 나오게 된다. 이는 두 벡터를 연산하는 순서에 따라서 달라지게 되고, 수직벡터는 서로 반대의 방향으로 나타난다. 그러므로 연산 순서에 따라 외적값이 음수 또는 양수로 나타난다. (크기는 같다) 혹시 오른손법칙을 알고 있는 사람이라면, 수직벡터가 어떤 방향으로 나타나는지 쉽게 알 수 있을 것이다. 위의 그림은 a X b 를 구한 경우이다. 즉, a에서.. CCW (Counter-ClockWise) - (1) CCW (Counter-ClockWise) - (1) CCW 알고리즘은 수 계산에서의 사칙연산처럼, '기하 알고리즘'에서 가장 기본적인 알고리즘이다. 즉, 기하 알고리즘에서 매우 자주 이용된다는 뜻이다. 우선 이 게시글에서는 CCW에 대한 소개를 하려고 한다. CCW 알고리즘이란? "평면에 놓여진 세 점의 방향관계를 구하는 알고리즘" 기본적으로 벡터의 외적 개념이 사용되지만 크게 어려운 내용은 아니다. 아래의 그림을 통해서 이해해보자. 이렇게 세 점이 주어져 있는 경우에, 이 세 점이 시계방향인 관계인지, 시계 반대 방향인지, 혹은 평행한 관계인지를 따지는 것이 목표이다. CCW 알고리즘은 시계반대방향일 때 양수, 시계방향일 때 음수, 평행일 때 0을 반환한다. 위의 그림과 같이 A,B,C 순서로 세 점.. 퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort)은 '찰스 앤터니 리차드 호어 (Charles Antony Richard Hoare)가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬하는 "비교 정렬"에 속하며, 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 갖는다. 비교 정렬의 시간복잡도 하한선 : O(nlogn) / 퀵 정렬의 평균 시간복잡도 O(nlogn) (이름 자체에서도 빠르다는 것을 알려주고 있다...) 퀵 정렬 (Quick Sort) 알고리즘의 동작 원리 기준점(pivot)을 설정해 해당 기준으로 분할 i) 리스트 중에서 한 원소를 선택한다. 이렇게 고른 원소를 피벗(Pivot)이라고 한다. (일반적으로는 pivot을 리스트의 가장 앞의 원소 혹은 가.. 셸 정렬 (Shell Sort) 셸 정렬 (Shell Sort) 셸 정렬 (Shell Sort)에 대해서는 학교 수업시간에 학습한 개념이지만, 겉핥기 식으로만 학습하였고, 또 백준 알고리즘 문제를 해결하다보니 기존에 학습한 기본적인 정렬 (삽입, 선택, 버블)로는 대부분 시간초과로 통과하지 못하였기에 더 빠른 정렬을 이용하고자 다시 제대로 학습하게 되었다. 우선 셸 정렬 (Shell Sort)는 1959년, 이 방법을 고안한 "도널드 셸"의 이름을 따서 붙여졌고, 기존의 삽입 정렬(Insertion Sort)의 단점을 보완하고자 개발되었다. 1. 정렬이 하나도 되어 있지 않은 경우 매우 비효율적 2. 삽입되어야 할 위치가 멀리 있다면 원소들의 많은 이동을 해야만 삽입 가능 (삽입 정렬 Review) 주어진 배열에서 모든 요소를 앞에서부.. [BOJ 2399] 거리의 차이 2399번 (거리의 차이) 이 문제는 단순히 이중 반복문을 이용하여 (x[0] ,x[0]~x[n]) , (x[1], x[0]~x[n]), ... (x[n], x[0]~x[n]) 이렇게 총 n^2개의 모든 쌍을 구하는 방식으로 구할 수 있다. 하지만 이 방식은 시간복잡도가 O(n^2)이기 때문에 n이 커지면 시간이 오래 걸리게 되고, 또 이 문제의 분류가 "정렬" 이기 때문에 정렬을 이용하여 문제를 풀어보았다. 정렬을 이용한 풀이에는 아주 유용한 "수학적인 아이디어"가 이용된다. 1. 우선 정렬을 통해서 n개의 점을 좌표가 오름차순이 되도록 정렬을 한다. 2. 특정한 x[i]를 생각해보면, 모든 n^2개의 쌍 중에서, x[i]는 총 2n번 등장하게 된다. (x[1] ~ x[n] , x[i]) : n개 / .. 이전 1 ··· 4 5 6 7 다음
