알고리즘 (Algorithms)

1. 검색 알고리즘

• 메모리를 바이트의 격자 배열로 취급하면 자료구조 사용 가능
• 컴퓨터는 사람처럼 빠르게 전체를 파악하는 감지 능력 X
• 컴퓨터는 배열 속 내용물을 하나씩 확인해야함

선형 검색

• 배열의 처음 요소부터 시작해서 인덱스를 하나씩 옮기면서 값이 존재하는 지 확인
• 정렬되지 않은 배열이라면 선형 검색이 더 효율적

이진 검색

• 분할 정복 기법을 사용, 배열의 중앙 요소부터 시작해서 현재 요소가 찾고자 하는 값보다 크면 좌측으로, 값이 작으면 우측으로 진행 반복하여 확인

2. 알고리즘 표기법

• 알고리즘은 직선으로 그려지는 선형 형태이거나 좀 더 굴곡이 있거나 로그 형태 등을 가짐
• 컴퓨터 과학자는 알고리즘을 설명하기 위해 특정 용어 사용 : 알고리즘이 얼마나 잘 설계되어 있는지, 코드가 얼마나 잘 구현되었는지 말해줌
• 가장 일반적으로 Big-O 표기법(알고리즘을 수행하는 데 필요한 시간의 상한선) 사용
• Big-O는 대략적인 추정값 표현 => 인풋값이 커지면 같은 선으로 수렴되기 때문
• 실행시간 : 프로그램이나 알고리즘이 동작하는 데 걸리는 시간 (몇 번의 계산 과정)

O(n^2)
O(nlogn)
O(n)    // 선형 검색 
O(logn) // 이진 검색 
O(1)

• Omega(Ω) : 알고리즘을 수행하는 데 필요한 시간의 하한선

Ω(n^2)
Ω(nlogn)
Ω(n)    // 배열의 길이/개수 계산 
Ω(logn)
Ω(1)    // 선형 검색, 이진 검색

3. 선형 검색

• 배열에 넣고 싶은 값을 미리 안 다면 중괄호({})를 사용해서 한 줄로 표현 가능

int numbers[3] = { 1, 2, 3} 

• 관계연산자(==)는 문자열에 사용할 수 없음. 두 문자열을 비교하려면 문자열 속에 문자를 하나씩 비교해야 함 => strcmp 를 사용
• 서로 관련된 정보를 따로 분리해서 배열로 정의한다면 "항상 동일한 인덱스에 위치함"을 보장하기 어렵다는 단점 존재
• 구조체(struct)는 C에 미리 정의된 키워드로 마치 그릇처럼 여러 가지 자료형을 담을 수 있음, 관련된 정보를 한번에 묶어서 표현할 수 있음

4. 버블 정렬

• 서로를 비교하면서 위치를 바꾸는 방식
• 바깥 반복문 n-1 번 반복하여 비교 기준점이 안쪽 반복문 n-1번 반복하여 비교 대상보다 큰지 작은지 계산
• O(n^2)
• Ω(n^2)

5. 선택 정렬

• 쌍을 이뤄 앞뒤 순서를 교환하지 않고 매번 목표를 세워 가장 작은 값을 찾고 그 다음으로 작은 값을 찾는 방식
• O(n^2)
• Ω(n^2)

6. 정렬 알고리즘의 실행시간

• 버블 정렬 : 교환이 없을 때까지만 반복하도록 조건식을 추가하면 O(n)으로 실행시간을 단축할 수 있음

7. 재귀

• 기존 문제보다 더 작은 크기의 문제를 풀어감

8. 병합 정렬

• 받은 입력에 항목이 하나라면 이미 정렬된 것으로 간주
• 우선 왼쪽 절반을 정렬하고 오른쪽 절반을 정렬한 뒤 짜집기를 하듯이 하나의 배열로 합침, 합쳐진 배열 또한 정렬함
• O(nlogn)
• Ω(nlogn)
• 상한선과 하한선이 같을 때 Theta 표기법(Θ) 사용