🌈 [Section2] 6. 알고리즘

📕 오늘 배운 내용!

• 의사코드 (pseudocode)
• 시간복잡도 (Time Complexity)
• 탐욕 알고리즘 (Greedy)
• 완전 탐색 알고리즘(Brute-Force Algorithm)
• 이진 탐색 알고리즘(Binary Search Algorithm)

---

✏️ 의사코드 (pseudocode)

• 코드 작성 전에, 일상 언어로 프로그램이 작동하는 논리를 먼저 작성하는 것

• 자연어(일상 언어)와 프로그램 언어의 조합으로 사용해야함

✔ 장점

• 시간이 단축 됨

• 디버깅에 용이함 (오류 발생 시 의사코드로 더 빠르게 원인 파악 가능)

• 프로그래밍 언어를 모르는 사람과 소통 가능

---

✏️ 시간복잡도 (Time Complexity)

' 효율적인 코드 작성 방식을 고민한다 = 시간복잡도를 고민한다 '

• 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘

• 시간복잡도 표기법 : Big-O(빅-오) / Big-Ω(빅-오메가) / Big-θ(빅-세타)
  ➜ 각각 최악 / 최선 / 중간(평균)의 경우에 대비해 나타내는 방법
  ➜ 시간을 계산할 때 최악의 경우를 고려하여 대비하는 것이 바람직하기 때문에
  주로 Big-O 표기법을 사용하여 나타냄

  💡 Big-O 표기법
  ➜ '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는가?' 를 표현한 방법

✔ Big-O 표기법의 종류

( 연산이 빠른 순으로 )
➜ O(1) ➜ O(log n) ➜ O(n) ➜ O(n^2) ➜ O(2^n) ➜ O(n!)

✔️ O(1)

• 일정한 복잡도(constant complexity)

• Big-O 표기법중 가장 빠른 시간 복잡도

• 입력값이 증가하더라도 시간이 늘어나지 않음
  ➜ 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미

  Ex. 배열의 특정 인덱스 값 계산하기
  ➜ 입력값의 크기가 아무리 커져도 다른 계산 없이 특정 인덱스의 값만 출력하면 됨

✔️ O(n)

• 선형 복잡도(linear complexity)

• 입력값이 증가함에 따라 시간 또한 같은 비율로 증가

  Ex. 하나의 for문으로 i가 커지는 만큼 순회하기
  ➜ 입력값의 크기를 모두 순회해야하기 때문에 입력값 만큼 시간이 같이 증가함
  ⠀
  ⚠️ 입력값이 1증가할 때 실행 시간이 2초씩 증가해도 O(n)으로 표기
  ➜ 입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기

✔️ O(log n)

• 로그 복잡도(logarithmic complexity)

• Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도

  Ex. BST(Binary Search Tree) 자료구조에서 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듦
  ➜ 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦

✔️ O(n^2)

• 2차 복잡도(quadratic complexity)

• 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가

  Ex. 중첩된 for문
  ➜ for문의 개수에 따라 n의 제곱수로 시간복잡도가 늘어남
  ⠀
  ⚠️ n^3과 n^5 도 모두 O(n^2)로 표기
  ➜ n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에

✔️ O(2^n)

• 기하급수적 복잡도(exponential complexity)

Ex. 피보나치 수열 fibonacci(n - 1) + fibonacci(n - 2)
➜ n을 40으로 두어도 수초가 걸리고 n을 100으로 하면 평생 결과를 반환받지 못할 수도 있음

⬇️ 입력되는 N값에 따른 다른 알고리즘의 시간 복잡도 ⬇️

✔ 시간복잡도를 구하는 요령

• 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 ➜ O (n)
• 컬렉션의 절반 이상 을 반복 하는 경우 ➜ O (n / 2) ➜ O (n)
• 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 ➜ O (n + m) ➜ O (n)
• 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 ➜ O (n²)
• 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) ➜ O (n²)
• 컬렉션 정렬을 사용하는 경우 ➜ O(n*log(n))

---

✏️ 탐욕 알고리즘 (Greedy)

• 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식

• 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있음

✔ 문제해결 방법

1. 선택 절차(Selection Procedure)
   ➜ 현재 상태에서의 최적의 해답 선택

2. 적절성 검사(Feasibility Check)
   ➜ 선택된 해가 문제의 조건을 만족하는지 검사

3. 해답 검사(Solution Check)
   ➜ 원래의 문제가 해결되었는지 검사, 해결되지 않았다면 선택 절차로 돌아가서 위의 과정 반복

✔ 조건

1. 탐욕적 선택 속성(Greedy Choice Property)
   ➜ 앞의 선택이 이후의 선택에 영향을 주지 않아야함

2. 최적 부분 구조(Optimal Substructure)
   ➜ 문제를 최종적으로 해결하는 방법은 부분 문제에 대한 최적의 문제 해결 방법으로 구성

