Section 4 - Unit 11 [자료구조 / 알고리즘]

Alogrithm

: IT 분야에서는 " 문제를 해결하기 위한 프로세스 및 로직을 의미 "로 해석되며, 추가적으로 그저 단순히 "해결"이 아닌, "효율성, 정확성"등을 만족하는 최적의 로직을 의미

• 코딩에서는 어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제 풀이 방법, 해(解)를 의미합니다. 이런 알고리즘은 프로그래밍에서는 input 값을 통해 output 값을 얻기 위한 계산 과정으로 해석

==> 알고리즘은 정확성, 효율성, 명확성을 확보하기 위해 사용함

시간 복잡도 & 공간 복잡도

시간 복잡도

: '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?'에 대한 해답을 얻기 위해 입력값과 연산 수행 시간의 일련의 상관관계를 표현하는 방법

Bing-O 표기법

: 시간 복잡도를 표현하는 방법중 가장 일반적으로 가장되는 방법으로, 최악의 경우를 고려하여 산정하여 시간을 산정하는 방식, 이를 통해 '이 정도 시간까지 걸릴 수 있다'를 고려해 최악의 경우까지 대응가능하게 설계할 수 있음

[Bing-O 종류]

• O(1)
  : 즉시 출력 값을 얻을 수 있음

function O_1_algorithm(arr, index) {
	return arr[index];
}
let result = O_1_algorithm([1,2,3,4,5], 3);

• O(n)
  : n의 입력에 비례하여 연산횟수 증가

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}

• O(log n)
  : n의 입력에 따라 log n의 반복횟수를 가짐

const binarySearch = function (arr, target) {
    let start = 0, end = arr.length - 1
    let mid = 0
    while (start <= end) {
        mid = parseInt((end + start) / 2)
        if (arr[mid] === target) {return mid}
        if (arr[mid] < target) { // 타겟이 오른쪽에
            start = mid +1
        } else { //  타겟 왼쪽
            end = mid - 1
        }
    }
    return -1
};

• O(n^2)
  : n의 입력에 따라 n의 제곱수의 비율로 연산횟수 증가

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		// do something for 1 second
		}
	}
}

• O(2^n)
  : n번의 입력마다 2배수 반복 횟수가 증가해 2^n의 반복횟수를 가짐

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

• 입력의 크기에 따라 시간 복잡도의 개선 정도를 결정해야 하며, 데이터 크기 제한이 있을 경우, 해당 문제상황에 대한 해결 알고리즘의 시간 복잡도를 추측할 수 있음
  

공간 복잡도

: 알고리즘이 동작하는데 사용하는 메로리의 총량, 프로그램 수행시 가변적으로 변동되는 메모를 효율적으로 사용하면 프로그램 성능 개선 가능 (Big-O를 사용해 표현 가능)
[공간 복잡도 중요 상황]

• 하나의 큰 문제상황을 해결하기 위해 문제를 나누고 각각 문제를 해결하고 취합해 큰 문제를 해결하는 문제해결 패더라임으로 해당 방식을 사용할 때는 일반적으로 많이 메모리를 소모함으로 공간 복잡도 개선 중요

알고리즘 유형

Greedy Algorithm

: 선택의 순간마다 현재의 상황에서의 최대-최적의 이익을 얻기위해 선택하는 방식
[절차]

• 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택
• 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
• 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

[특징]

• 탐욕적 선택 속성( Greedy Choice Property ): 앞의 선택이 이후의 선택에 영향을 주지 않음
• 최적 부분 구조( Optimal Substructure ): 문제의 최종적인 해결 === 부분 문제에 대한 최적을 해결 방법의 합

알고리즘 구현 방식 기초

• 알고리즘 구현은 문제 조건에 모두 부합하는 코드를 정확하고 효율적으로 작성하는 것을 목표로 하며, 이런 알고리즘을 구현하기 위해서는 사용하는 프로그래밍 언어의 문법을 정확하게 이해하고 있는 역량 요구됨

완전 탐색

: 모든 경우를 탐색에 문제를 해결하는 방법으로, 답을 무조건적으로 도출할 수 있다는 강력함이 있지만, 최악의 경우에 대한 시간 복잡도(Big-O)를 좋게 가지기 어려움

• ex. Brute Force, 재귀, 순열, DFS/BFS

시뮬레이션

:시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형

• 보통 문제에서 설명해 준 로직 그대로 코드로 작성하면 되어서 문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있음
  -출처 코드스테이츠

동적 프로그래밍 (Dynamic Programming , DP)

: 주어진 문제를 여러 개의 (작은) 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 방식

• 하위 문제에 대한 해결책을 저장하고 동일한 문제의 경우 저장한 해결책을 저장해 하나의 문제에 대해 한 번만 풀도록 함 --> 계산 횟수 줄임
  [동적 프로그래밍 적용 조건]
• Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견됨 (ex. 피보나치 재귀 알고리즘)
• Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같음
  ==> 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있음
  (ex. 최단경로를 파악하는 과정에서 다른 노드까지의 최단 경로 또한 파악 가능)

[tiling 예시]--> 한번씩 보면서 생각해 보자

function tiling2x1(n) {
  //2*n 공간
  let memo = [0, 1, 2]; // 타일 1개 세로로, 타일 2개 가로로 나열 & 세로로 내열
	// memo를 정의하는 아이디어가 중요한 듯
  for (let i = 3; i <= n; i++) {
    memo[i] = memo[i - 1] + memo[i - 2]; // n>=3 부터는 
  }
  return memo[n];
};

알고리즘 with Math

순열 & 조합

순열

: 서로 다른 n개의 원소 중 r개를 순서와 상관있게 선택 혹은 나열하는 것

• n!/(n-r)!

조합

: 서로 다른 n개의 원소 중 중복 없이 순서에 상관없게 r개를 선택하는 것

• n!/r!(n-r)!

Greatest Common Divisor (최대 공약수) & Lowest Common Multiple(최소 공배수)

유클리드 호제법

: 최대 공약수를 구할려는 두수 사이에서 몫과 나머지 구하고 나누는 수와 나머지를 다시 나누는 과정을 반복하고 나머지가 0 이 되는 순간의 나누는 수가 최대 공약수가 되는 최대 공약수를 구하는 방법 (아래 예시 참고)

• 절대조건) a가 b 보다 커야함

ex)

124 / 12 = 10 + 4
		12/4 = 3 + 0
         	   ==> 4

멱집합

: 어떤 집합이 있을 때, 이 집합의 모든 부분집합