알고리즘 -1 삽입정렬, 버블정렬, 선택정렬

알고리즘(Algorithm)

 

알고리즘(Algorithm) : 주어진 문제를 해결하기 위한 단계적인 풀이 과정의 모임을 의미한다.

 

• 입출력(Input & output) : 0개 이상의 외부입력과 하나이상의 출력이 있어야 한다.

• 명확성(Definiteness) : 명령은 모호하지 않고 단수 명확해야 한다.

• 유한성(Finiteness) : 한정된 수의 단계를 거친 후에는 반드시 종료해야한다.

• 유효성(Effectiveness) : 모든 명령들은 컴퓨터에서 실행 가능해야 한다.

 

※ 실용적인 관점에서 효율성이 중요하다.

 

 

자료구조와 알고리즘의 관계

 

좋은 프로그램(효율성 좋은) = 자료구조 + 알고리즘

 

 

알고리즘의 설계

 

1. 분할정복 방법 (Recursively)

 

① 분할 : 문제를 더 이상 나눌 수 없을 때 까지 작은 문제로 분할

 

② 정복 : 작은 문제들을 순환적으로 분할하고, 만약 작은 문제가 더 이상 분할되지 않을 정도로 충분히 작다면, 작은 문제의 해를 구한다.

 

③ 결합 : 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구한다.

 

※ 하향식 접근 방법 이며, 퀵 정렬, 합병 정렬, 이진탐색이 분할정복 방법이 적용 되었다.

 

 

 

 

2. 동적 프로그래밍 방법 (Dynamic Programming)

 

최적화 문제의 해를 구하기 위한 상향식(Bottom-up) 접근 방식

 

① 주어진 문제를 여러개의 문제로 분할

 

② 가장 작은 부분 문제부터 해를 구하여 테이블에 저장

 

③ 저장된 해를 이용하여 입력 크기가 큰 원래 문제를 점진적 해결

 

 

 

3. 욕심쟁이 방법(Greedy)

 

 

일련의 선택 과정을 통해 해를 찾는데, 전후 단계의 선택과는 상관없이 어떤 기준에 따라 각 과정마다 ‘가장 최고’ 라고 여겨지는 최적해를 선택해 나가면 결과적으로 전체적인 최적 해를 얻을 수 있을 것이라고 희망하는 방법 대표적으로 ‘거스름돈 문제’ 와 ‘배낭 문제’ 등이 있다.

 

 

※희망 : 각 단계의 최적 해를 통해 전체적인 최적 해를 만들어 내지 못 할수 도 있음.

 

 

 

① 거스름돈 문제

 

Q. 고객에게 돌려줄 거스름돈이 870원 이라고 할 때 동전의 최소 개수는 몇 개인가?

 

A. 액면가가 큰 동전부터 최대한 뽑아 거스름돈을 만든다.

 

500 x 1

100 x 3

50 x 1

20 x 2

 

총 7개의 동전을 사용한다.

 

 

② 배낭 문제

 

Q. 다음과 같은 배낭 문제에서 얻을 수 있는 최대의 이익은 얼마인가?

 

M : 가방의 무게

n : 원소의 개수

p : 각물건의 가치

w : 각 원소의 무게

 

 

 

단위당 가치가 높은

p1 > p2 > p4 > p3 식으로 제품을 가방에 넣어주면 된다.

 

p1= 15 , 무게 3

무게 10-3 = 7

p2= 20, 5

무게 7-5 =2

p4= 14 무게 4

무게 2-4 ※무게가 초과하여 넣을 수 없지만 단위 무게 당 쪼개어 넣어준다.

4/2 = 2 가치 14/2 -> 7

 

총 가치 : 15 + 20 + 7 = 42 가 된다.

 

 

※ 해당 문제에선 단위 무게당 원소의 가치로 쪼갤 수 있다는 전제하에 해결할 수 있다는 점이다.

 

 

알고리즘의 분석 및 성능 표현

 

1. 정확성 분석

 

유효한 입력이 주어 졌을 때 유한한 시간 내에 정확한 결과를 산출해야한다.

일반적으로 수학적 기법을 사용하여 알고리즘이 예상한 대로 수행되는지에 대한증명 이필요로 한다.

 

2. 효율성 분석

 

주어진 문제를 시간적으로 또는 공간적으로 얼마나 효율적으로 풀수 있는지를 판단하는 것을 의미

 

