Algorithm5 알고리즘 9장 - 해쉬 알고리즘(1) - 알고리즘 9장- 해쉬 알고리즘(1) - Direct-address tables 는 크기가 U인 테이블 T를 생성하고 key k를 slot k에 저장하는 방식이다. 이 때 중복되는 key는 없다고 가정한다. 이는 데이터를 저장하는 방식인데 전체 크기가 U인 곳에서 actual key인 K가 존재한다고 생각한다. 해당되는 데이터를 table에 저장하고 table에서 필요한 key 값과 그에 해당하는 data를 확인하는 자료구조이다. Direct-address tables을 사용하게 되면 수행시간이 매우 짧다는 장점이 있다. 우리가 알고자 하는 data의 key 값을 알고 있으면 table을 통해 바로 원하는 data를 찾을 수 있기 때문이다. 이에 해당하는 Pseudo code는 다음과 같다. 하지만 이런 .. 2017. 6. 8. 알고리즘 8장 - 선형시간 정렬 알고리즘 : 계수 정렬 - 알고리즘 8장- 선형시간 정렬 알고리즘 : 계수 정렬 - 앞 장에서 설명한 정렬 알고리즘은 비교 연산을 통해서 정렬을 하는 방식을 취했다. 비교 연산은 두 개의 원소의 관계를 크고 작음에 따라 비교하여 판단하는 연산이다. 비교연산으로 정렬하는 방법은 아무리 빨라도 nlgn보다는 빠를 수가 없다. 하지만 비교를 하지 않는 방법으로 하면 이 보다 따른 시간으로 수행이 가능하다. 이런 방법으로 계수 정렬이 있다. 계수 정렬은 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다. x라는 입력은 x보다 작은 원소의 개수가 I-1개라면 정렬 후에 I번째에 위치해야 한다. x보다 작은 원소의 개수는 원소를 개수를 세어서 확인할 수 있다. 계수 정렬에 대한 예를 한 번 들어보자. A라는 배열이 입력으로 들어왔다고 .. 2017. 6. 8. 알고리즘 7장 - 정렬 문제 : 퀵 정렬 - 알고리즘 7장- 정렬 문제 : 퀵 정렬 - 퀵 정렬은 크기가 커서 풀기 어려운 하나의 문제를 크기가 작아서 풀기 쉬운 여러 개의 문제로 바꾸어서 푸는 방법을 사용한다. 이런 방법을 divide-and-conquer paradigm라고 한다. 이를 수행하기 위해 Partitioning을 사용하여 정렬을 한다. Pivot element를 사용하여 Pivot element 왼쪽에는 Pivot 보다 작은 수들을 오른쪽에는 Pivot 보다 큰 값을 가지도록 정렬을 한다. Pivot을 계속 설정하여 위의 과정을 반복하여 수행하면 배열이 오름차순으로 정렬이 되게 된다. 퀵 정렬의 경우 Pivot을 어떻게 잡아서 Partitioning을 수행하는지가 매우 중요한 요건이라고 할 수 있다. 예를 들어 생각을 해보자. 라는.. 2017. 6. 7. 알고리즘 6장 - 정렬 문제 : 힙 정렬(2) - 알고리즘 6장- 정렬 문제 : 힙 정렬(2) - 앞 장에서 힙 정렬에 대한 개념을 알아보았다면 이번 장에서는 힙 구조를 만드는 것에 대해 중점을 두고 힙 정렬에 대해 살펴볼 것이다. 따라서 개념에 대한 부분을 보고자 하면 알고리즘 5장을 보면 될 것이다. Max 힙 구조를 만드는 코드를 한 번 살펴보자. Max 힙 구조는 부모 노드의 값이 자식 노드의 값보다 큰 이진 트리 구조를 나타낸다. Max 힙을 만드는 방법은 위에서 밑으로 만드는 것이 아니라 밑에서 위로 만든다고 할 수 있다. 만약 위에서부터 만들게 되면 밑으로 내려갈 때 마다 Max 힙의 구조를 만족시키는지를 확인해야하지만 밑에서 만들면 밑에서 트리 구조를 만족하는지만 생각하면 되기 때문에 수행 시간에서 단축될 수 있다. 여기서 length의 .. 2017. 6. 7. 알고리즘 1장 - 알고리즘 개요 - 알고리즘 1장- 알고리즘 개요 - 컴퓨터를 공부할 때 필수적으로 공부하는 분야 중 하나가 바로 알고리즘이다. 또한 다양한 곳에서 알고리즘을 활용한 문제나 대회들이 존재한다. 알고리즘은 크게 문제와 해결 방법으로 구성되어 있다고 할 수 있다. 문제는 알고리즘이 나와야하는 이유이고 해결 방법은 알고리즘의 부분이라고 할 수 있다. 이 때 효율성을 고려하게 되는데 알고리즘이 문제의 해결 방법으로 적절한지에 대한 판단이 필요하다. 또한 알고리즘은 단계적으로 이루어진다. 한 단계씩 넘어가면서 문제 해결에 도달하게 된다. 컴퓨터 알고리즘은 컴퓨터를 이용하여 주어진 문제를 풀기 위한 방법이나 절차이다. 앞에서 말한 문제, 해결 방법, 효율성, 단계적 이라는 단어들을 모두 포함하고 있는 어휘이다. 컴퓨터를 이용해서 어떤.. 2017. 6. 3. 이전 1 다음
