자료알고/알고리즘 검색 결과
오늘도 어김없이 신기한 정렬을 들고 왔습니다. 바로 바이토닉 정렬입니다. bitonic sort라고도 하는데요. 증가했다, 감소하거나, 감소하거나 증가하는 수열을 우리는 바이토닉 수열이라고 합니다. 말로 설명하면 쉽지 않으니, 간단하게 n = 8 데이터를 가지고 sort를 해 봅시다. 먼저 다음과 같은 배열이 있다고 가정해 봅시다. 이것을 우리는 오름차순으로 정렬해야 합니다. 어떻게 하면 좋을까요? 일단, 초록색, 보라색, 노란색, 하늘색 순서대로 칠해 봅시다. 이들은 1칸 차이이기 때문에 서로 인접해 있습니다. 이제 우리는 어떻게 할 것이냐면, 초록색은 증가, 보라색은 감소, 노란색은 증가, 하늘색은 감소가 되게 할 거에요. 그러면 이렇게 될 겁니다. 1회전이 끝났습니다. 이제 2회전을 돌려 봅시다. ..
저번 시간에는 그리디 알고리즘의 기초 문제를 다루어 보았습니다. 오늘은 피보나치 수열을 해 보도록 하겠습니다. 이 친구를 언급하기 전에, 일반항을 먼저 구해보도록 하겠습니다. 왜냐하면, 오늘 하는 내용과, 어느 정도 맞아 떨어지기 때문이에요. 먼저 피보나치 수열은 아래와 같은 관계식을 가집니다. a(0) = a(1) = 1 a(n) = a(n-1) + a(n-2) if n>=2 여기까지만 보면 크게 어려울 건 없어 보입니다. 그러면 어떻게 일반항을 구할까요? 2번째 식을 잘 변형해 봅시다. a(n) - a(n-1) - a(n-2) = 0 그러면 위와 같이 되는데요. 이를 (3)이라 합시다. 아래 꼴로 변형해 봅시다. 이걸 (4)라고 합시다. a(n) - ta(n-1) = k(a(n-1) - ta(n-2)..
greedy는, 욕심쟁이라는 뜻입니다. 이름에 걸맞게, 매 순간 제일 매력적인 해를 택하는 방법입니다. 그런데 그게 best한 답일까요? 답은 그럴 수도 있고 아닐 수도 있다는 것입니다. 오늘은 이러한 approach로 풀 수 있는 문제 중에서 쉬운 문제만 소개해 드리도록 하겠습니다. 작업 n개가 주어집니다. 이들을 끝내는 데 걸리는 시간이 있습니다. 각각 T(1), ... ,T(n)이라고 합시다. 우리는 제한시간 limit 내에 최대한 많은 작업을 끝내려고 합니다. 어떻게 하면 좋을까요? 직관적으로 생각했을 때, 선택하지 않은 작업들 중에서, 소요 시간이 제일 짧은 작업들을 매 순간마다 선택하면 될 거 같습니다. 그러면 T 배열을 정렬하면 될 겁니다. 예를 들어 T = [2, 5, 1, 3, 7] 이라..
삽입 정렬의 복잡도는 O(n^2)입니다. 물론 평균 복잡도 또한 O(n^2)입니다. 물론, memcpy 등으로 실행 시간을 빠르게 할 수 있는 여지는 있지만, 거기까지일 뿐입니다. 다만, insertion sort의 장점도 있는데요. 거의 정렬된 데이터에 대해서는 상당히 빠르게 동작한다는 장점이 있어요. 하지만, 한 번에 한 요소씩. 비교 1번 할 때 마다, 1요소씩만 move 하기 때문에 효율적이지 않은데요. 이를 보완하기 위해서 gap이라는 변수를 둡니다. 그러면 먼저 init 함수를 봅시다. 먼저, si 라는 벡터가 있습니다. 여기에 무슨 값들이 들어있는지 봅시다. 1, 4, 13, 40, 121, 361, 1093, 3280, ... 네. 이런 값들이 들어 있는데요. gap으로 쓸 겁니다. 예를 ..
최근댓글