반응형 알고리즘 썸네일형 리스트형 CCW (Counter-ClockWise) - (2) CCW (Counter-ClockWise) - (2) 이전 게시글 (CCW (Counter-ClockWise) https://wogud6792.tistory.com/10) 이번 게시글에서는 CCW알고리즘이 어떻게 이용되는지를 알아볼 것이다. 우선 CCW 알고리즘 코드는 다음과 같다. 소개할 내용은 아래와 같이 총 3가지이다. 1. 두 선분의 교차 여부 2. 다각형의 넓이 3. 볼록 껍질 (Convex Hull) 이 중에서 3. 볼록 껍질은 기하 알고리즘에서 중요한 파트이므로 별도의 게시글로 작성할 예정이다. 1. 두 선분의 교차 여부 평면상에서 어떤 두 선분이 주어졌을 때, 이 두 선분이 교차하고 있는지를 어떻게 판단할까? 이는 CCW알고리즘을 이용하면 매우 쉽게 판단할 수 있다. 위의 그림과 같이 선분.. 외적 (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) 주어진 배열에서 모든 요소를 앞에서부.. 메모이제이션 (Memoization) 메모이제이션 (Memoization) 이 알고리즘에 대해서는 백준 알고리즘 11051번 (이항 계수 2) 문제를 통해서 학습하게 되었다. 메모이제이션은 동적 계획법 (Dynamic programming)의 핵심 기술이다. (동적 계획법에 대한 설명은 따로 정리를 할 예정이므로 이 게시물에서 개념에 대한 설명은 간단하게 한다.) 우선 해당 문제에 대해서 한번 살펴보자. 다음과 같이 문제가 주어져 있다. 즉, 예를 들어 입력으로 5 2를 입력하게 되면, 10이 출력되어야 한다. 이 알고리즘에 대해 알지 못하거나 익숙하지 않은 사람들은 필자를 포함하여 대부분 위의 식을 이용해서 풀었을 것이다. 즉, 만약 "10 5" 가 입력되었다면, (N = 10, K = 5) 1부터 10까지 곱한 후, 다시 1부터 5까지 .. 이전 1 2 3 다음
