반응형 알고리즘 썸네일형 리스트형 [BOJ 1992] 쿼드트리 1992번 (쿼드트리) 위와 같이 문제가 주어져 있다. 주어진 크기 안의 숫자가 모두 0이거나 모두 1이어야 하고, 만약 이를 만족하지 않는다면 다시 사각형을 4등분하기 때문에 재귀함수를 이용해야 한다는 생각을 할 수 있다. 따라서 분할정복으로 아래와 같이 코드를 작성하면 된다. quadtree라는 재귀함수를 작성하여, 해당 사각형내의 숫자가 모두 같은 경우에는 그 숫자를 출력하고, 같지 않다면 ( 괄호를 출력하고, 4등분한 사각형에 각각 재귀함수를 호출해준다. 볼록 껍질 (Convex Hull) 볼록 껍질 (Convex Hull) 볼록 껍질이란? "2차원 평면 상에서 주어진 점들을 모두 포함하는 가장 작은 다각형" (이 때, 다각형의 각 변들은 주어진 점을 양 끝점으로 갖는다) 기하 알고리즘에서 볼록 껍질이 자주 응용되기 때문에 중요한 알고리즘이다. 볼록 껍질을 구하는 데에는 '그라함 스캔 알고리즘(Graham's Scan Algorithm)'이 이용된다. 볼록 껍질 (Convex Hull) 구하는 과정은 다음과 같다. 1. 주어진 점들 중 y좌표가 가장 작거나 혹은 y좌표가 가장 작은 점이 둘 이상이라면 x좌표가 가장 작은 점을 선택 2. 선택한 점을 기준으로 나머지 점들을 반시계 방향으로 정렬 (각을 이용) 3. 그라함 스캔 알고리즘.. [BOJ 2166] 다각형의 면적 2166번 (다각형의 면적) CCW 알고리즘을 이용하여 다각형의 꼭짓점만으로 다각형의 면적을 구하는 문제이다. 코드의 자세한 원리는 CCW(Counter-ClockWise) - (2) 게시글 (https://wogud6792.tistory.com/12) 에서 확인할 수 있다. 주어지는 점들의 좌표가 모두 정수인데 왜 실수로 출력하라는지 정확히는 모르겠지만.. 이것때문에 꽤나 애를 먹었다. 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) 주어진 배열에서 모든 요소를 앞에서부.. 이전 1 ··· 3 4 5 6 7 다음
