반응형 전체 썸네일형 리스트형 퀵 정렬 (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개 / .. [BOJ 11051] 이항 계수 2 11051번 (이항 계수 2) Try 1) 단순히 이항 계수의 식인 nCk = n! / k!(n-k)! 을 이용하여 해결하기 (idea) N과 K를 입력받았을 때, 1부터 N까지 곱하고, 그 후 1 ~ K까지 나누고, 1 ~ N-K까지 나눈다. 하지만 이 경우, 가장 큰 범위의 정수형 타입인 long long 타입이라고 하더라도, N이 큰 수면 오버플로우(Overflow)가 발생해서 정확한 수가 저장 되지 않는다. 따라서, 이 방법은 올바른 답을 도출해낼 수 없다. Try 2) 이항 계수 공식 nCk = n-1Ck-1 + n-1Ck 을 이용하고, Try 1)의 문제점을 해결하기 위해 (a+b)%mod = a%mod + b%mod 성질 이용하기. (idea) 이항 계수 공식인 nCk = n-1Ck-1 + .. 메모이제이션 (Memoization) 메모이제이션 (Memoization) 이 알고리즘에 대해서는 백준 알고리즘 11051번 (이항 계수 2) 문제를 통해서 학습하게 되었다. 메모이제이션은 동적 계획법 (Dynamic programming)의 핵심 기술이다. (동적 계획법에 대한 설명은 따로 정리를 할 예정이므로 이 게시물에서 개념에 대한 설명은 간단하게 한다.) 우선 해당 문제에 대해서 한번 살펴보자. 다음과 같이 문제가 주어져 있다. 즉, 예를 들어 입력으로 5 2를 입력하게 되면, 10이 출력되어야 한다. 이 알고리즘에 대해 알지 못하거나 익숙하지 않은 사람들은 필자를 포함하여 대부분 위의 식을 이용해서 풀었을 것이다. 즉, 만약 "10 5" 가 입력되었다면, (N = 10, K = 5) 1부터 10까지 곱한 후, 다시 1부터 5까지 .. 시작 블로그의 시작을 알리는 글이다. 사실 개인 사이트나 블로그를 운영해본적이 없어 이렇게 글 쓰는 것이 되게 어색하다 시작하게 된 계기는 블로그의 이름에서도 알 수 있듯이 코딩과 관련된 공부나 일들을 했을 때"일기장"처럼 기록을 해두기 위함이다. 그 동안 나름 학교 공부를 통해서 2년간 컴퓨터공학 또는 코딩에 대한 지식을 많이 학습한 것 같지만, 정작 머리속에 남아있는게 많지 않고 또 무엇을 배웠는지 정확하게 말할 자신이 없다. 특히 코딩의 특성상 아주 참신한 아이디어나 알고리즘을 통해서, 수 많은 시도를 통해서 만든 코드라 할지라도,따로 저장해두지 않았다면 후에 아무 소용이 없었다. 또한, 내가 코딩과 관련된 공부를 할 때 검색이 필요하면, 거의 항상 구글링을 통해서 검색을 하는데, 한글로 아주 잘 설명된.. 이전 1 ··· 20 21 22 23 다음
