2. 알고리즘

01 알고리즘

1. 알고리즘이란

• 컴퓨팅이 입력 - 처리 - 출력하는 과정일 때, 알고리즘은 입력자료 -> 출력형태로 만드는 처리 과정을 뜻함.
• 즉, 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열입니다.
• 알고리즘을 정확하고 효율적으로 짜면 시간과 공간을 절약할 수 있다.

2. 의사코드

• 알고리즘을 표현하는 방법으로는 자연어(natural language), 의사 코드(Pseudocode), 순서도(flowchart)등이 있다.
• 프로그래밍은 컴퓨터가 알아들을 수 있게 정해진 코드를 사용해야하는 반면, 의사코드는 정해진 방법이 없어 문법 제약을 덜 받으므로 알고리즘 표현에 많이 사용된다.

02 선형(linear) 탐색

• 선형탐색 : 원하는 원소가 발견될 때까지 처음부터 차례대로 탐색하는 것. 모든 자료를 확인해야 함.
• 특징 : 정확하지만 비효율적. 자료가 정렬되어 있지 않거나 어떤 정보도 없어서 하나씩 찾아야만 하는 경우에 유용함.

03 정렬

1. 버블정렬

• 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법
• n개의 원소에 대해 버블정렬을 한 번 수행할 때마다 n번째 원소가 제 자리를 찾게 됨
• 간단하지만 교환이 너무 많이 일어남

2. 선택정렬

• 배열 안의 자료들 중 가장 작은(큰) 수를 찾아 첫번째(마지막) 위치의 수와 교환해주는 방식 (출석체크처럼)
• 첫 번째 ~ 마지막 원소까지 훑으면서 그 중 가장 작은 수를 계속 기억한 뒤, 맞는 자리에 있는 원소와 교환한다. 최적-최악에 상관없이 n²번의 비교와 n-1번의 교환이 일어남
• 각 자료를 비교하는 횟수는 증가하지만, 교환 횟수는 최소화됨

3. 삽입정렬

• 자료를 정렬된 부분과 안 된 부분으로 나누고 -> 정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태
• 새로운 원소가 삽입될 때마다 정렬되어 있는 것들이 한 칸씩 이동해야 하고, 마지막 원소가 정렬될 때까지 현재 위치가 최종 위치라고 확신할 수 없으므로 안정성이 낮음
• 이미 대부분 정렬되어 있는 경우 or 자료의 양이 적을 때 효율적

** 다양한 정렬 방법을 표현한 시청각 자료(2번째 영상) : https://www.edwith.org/cs50/lecture/22857?isDesc=false

04 시간복잡도

1. 시간복잡도란

• 알고리즘 수행 시 걸리는 시간(step)으로 효율성을 분석하는 것.
• 효율성이란 비교/교환 처리 시 연산자의 처리 횟수가 적다는 의미

2. Big-O 표기법

• 컴퓨터과학에서 "대략"을 나타내는 공식적인 개념. 가장 중요한(가장 지수가 큰) 부분만 남기고 계수를 삭제함.

• 시간복잡도에서 최악의 경우(시간의 상한선)를 나타내는 표현.

티스토리 텍스트 편집기 이걸 다 옮기다가는 화딱지가 날 것이다

 

3. Big-Ω 표기법

• 최선의 경우(시간의 하한선)을 나타내는 표현.

(1)은 1번이 아니고 상수 시간. log n은 전화번호부 예제처럼 n의 수를 계속 줄여나가는 이진탐색의 경우

 

4. Θ 표기

• 최악의 경우와 최선의 경우에 시간복잡도가 같은 경우.

(추가자료: https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/)

04 정렬 again

1. 합병정렬 (병합정렬)

• 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬하는 방식
• 병합 시에는 Left 와 Right 의 최소값끼리 비교해 그 중 최소값을 배열하는 식으로 합침 (참고: https://reakwon.tistory.com/38 감사합니다..)
• 시간복잡도는 O(n×lon(n))으로 제일 작지만, 나뉘고 합쳐지는 배열을 임시로 저장하기 때문에 메모리가 많이 사용됨.

  

2. 이진탐색

• 계속 나왔던 전화번호부 예시처럼 영역을 반씩 줄여가며 탐색하는 방식
• 원소 정렬되어 있어야만 효율적으로 탐색이 가능

---

부트캠프 테스트 문제 중에 이진탐색으로 풀었던 게 있어서 예시 나올 때마다 신기하고 기분이 새로웠음.

그 때는 물론 이런 용어도 몰랐고 상식적인 방법이라고 생각해서 그렇게 푼 건데, 기초적인 알고리즘 선택 능력을 보는 문제였겠구나 싶다.