hisLibrary

퀵 정렬 이번 글에서는 퀵 정렬에 대해서 알아 봅시다. 앞서 우리는 병합 정렬에 대해서 공부했다. (http://history1994.tistory.com/28?category=670299) 퀵 정렬은 이와 비슷하면서 다르다 한 번 살펴보면 Divide , Conquer 과정에서 이미 정렬 되어져 생기기 때문에 따로 Combine 과정은 필요로 하지 않는다.그리고 PARTITION 과정을 통해 DIVIDE 과정을 수행하게 된다.즉, 이러한 순서대로 퀵 정렬은 이루어진다. PARTITION 과정부터 한번 살펴 보자. PARTITION과정으로 인해 부분 배열로 재구성 되어지고 'PIVOT' 이라는 인덱스가 리턴 되어진다.과정을 보면 이러한 과정을 거치게 된다.이를 예로 들자면 a ~ i 과정을 거쳐 pivo..

알고리즘 2018. 10. 7. 16:47

힙 정렬 (Heap Sort) 오늘은 힙 정렬이라는것을 한번 공부 해보자 힙 정렬은 우선순위에 따라 접근해야하면 정렬된 구조를 이룰때 사용하는 자료구조입니다.힙은 한노드가 최대 두 개의 자식노드를 가지면서, 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉채워진 완전 이진트리를 기본으로 합니다. 힙 정렬을 이해하기 위해 먼저 트리의 구조를 알아야 할 필요가 있습니다. Perfect Binary Tree(포화 이진 트리) , Complete Binary Tree (완전 이진 트리) 이 두 구조를 먼저 잠깐 보고 갑시다. Perfect Binary Tree 먼저 h는 해당 트리의 높이를 의미한다. 포화 이진 트리는 h-1 이하 레벨에서 2개의 자식노드를 가지고 있다. Complete Binary Tree 완전..

알고리즘 2018. 9. 22. 13:45

알고리즘의 분할과 정복 과정 이전 공부에서 보면 알고리즘의 분할과 정복 과정을 알아봤다 정리 하자면 분할 - 현재의 문제와 동일하되 입력의 크기가 더 작은 다수의 부분 문제로 분할한다. 정복 - 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다. 결합 - 부분 문제의 해를 결합해 원래 문제의 해가 되도록 만든다. 이러한 재귀 과정을 '바닥을 쳤다'라고 표현하는 베이스 케이스까지 내려올 때까지 과정을 거친다. 이러한 형태는 이전의 계산된결과를 이용하여 현재 계산을 푼다는 점이 있다. 이번에는 이러한 재귀과정을 해결하는 방법에 대해 알아보자. 방법에는 들이 있다 차례대로 치환법 - 한계를 추측한 후 그 추측이 옳음을 증명하기 위해 수학적 귀납법을 이용한다. 재..

알고리즘 2018. 9. 10. 17:44

1. 알고리즘의 점근적 효율성 알고리즘의 효율성에 대해 체크 할때는 충분히 큰 입력들에 대한 수행시간 증가에 있어 가장 큰 차수만 중요하게 취급한다. 즉, 입력 크기가 극한으로 증가할 때 어떤 알고리즘의 수행시간이 어떻게 증가하는지에 관심을 가진다. 이를 점근 표기법 이라고 한다 2. 빅오 - O g(n)은 f(n)에 대한 상한을 뜻한다. 즉 , 시간 복잡도가 최악의 경우더라도 f(n)의 계산 복잡도는 g(n)과 같거나 작다는 것인데 여기서 조건이 있다. 빅오 O(g(n))에 있어 0 ≤ f(n) ≤cg(n) for all n>n0 을성립해야 한다. 여기서 C는 양의 상수이며 n0는 1 이상 자연수 이어야한다. 간단한 예를 들면f(n)=n2 - 2ng(n)=n20≤ n2 - 2n ≤cn2 (n>n0)여기..

알고리즘 2018. 9. 7. 19:30

그림 출처: https://www.inflearn.com 알고리즘은 간단히 말해 어떤 값이나 값의 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는 잘 정의된 계산 절차를 말한다. 그리고 모든 입력 사례에 대해 항상 올바른 출력을 내고 종료할 경우 이를 '타당하다'고 하며 , 그 타당한 알고리즘이 주어진 계산 문제를 푼다고 말한다. 지금 부터 이러한 알고리즘에 대해서 간단한 예를 설명 하겠습니다. 2. 정렬 2.1) 삽입 정렬 하나의 storage에 비교할 값을 넣고 바로 전 인덱스 부터 대소를 비교하며 차례대로 이동하는 형식이다. 따라서 기준점(*)을 기준으로 왼쪽은 정렬이 되어져 있고 오른쪽은 정렬되지 않았다. 의사코드를 보면 이러한 값이 된다. 여기서 잠깐 이 의사코드가 맞는지 확인 하기 ..

알고리즘 2018. 9. 1. 20:18

오늘은 달팽이 알고리즘을 작성 해보겠다. 절차를 먼저 설명 하자면 먼저 값을 입력 받는다. 이 후 그 값에 해당하는 결과물이 출력되야한다. 예를 들면 정수 입력 : 3 1 2 0 3정수 입력 : 15 1 2 3 4 12 13 14 5 11 0 15 6 10 9 8 7 정수 입력 : 17 1 2 3 4 5 16 17 0 0 6 15 0 0 0 7 14 0 0 0 8 13 12 11 10 9 정수 입력 : 35 1 2 3 4 5 6 20 21 22 23 24 7 19 32 33 34 25 8 18 31 0 35 26 9 17 30 29 28 27 10 16 15 14 13 12 11 이런식으로 진행 된다. 그럼 먼저 해당 알고리즘을 적용 하기에 앞서 적절한 2차 배열을 생성 해줘야 한다. 어떠한 규칙이 있는..

알고리즘 2018. 7. 12. 11:15