📖 학습 주제
- 힙(heap) 문제
- DP(Dynamic Programming) 문제
- DFS/BFS 문제
- 코딩테스트, 면접 특강
✏️ 주요 메모 사항 소개
힙(Heap)
- 최대/최소 원소를 빠르게 찾으려면
힙(Heap)자료구조를 이용할 수 있다.- 연산 : 힙 구성(
heapify), 삽입(insert), 삭제(remove)
- python 에서 힙 적용
import heapqheapq.heapify(L): 리스트 L 로부터 min heap 구성m = heapq.heappop(L): min heap L 에서 최소값 삭제 (반환)heapq.heappush(L,x): min heal L 에 원소 x 삽입
문제 : 더 맵게
https://velog.io/@hjjwa1234/lv2%EB%8D%94-%EB%A7%B5%EA%B2%8C
Dynamic Programming
- Dynamic Programming : 주어진 최적화 문제를 재귀적인 방식으로 보다 작은 부분 문제로 나누어 부분 문제를 풀어, 이 해를 조합하여 전체 문제의 해답에 이르는 방식.
- 알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정 함으로써 탐색 범위를 한정할 수 있음
Dynamic Programming의 적용 예
1. 피보나치 수열
2. Knapsack Problem (가장 높은 값을 가지도록 물건들을 골라 배낭에 담는 문제)
문제 : N 으로 표현
https://velog.io/@hjjwa1234/N%EC%9C%BC%EB%A1%9C-%ED%91%9C%ED%98%84
깊이/넓이 우선 탐색(DFS/BFS)
그래프(graphs)
- 정점(vertex,node)과 간선(edge,link)으로 이루어진 자료 구성
- 유향(directed) 그래프와 무향(undirected) 그래프로 나눔
깊이 우선 탐색 (DFS; Depth-First Search)
- 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행하는 탐색 방법.
스택(Stack)을 이용하여 어느 정점에서DFS를 하고 있는지를 기억하고 되돌아가야함
넓이 우선 탐색 (BFS; Breadth-First Search)
- 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하고, 방문한 각 인접 정점을 기준으로 (방문한 순서에 따라) 또다시 넓이 우선 탐색을 행하는 탐색 방법.
큐(Queue)를 이용하여 어느 정점에서BFS를 해야 하는지를 기록하고 진행해야함
문제 : 여행경로
https://velog.io/@hjjwa1234/%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C
특강 : 코딩 테스트 면접
코딩 테스트
- 코딩테스트를 하는 이유 : 최소한의 문제 해결 능력을 확인(검증) 하기 위하여
- 문제 해결 능력 = 문제 분석과 해결 방법 착안(
problem solving) + 코드로 구현(code implementation)
코딩 테스트
- 검증하려는 역량에 따라 문제 종류와 난이도가 달라짐
코딩 인터뷰
- 직무에 필요한 배경지식을 충분히 갖추고 있는지 점검
- 생각한 바를 논리적으로 올바르게 전달할 수 있는지 점검
whiteboard test,live coding방법 등 활용
<코딩 문제의 대강의 종류>
Implementation : 제시된 흐름에 따라 실행하는 코드를 만들도록 요구
Algorithm Comprehension : 문제의 효과적/효율적 해법을 찾아내도록 요구
Competency Test : 특정한 (고난도) 자료구조와 알고리즘을 착안하여 제한시간 내에 문제의 답을 도출하도록 요구. 좋은 방법을 찾아내라는 테스트
기타 : 특정한 언어 구문(예: SQL)을 활용할 수 있는지를 테스트
<대비>
1. 구현 능력 갖추기 (적어도 하나의 프로그래밍 언어)
2. 기본적인 자료구조 이해 (Array, Stack/Queue, Hash/Map, Tree, Graph)
3. 기초 알고리즘 및 시간/공간 복잡도에 대한 이해
4. 현실 문제를 해결하기 위한 알고리즘 적용 해법 착안 사고훈련
5. 제한 시간 내에 오류 없이 코드 작성 및 디버깅할 수 있는 능력 훈련
<문제 해결 흐름>
빠지기 쉬운 함정
1. 코드를 짧게 쓴다고 빠르게 실행되는 것은 아님
2. 내가 쓴 코드가 어떻게 실행되는지 이해하고 있는 것이 중요. 문제의 성질이 어떤 것인지에 대한 이해.
💦 공부하며 어려웠던 내용
Dynamic Programming 이 어떤 것이고 어떠한 방법으로 구성하면 되는지는 잘 파악했지만 실제로 구현하는 과정은 좀 애를 먹었던 것 같다.