대표적인 Ex.
가격과 무게가 각기 다른 빵들이 있을 때, 35g까지 담을 수 있는 가방에 최대한 가격이 많이 나가는 빵을 채우려고 한다. (쪼개어 넣는 것도 가능하다)
⠀
1. 넣을 수 있는 빵 중 무게 대비 가장 비싼 빵을 넣는다.
2. 그 다음으로 무게 대비 비싼 빵을 넣는다.
3. 가방에 다 들어가지 않는다면 쪼개어 넣는다.

---

✏️ 구현 (implementation)

➜ 본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있는 상태에서, 문제의 조건에 전부 부합하는 코드를 실수없이 빠르게 작성하는 것을 목표로 두는 것

✔️ 알고리즘 문제를 푼다.
➜ 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다.

✔ 구현능력을 보는 대표적 사례

• 완전 탐색 (brute force)
  ➜ 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식

• 시뮬레이션 (simulation)
  ➜ 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션 하는 것처럼 결과를 확인하는 것

---

✏️ 완전 탐색 알고리즘 (Brute-Force Algorithm)

• 무차별 대입 방법을 나타내는 알고리즘

• 공간복잡도와 시간복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 모든 가능성을 시도하여 문제를 해결하려는 방법

• But, 최적의 솔루션은 아님

💡 무차별 대입 공격 (Brute Force Attack)

• 특정한 암호를 풀기 위해서 모든 값을 대입하는 방법
• 지능형 전략을 사용하지 않고 올바른 조합을 찾을 때까지 다양한 조합을 시도하여 민감한 데이터를 해킹하는 방법

✔ 사용되는 때

1. 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때

2. 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

• 순차 검색 알고리즘
  ➜ 배열 안에 특정 값이 존재하는지 검색할 때 인덱스 부터 마지막 인덱스까지 차례대로 검색

• 문열 매칭 알고리즘 (Brute-Force String Matching)
  ➜ 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지 검색

• 선택 정렬 알고리즘 (Selection Sort)
  ➜ 전체 배열을 순환하면서 현재 요소와 그 다음 요소의 크기를 비교하여 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)의 자리를 교환하는 정렬 알고리즘

• 버블 정렬 알고리즘 (Bubble Sort)

• Tree 자료 구조의 완전탐색 알고리즘 - Exhausive Search (BFS, DFS)

• 동적 프로그래밍 - DP(Dynamic Programing)

✔ 한계

• 문제의 복잡도에 매우 민감
  ➜ 문제가 복잡해질수록 기하급수적으로 많은 자원을 필요로 하는 비효율적인 알고리즘

---

✏️ 이진 탐색 알고리즘(Binary Search Algorithm)

• 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘

• 복잡도 : O(log n)

✔️ 탐색 알고리즘
수많은 데이터중 원하는 데이터를 찾아낼 때 사용하는 알고리즘

• Linear Search Algorithm(선형 탐색 알고리즘)
• Binary Search Algorithm(이진 탐색 알고리즘)
• Hash Search Algorithm(해시 탐색 알고리즘)

✔ 사용되는 때

1. 정렬된 배열에서 요솟값을 더 효율적으로 검색할 때 사용

2. 정렬된 데이터의 양이 많을 때 사용
   ➜ 계속 반으로 자르면서 탐색하기 때문에 데이터의 양이 많으면 많을수록 효율이 높아짐

( But, 데이터양이 적고, 앞쪽에 위치한 데이터를 탐색할 경우에는 Linear Search Algorithm이 더 빨리 찾을 수 있음 )

Ex. 사전, 도서관의 도서와 같은 대규모 데이터 검색

✔ 동작 단계

1. 정렬된 배열의 가장 중간 인덱스를 지정

2. 찾으려고 하는 값 = 지정한 중간 인덱스의 값 이면 탐색 종료 / 아니라면 3단계 실행

3. 찾으려고 하는 값이 중간 인덱스의 값보다 큰 값인지, 작은 값인지 확인

4. 값이 있는 부분과 값이 없는 부분으로 분리

5. 값이 있는 부분에서 다시 1단계부터 반복

➜ 반으로 자르고 탐색하고 또 거기서 반으로 자르고 탐색하고 반복하면서 찾는 것

✔ 한계

• 배열에만 구현 가능

• 정렬되어 있어야만 구현 가능
  ➜ 규모가 작은 배열이라도 정렬이 되어 있지 않다면 정렬을 한 후 Binary Search Algorithm을 사용해도 효율이 높지 않음

💡 BST (Binary Search Tree) vs BSA (Binary Search Algorithm)
BST - 자료구조를 나타냄
BSA - 해결 방법을 나타냄

---

🌈 느낀점

오늘은 개념들이 많았는데 사실 읽으면서 왼쪽 귀로 들어가서 오른쪽 귀로 나오는 기분이었다
집중이 왜 이렇게 안돼 ,, 날이 좋아서 그럴까..?
문제 풀 때는 이해도 안되고 해결하고 싶으니 몇시간이던 시간가는 줄 모르고 보는데 이런 개념은 직접 해보지 않으니 뭔가 머릿속에 안들어온다 ㅠ
오늘도 빡공해서 내일 문제 잘 풀 수 있도록 해야지