배열3 알고리즘 8장 - 선형시간 정렬 알고리즘 : 계수 정렬 - 알고리즘 8장- 선형시간 정렬 알고리즘 : 계수 정렬 - 앞 장에서 설명한 정렬 알고리즘은 비교 연산을 통해서 정렬을 하는 방식을 취했다. 비교 연산은 두 개의 원소의 관계를 크고 작음에 따라 비교하여 판단하는 연산이다. 비교연산으로 정렬하는 방법은 아무리 빨라도 nlgn보다는 빠를 수가 없다. 하지만 비교를 하지 않는 방법으로 하면 이 보다 따른 시간으로 수행이 가능하다. 이런 방법으로 계수 정렬이 있다. 계수 정렬은 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다. x라는 입력은 x보다 작은 원소의 개수가 I-1개라면 정렬 후에 I번째에 위치해야 한다. x보다 작은 원소의 개수는 원소를 개수를 세어서 확인할 수 있다. 계수 정렬에 대한 예를 한 번 들어보자. A라는 배열이 입력으로 들어왔다고 .. 2017. 6. 8. 알고리즘 3장 - 정렬 문제 : 삽입 정렬 - 알고리즘 3장- 정렬 문제 : 삽입 정렬 - 정렬 문제는 n개의 숫자들의 배열을 입력으로 받게 되면 입력된 숫자의 배열이 특정 조건을 만족하도록 다시 나열한 결과를 출력으로 나타내는 문제이다. 이번 장에서는 정렬 문제 중에서 삽입 정렬에 대해서 학습할 것이다. 삽입 정렬은 말 그대로 삽입을 이용한 정렬 알고리즘이다. 삽입이라는 것은 어떤 대상을 다른 대상 사이에 넣는다는 말로 어떤 값을 어디에 삽입할 것인가라는 점이 매우 중요하게 된다. Key 값과 정렬된 리스트가 주어졌을 때, key 값을 정렬된 리스트의 알맞은 위치에 삽입을 해야 하는 문제이다. 예를 들어 key 값이 3이고 정렬된 배열이 일 때 키를 알맞은 위치에 삽입한 배열은 으로 정렬이 될 수 있다. 삽입 정렬의 방법은 key 값을 하나씩 추가.. 2017. 6. 4. 알고리즘 2장 - 정렬 문제 : 선택 정렬 - 알고리즘 2장- 정렬 문제 : 선택 정렬 - 정렬문제는 Sorting problem으로 n개의 숫자들의 배열을 입력으로 받게 되면 입력된 숫자의 배열이 특정 조건을 만족하도록 다시 나열한 결과를 출력으로 나타내는 문제이다. 특정 조건으로는 오름차순이나 내림차순과 같은 것이 예시가 될 수 있다. 만약 input으로 과 같이 들어오게 된다면 오름차순으로 재배열을 시켜서 내보내는 문제일 경우 output으로 값을 가지게 만들어주는 것이다. 정렬문제 중에서 선택정렬 알고리즘이 있다. 이를 알고리즘 설명과 정확성 증명, 성능 분석을 통해 알고리즘에 알아보도록 하자. 선택정렬은 말 그대로 선택하여 정렬하는 알고리즘이다. 여기서 중요한 핵심은 무엇을 선택해서 정렬을 할 것인가에 대한 의문이 생긴다. 최솟값을 선택하여.. 2017. 6. 4. 이전 1 다음
