[컴퓨터 공학_복습] 알고리즘 정의, 검색과 정렬 알고리즘

▼ 부스트 코스의 컴퓨터 공학 내용을 복습 & 요약한 내용입니다.

https://www.boostcourse.org/cs112

 

부스트코스의 컴퓨터 공학을 수강 중인데, 알고리즘 부분 내용이 잘 이해가 가지 않아서ㅠㅠ

스스로의 이해를 위해서 내용을 요약, 정리해보려 한다.

 

1. 알고리즘이란?

입력값을 출력값의 형태로 바꾸기 위해, 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열

- 알고리즘에서 중요한 것은, 정확성과 효율성이다. 

- 알고리즘의 실행시간을 나타내는 것은 big O와 big Omega가 있다. 

** 실행시간의 상한(big O)이 낮은게 좋을까, 하한(big Omega)가 낮은게 좋을까? 

>> 데이터의 양이 많을 수록, 최악의 경우를 고려하여 실행시간의 상한이 낮은 알고리즘을 사용하도록 하는 것이 필요.

 

 

2. 선형 검색과 이진 검색

※ 참조 : https://andrew0409.tistory.com/143 

 

(1) 선형 검색(Linear Search) : 배열의 인덱스를 순차적으로 확인하는 검색 알고리즘 

- 자료가 정렬되지 않았거나, 그 어떠한 정보도 없어서 하나씩 찾아야 할 때 유용함

 

a. 의사코드 

**첫번째 값이 찾고자 하는 값이면 완료, 그렇지 않으면 다시 두번째부터 총 n번씩 확인

for i from 0 to n-1
  if i'th element is the target value
     return true
  return false

 

b. 예시 코드

#include <stdio.h>
#include <string.h>

typedef struct
{
	string name;
    string number;
}
product;

int main(void)
{
	product serial[4];
    
    serial[0].name = "컵";
    serial[0].number = "12345";
    serial[1].name = "칼";
    serial[1].number = "12346";
    serial[2].name = "주걱";
    serial[2].number = "12347";
    seiral[3].name = "도마";
    serial[3].number = "12348";
    
    for(int i = 0; i<4; i++)
    {
        if (strcmp(serial[0],"주걱")==0)
        {
            printf("일치하는 값을 찾았습니다.\n");
            return 0;
        }
        printf("일치하는 값이 없습니다.\n");
        return 1;
    }
}

 

c. 실행 시간

- big O = n  >> 최악의 경우, n 번씩 검색해야 함

- big Omega = 1 >> 최선의 경우, 가장 첫번째로 나온 숫자가 찾으려던 값일 수 있음

 

 

(2) 이진 검색(Binary Search) : 배열이 정렬된 경우에 중간부터 시작하여 크고작은 크기에 따라 좌/우로 이동하여 계속 중간값을 비교하는 검색 알고리즘

 

a. 의사 코드 

*찾고자 하는 값이 50일 때,

if no items
	return false
if middle item is 50
	return true
else if 50 < middle item
	search left half
else if 50 > middle item 
	search right half

 

b. 실행 시간

- big O = log n >> 최악의 경우, log n 번씩 검색해야 함

- big Omega = 1 >> 최선의 경우, 중간값이 찾고자 하는 값일 수 있음

 

 

3. 버블 정렬, 선택 정렬, 병합 정렬

※ 참조 : https://velog.io/@jaeyunn_15/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%81-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%84%EA%B5%90

 

(1) 버블 정렬 (bubble sort) : 두 개의 인접 자료 값을 비교하여 위치를 교환하는 정렬 알고리즘

- 이미 정렬된 데이터를 정렬할 때에 가장 빠름 //역순 정렬 시에는 오히려 더 느려짐 

 

a. 의사 코드

repeat n-1 times 
for i from 0 to n-2
	if i'th and i+1'th elements are out of order
    	swap them

- 중첩 루프를 사용하여 (n-1) x (n-2) 번 반복, 

 

b. 실행 시간 

- big O = n^2 >> 최악의 경우, n^2 만큼 정렬을 해야함 

- big Omega = n^2 >> 최선의 경우에도, (검색과는 다르게 정렬되었든 안 되었든 루프는 다 돌아야 해서) n^2 만큼 정렬을 해야함.

 

c. 변형된 버블 정렬 : 자료가 정렬되어 있을 때 버블 정렬을 사용한다면 아래와 같이 의사코드 변경이 가능하다.

repeat until no swaps
	for i from 0 to n-2
    	if i'th and i+1'th elements are out of order
        swap

>> 이때는, 버블 정렬의 하한은 big Omega = n 이 된다.

 

(2) 선택 정렬(selection sort) : 배열 안의 값 중 가장 작은 수 또는 큰수를 찾아, 첫번째 위치 또는 마지막 위치의 수와 교환하는 방법

- (버블 정렬보다) 비교 횟수에 비해서 적은 교환 횟수를 가지기에, 많은 교환이 일어나야 하는 자료 구조에서 비교적 효율적임

 

a. 의사코드

for i from 0 to n-1
  find smallest item between i'th item and last item
  swap smallest item with i'th item

- 처음에 비교 후, 필요할 때에 교환이 이루어짐

- 실제로 돌리면 버블과 마찬가지로 중첩 루프 형태 (밖에서 0부터 시작해서 루프 돌리고, 안에서는 작은 수를 순차적으로 차례대호 확인함)

>> n + (n-1) + (n-2) .... + 1 = n(n+1)/2

 

b. 실행 시간

- big O = n^2 >> 최악의 경우, n^2 만큼 정렬을 해야함 

- big Omega = n^2 >> 최선의 경우에도, (마찬가지로 루프 다 돌아야 해서) n^2 만큼 정렬을 해야함.

 

(3) 병합 정렬(selection sort) : 배열 안의 값들을 가장 작은 단위들로 분할한 뒤, 각각의 작은 단위를 순환적으로 해결 후, 병합(=합병)을 하는 방법

- LinkedList 정렬 사용에 효율적. 크기가 큰 레코드 정렬시 효율적 (이라는데 무슨 말인지는 아직 모르겠다..)

※ 참조 : https://journee912.tistory.com/48

 

a. 의사코드(는 아직 단계가 아니라 나중에 별도로 올리겠습니다. > 참조를 보면 내용 나와 있더라고요.)

 

b. 실행 시간

- big O = n log n >> 최악의 경우, n log n 만큼 정렬을 해야함 

- big Omega = n log n >> 최선의 경우에도, n log n 만큼 정렬을 해야함.

 

 

4. 재귀(recursion) : 함수가 본인 스스로를 호출하는 것.

>> 재귀를 사용하는 이유 : 코드가 간결해짐 = 메모리 줄일 수 있음