알고리즘Algorithm : 문제해결을 위한 절차, 명령의 나열 형태
알고리즘의 표현방식 : 순서도 flowchart(도형), 의사코드 pseudo-code(수도코드)
-> 대부분 수도코드를 사용함
알고리즘의 효율성 : 시간복잡도, 공간복잡도
-> 주로 시간복잡도로 효율성을 평가
알고리즘의 복잡도 : best, worst, average
-> 주로 최악의 경우를 통해 효율성을 평가
제어구조 : 명령 실행 순서 표현을 위한 문장구조
-> 순차구조 : 순차적으로 실행하는 구조
-> 선택구조(if-else) : 조건식의 참, 거짓에 따라 선택적으로 실행하는 구조
-> 반복구조(while/for) : 특정 문장들을 반복해서 실행하는 문장구조
🖥️ 정렬 알고리즘
➡️ 선택 정렬 selection sort
: 정렬되지 않은 데이터 중에서 가장 작은 데이터를 가장 앞의 데이터와 교환하는 방식
제일 작은 수를 찾아서 자가자리로
ex.1432
1432 -> 1을 1번자리에 -> 제자리
1432 -> 2를 2번자리에 -> 2와 4를 교환 -> 1234
-> 데이터를 하나씩 정렬하기 위해서는 중첩 반복문 필요
➡️ 삽입 정렬 insertion sort
: 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해가며 정렬하는 방식
ex1. 1432
1432 -> 1,4비교 -> 1432 -> 1,4,3비교 -> 1342 -> 1,3,4,2비교 -> 1324 -> 1234
ex2. 2413
2413 -> 2,4비교 -> 2413 -> 2,4,1비교 -> 2143 -> 1243 -> 1,2,4,3비교 -> 1234
-> 정렬되지 않은 데이터들 중 첫 번째 데이터를 key로 하여 정렬된 원소들과 비교한다.
-> 삽입 정렬도 모든 데이터 정렬을 위해 중첩 반복문이 필요하다.
➡️ 버블 정렬 bubble sort
: 서로 이웃한 데이터들을 비교하여 큰 데이터를 뒤로 보내는 과정을 반복하여 정렬하는 방식
ex1. 1432
1432 -> 1,4 비교 -> 1432 -> 4,3 비교 -> 1342 -> 4,2비교 -> 1324 -> 4자리 찾음
1324 -> 1,3 비교 -> 1324 -> 3,2비교 -> 1234
ex2. 2413
2413 -> 2,4비교 -> 2413 -> 4,1비교 -> 2143 -> 4,3비교 -> 2134 -> 3,4자리 찾음 -> 2,1비교 -> 1234 -> 1,2자리 찾음
🖥️ 탐색 알고리즘
➡️ 선형 탐색 linear search
(순차탐색 sequential search라고도 한다)
: 주어진 데이터 집합에서 원하는 데이터를 처음부터 순차적으로 비교하며 찾는 알고리즘
-> 앞에서부터 하나하나 비교하며 찾아내는 것
위와 같은 n개의 데이터가 있을 때, d를 찾기 위해 d1부터 순서대로 탐색한다.
best case일 때 탐색횟수는 1 (d = d1인 경우)
worst case일 때 탐색횟수는 n (d = dn인 경우, 또는 탐색실패인 경우)
-> 비효율적.
➡️ 이진 탐색 binary search
: 정렬된 데이터 집합을 반으로 쪼개면서 탐색하는 알고리즘
(선형탐색은 정렬되지 않은 데이터집합으로도 탐색 가능)
이진탐색 과정
1. 데이터를 정렬한다 : 위 사진이 정렬된 거
2. 가장 작은 인덱스 low값과 가장 큰 인덱스 high값을 구해준다 : low=0, high=6
3. 그 사이 값인 mid값을 구해준다 : mid = (low+high)/2 = 3
4. mid인덱스의 값과 key를 비교한다 : 11 < 15 -> ds[4]~ds[6]
-> mid < key 이면 [mid]~[high] 에서 탐색
-> mid > key 이면 [low]~[mid] 에서 탐색
5. 줄어든 데이터에서 계속 반복 : ds[4]~ds[6]을 가지고 다시 2번 과정으로 가서 반복
6. low인덱스와 high인덱스보다 작은 동안 mid인덱스의 값이 key와 같을 때까지 반복하면서 탐색
✏️ 문제
Q1. 아래 빈칸을 채우시오.
알고리즘은 순서도와 _____를 이용하여 표현할 수 있으며, _______와 _______를 통해서 효율성을 판단할 수 있다.Q2. 버블정렬을 이용해 2413을 정렬할 때, 숫자 교환이 몇 번 일어났는지 쓰시오.
Q3. 정렬된 데이터 1,3,8,11,15,17,20이 있다. key값이 15일 때, 각각 선형탐색과 이진탐색의 비교횟수를 구하시오.
✏️ 해답
A1. 수도(의사)코드, 시간복잡도, 공간복잡도
알고리즘은 순서도와 (수도코드)를 이용하여 표현할 수 있으며, (시간복잡도)와 (공간복잡도)를 통해서 효율성을 판단할 수 있다.
A2. 3번
버블정렬은 서로 이웃한 데이터들을 비교하여 큰 데이터를 뒤로 보내는 과정을 반복하여 정렬하는 방식이다
버블정렬을 통해 2413을 정렬하는 과정은 아래와 같다.
2413 -> 2,4비교 -> 2413 -> 4,1비교(1) -> 2143 -> 4,3비교(2) -> 2134 -> 3,4자리 찾음 -> 2,1비교(3) -> 1234 -> 1,2자리 찾음
위 과정에서 숫자교환은 총 3번 일어났다.
A3. 5번, 2번
1. 선형탐색 : 하나씩 숫자를 비교하며 탐색하는 방법이다.
처음부터 순서대로 1과15, 3과15, 8과15, 11과15, 15와15를 비교하여 같은 숫자를 찾았으니 비교횟수는 5번이다.
2. 이진탐색 : 데이터를 반으로 쪼개면서 탐색하는 방법이다.
(low인덱스와 high인덱스보다 작은 동안 mid인덱스의 값이 key와 같을 때까지 반복하면서 탐색)
먼저, low=0, high=6, mid1=3에서 인덱스가 mid1일 때 값이 11인데,
key값인 15보다 작으므로 mid1 오른쪽의 데이터를 사용한다. --> 비교1번쪼개진 데이터
15,17,20에서도 반복한다.low=4, high=6, mid2=5에서 인덱스가 mid2일 때 값이 17인데,
15보다 크므로 mid2 왼쪽의 데이터를 사용한다. --> 비교2번쪼개진 데이터
15에서 low=4,high=4 : low가 high보다 작지 않으므로 탐색 끝