① 공간 복잡도

알고리즘의 공간복잡도(space complexity)는 알고리즘의 실행부터 완료까지 필요한 총 메모리의 양

 

 

② 시간 복잡도

알고리즘을 실행시켜 완료하는데 걸리는 시간.

 

※ 알고리즘의 총 수행 시간은 단위 연산이 몇 번 수행되는가에 비례

 

단위 연산의 개수로 표현하기보단, 입력 크기의 함수로 표현 하는 것이 바람직하다. 또한 알고리즘의 수행 시간은 주어진 입력 데이터의 상태에 의해 영향을 받는다.

 

※※※ 최악의 수행 시간을 알고리즘의 시간 복잡도를 평가하는 척도로 많이 사용된다.

 

 

시간 복잡도는

 

표기

 

(1) 점근성능

알고리즘의 수행 시간은 입력의 크기 n이 커질수록 증가한다.

입력데이터의 크기 n이 충분히 커짐에 따라 결정되는 성능을 점근 성능이라 한다.

 

알고리즘 점근성능은 유도된 다항식의 수행시간에 대해 최고차항 만을 이용해 표기한다.

 

알고리즘간의 성능비교가 용이하며, 데이터 개수의 증가 따른 알고리즘 수행시간의 증가 추이를 쉽게 파악할 수 있는 장점을 가지나, 정확한 수행시간을 알지못하는 단점이 존재한다.

 

※ Big-oh [빅 오 표현] : g(n)을 상한으로 표기 하기 때문에 점근적 상한(asymptotic upper bound)를 나타내며, 최악을 표현한다.

 

※ Big-omega [빅 오메가 표현 ] : 빅오 표현의 반대 개념으로 쉽게 접근가능, 알고리즘의 최선의 경우의 성능을 나타낸다.

 

※ Big-theta [빅 세타 표현] : 점근적 상한과 하한으로 동시에 같는 경우에 사용하며, 다른 표기법보다 정확하게 성능을 나타낼수 있다.

 

정렬 알고리즘

 

내부 정렬(Internal sort) : 정렬할 데이터의 양이 충분히 크지 않기 때문에 모든 데이터를 주기억장치에 적재해 정렬하는 방법으로 , Selection Sort, Bubble Sort, Insertion sort, Quick sort ,Merge Srot 등 이 있다.

 

비교기반 정렬 :데이터의 킷값을 직접적으로 비교하며 정렬하는 방식

비교기반 정렬이 아닌 방식 : 키의 분포를 이용하여 정렬 하는 방법이 있다.

 

 

외부 정렬(external sort) : 정렬할 데이터 양이 많아 전체 데이터를 보조기억장치에 저장하여 외부 데이터를 번갈아 가면서 주기억장치에 적재해 정렬하는 방법 , 대치선택방법, 다단계 합병 정렬 등이 있다.

 

 

 

- Selection Sort

선택 정렬은 주어진 원소중에서 가장 작은 킷값을 갖는 원소를 선택하여 차례대로 나열하는 정렬방식

 

1. 가장 작은 값을 갖는 원소를 골라 맨 왼쪽에 위치

2. 두 번째로 작은 값을 갖는 원소를 왼쪽 두 번째에 위치

3. .. 계속 반복

 

선택 정렬은 간단하며 데이터수가 적은 경우에 효율적이다.

 

데이터의 입력 상태에 민감하지 않은 수행 시간을 갖는다. 시간 복잡도를 갖는다.

 

- Bubble Sort

버블 정렬은 주어진 리스트의 왼쪽에서부터 모든 인접한 두 원소를 차례대로비교하면서 왼쪽 값이 더 큰 경우에 오른쪽 값과의 자리 바꿈을 통해 정렬해 나가는 방법

 

※ 자료구조나 프로그래밍을 처음 배울 때 이용하는 정렬방법이며 , 선택 정렬에 비해 매우 비효율적이다.

 

- Insertion Sort

삽입정렬은 자주 사용되는 간단한 정렬방법이다.

 

1. 정렬된 부류와 정렬이 되지않은 그룹으로 나눈 뒤 카드를 하나 뽑아 정렬된 부류와 비교한다.

2. 비교하여 작은 값은 왼쪽으로 이동하고 뽑아진 빈공간에 오른쪽으로 한칸씩 이동시킨다.

 

 

[Developer /DataStructure] - Insertion_sort_ 구현