[동빈나] 이코테 2021 강의 몰아보기

(이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬

위 동영상을 보고 일부 내용만 정리한 내용입니다.

2. 그리드 & 구현

그리드 알고리즘(탐욕법)

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법

- 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구

 

구현

- 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제

- 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용됩니다.

3. 그래프 탐색 알고리즘 : DFS/BFS

- 탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

- DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형

 

스택 자료구조

- 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조

- 입구와 출구가 동일한 형태

큐 자료구조

- 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조

- 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태

재귀 함수

- 자기 자신을 다시 호출하는 함수

- 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시

- 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.

 

DFS(Depth-First Search)

- DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

- DFS는 스택 자료구조(혹은 재귀 함수)를 이용

탐색 순서: 1 -> 2 -> 7 -> 6 ->8 -> 3 -> 4 -> 5

BFS

- 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

- BFS는 큐 자료구조를 이용

탐색 순서: 1 -> 2 -> 3-> 8 -> 7 -> 4 -> 5 -> 6

 6. 다이나믹 프로그래밍(동적 계획법)

- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다.

1. 최적 부분 구조

- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결

2. 중복되는 부분 문제

- 동일한 작은 문제를 반복적으로 해결

 

ex) 피보나치 수열

메모이제이션(Memoization)

- 다이나믹 프로그램을 구현하는 방법 중 하나

- 한 번 계산한 결과를 메모리 공간에 메모

ㄴ 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옵니다.

ㄴ 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 합니다.

 

탑다운 VS 보텀업

- 탑다운(메모이제이션) 방식은 하향식이라고도 하며, 보텀업 방식은 상향식

- 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식

ㄴ 결과 저장용 리스트는 DP 테이블이라고 합니다.

다이나믹 프로그래밍 VS 분할 정복

- 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용

- 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복

 

다이나믹 프로그래밍 문제에 접근하는 방법

- 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요

- 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토

- 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제