오늘은 선택 정렬 알고리즘에 대해 공부해 봅시다. selection sort는 매 회전마다, 제일 우선 순위가 높은 값을 선택해서 재정렬 하는 알고리즘입니다. 배열 arr의 크기가 n이라고 해 봅시다. 그러면 총 n회전을 돌 건데요. i회전일 때 이러한 일을 수행합니다. 구간 [i,n]에서 우선순위가 가장 높은 위치 lo를 찾습니다. 그리고 배열에서 i번째 원소와 lo번째에 있는 값을 맞바꿉니다. 구간 [i,n]은 정렬이 되어 있지 않기 때문에, 우선 순위가 가장 높은 값과 위치를 찾기 위해서, i에서부터 n까지 보아야 합니다. 그러므로, 회전마다 O(n-i)만큼 걸리게 되고, 결과적으로 시간 복잡도는 O(n^2)가 됩니다. 매 회전마다, O(log(n)) 급에 해결할 수 있는 방법이 있는데, 특수한 자..
자료알고/알고리즘 검색 결과
stable sort는, 정렬 알고리즘을 논할 때 간과하고 넘어가기 쉬운 키워드입니다. 하지만, 간과해서는 안 되는 것입니다. 이것이 대체 무엇을 의미할까요? 우선순위가 같은 데이터가 여러 개 있을 때, 정렬이 끝난 후에도, 순서가 유지되는 정렬을 stable sort라 합니다. 그렇지 않다면 unstable하다고 합니다. 예제를 하나 봅시다. n개의 데이터를 정렬한다고 해 봅시다. 매 회전마다 [i,e] 구간에 있는 원소들을 탐색해서, 가장 우선순위가 높은 원소가 있었던 위치를 lo라고 해 봅시다. 이 때 lo와 i에 있는 원소를 뒤바꾸는 정렬이 있다고 해 봅시다. 위에 있는 숫자는 숫자, 밑에 있는 숫자는 정렬 전 위치라고 해 봅시다. 만약에 숫자를 오름차순 정렬한다고 하면, 1이 0보다는 우선 순위..
정렬 알고리즘 시리즈를 쓰려고 합니다. 총 20 ~ 25편 정도로 구성이 될 듯 싶습니다. 먼저 O(n^2)짜리 알고리즘 3대장을 써 볼 건데요. 아마도, 알고리즘 교재에서는 맨 처음에 나올 듯 싶습니다. 오늘은 그 중, 삽입 정렬에 대해서 알아보겠습니다. 이 글을 이해하기 위해서는 memcpy와 memmove를 이해하면 더없이 좋을 겁니다. [관련글] 메모리 복사 함수는 어떻게 쓸까요? 삽입정렬 알고리즘은 Loop를 돌면서 해당 원소가 이미 정렬된 부분 배열에서 어디로 들어가면 좋은지를 구한 다음에, 그 위치에 넣는 식으로 동작합니다. [6, 3, 4, 2, 1, 3]을 오름차순으로 정렬한다고 해 봅시다. 수가 작을수록 우선 순위가 높을 겁니다. 먼저 1회전을 돌 겁니다. 6을 선택합니다. 제가 파란색..
생각난 김에, 간단하게 글을 써 보도록 하겠습니다. 수학 시간에 대우 명제를 써서 증명하는 것은 많이 해 보셨을 겁니다. 이런 걸 대체 ps 문제를 푸는 데 어떻게 쓰는 걸까요? 백준 12858번은 문제가 짧습니다. 구간 s에서 e까지의 수를 t로 바꾼다. 그리고 구간 s에서 e까지 최대 공약수를 구한다. 생각보다 문제에서 요구하는 것은 많지 않습니다. 그러면 이걸 어떻게 풀어야 할까요? 명제 p이면 q이다가 있다고 해 봅시다. 그러면 not Q이면 not P이다 또한 참입니다. ~not P는 ~not Q와 빨간색으로 칠한 부분을 합친 것이기 때문입니다. 보통 P이면 Q다. 라는 명제를 증명하기 어렵지만, ~Q이면 ~P이다를 증명하기가 상대적으로 쉬울 때, 대우 명제를 끌어와서 증명을 많이 합니다. 12..
12번째 글은, 냅색 알고리즘 문제입니다. 이것도 꽤 여러 종류가 있는데요. 쪼갤 수 있는 물건이냐, 그렇지 못하냐에 따라서, 그리디로 접근을 할 수 있는지, 아니면 dp로 접근해야 하는지가 나뉩니다. 저는 0/1 냅색 문제를 다뤄 보겠습니다. 이것은 물건을 쪼갤 수 없어요. 물건이 n개가 있습니다. 그리고 가방에 넣을 수 있는 무게는 W입니다. 이 때, 가방에 넣을 수 있는 물건들의 최대 이익은 얼마나 될까요? 먼저 기저 조건을 생각해 봅시다. 물건 0개를 넣었을 때, 가방에 넣은 물건의 총 무게는 0, 이익 또한 0일 겁니다. 따라서, dp[0개][용량 0]을 넣었을 때 값은 0입니다. 대충 이런 경우입니다. 만약에 물건 0개를 넣었는데, 가방에 넣은 물건의 총 무게가 x(x>0)라면 이건 어떨까요?..
최근댓글