2023.04.14 TIL

토깽이연구소 수석연구원·2023년 4월 14일

TIL 알고리즘

TIL

목록 보기

10/37

오늘의 나는 무엇을 잘했을까?

웹 컴포넌트에 조금 익숙해졌다. 컴포넌트에 데이터를 전달하는 것, render메서드의 진짜 역할 등을 알 수 있었다.

오늘의 나는 무엇을 배웠을까?

Dynamic Programming

다이나믹 프로그래밍은 다음 두 가지 개념을 알아야 한다.
- 최적 부분 구조
  - 부분 문제들의 최적의 답을 이용해서 기존문제의 최적의 답을 구할 수 있다는 것
  - 피보나치 수열 문제를 예로 들자면 다음처럼 부분 문제의 최적을 합하여 기존 문제의 최적의 답을 구할 수 있다는 것
  - 따라서 피보나치 문제는 최적 부분구조를 가진다고 한다.
- 중복되는 부분 구조
  - 피보나치 문제를 다시 예를 들면, 부분 문제들로 나누었을 때, 아래 그림과 같이 같은 색으로 표시된 것은 중복된다. 이렇게 중복되는 부분 문제들을 매번 계산하는 것은 비효율적이다. 다이나믹 프로그래밍 알고리즘 패러다임에서는 이런 중복되는 부분문제들을 중복 계산하는 것을 피하는 기법을 사용한다.
  
  정리하자면, 어떤 문제가 최적 부분구조를 지니고, 중복되는 부분 문제들이 있다면 다이나믹 프로그래밍을 이용해서 중복 계산을 피하면서 효율적으로 문제를 해결할 수 있다.
  
  다이나믹 프로그래밍의 핵심은 한 번 답을 구한 문제는 다시 계산하지 않는 것이다. 답을 기억해둠으로써 중복을 피하는 구조이다.
  
  실제 다이나믹 프로그래밍은 다음과 같은 두 가지 방법으로 구현된다.
- Memoization
  - 중복되는 계산은 한 번만 계산 후 메모해두는 것
  - 중복되는 부분 문제의 답들을 배열이나 변수에 담아 저장하고, 이후에 또 문제가 나오면 다시 계산하지 않고 이 변수들을 참조하는 방식
  - 피보나치 문제를 예로 들면, 가장 큰 문제를 나누어 쪼개가며 1, 2번항이 나올 때까지 푸는 방법
  - 재귀적으로 구현
  - Top-down approach
- Tabulation
  - 중복되는 것부터 먼저 푸는 방법
  - 피보나치 문제를 예로 들면, 1항, 2항부터 기입하여 n항까지, 베이스 케이스부터 배열에 저장해가면서 기존문제까지 올라가는 것
  - 반복문으로 구현
  - Bottom-up approach
Greedy Algorithm

미래를 내다보지 않고 당장 눈 앞에 보이는 최적의 선택을 하는 방식을 그리디 알고리즘이라고 한다.
- 장점
  - 간단하고 빠르다
- 단점
  - 정답이 보장되지 않는다
  
  그리디 알고리즘은 최적의 답을 보장해주지 않는다. 하지만 분명 그리디 알고리즘으로 최적의 답을 구할 수 있는 문제들도 있다. 그렇다면 언제 그리디 알고리즘을 사용할 수 있는지 알아보자. 아래의 두 속성을 가진 문제라면, 해당 문제는 그리디 알고리즘으로 최적의 솔루션을 찾을 수 있다.
- 최적 부분 구조
  - 다이나믹 프로그래밍 때도 설명했었던 개념이다. 부분 문제들의 최적의 답을 이용하여 기존 문제의 최적의 답을 구할 수 있다는 것이다.
- 탐욕적 선택 속성
  - 각 단계에서의 탐욕스러운 선택이 최종 답을 구하기 위한 최적의 선택이 되는 경우, 탐욕석 선택 속성이 있다고 한다.
주간 미션 웹 컴포넌트화

자세한 내용은 여기에 정리해두었다.