[이것이 취업을 위한 코딩 테스트다 with 파이썬] PART 03

방학동안 알고리즘을 공부하다 보니까 벌써 PART 03 기출문제네..

들어가기 전에 기억해야하는 것들을 정리해보고 싶었다.

 

1. 그리디 알고리즘 ( 내가 느끼는 난이도 : 쉬움 )

- 지금 당장 좋은 것만 고르는 방법. 현재의 선택이 나중에 미칠 영향은 신경쓰지 않아

- '최적의 해'를 구하기 위한 최소한의 아이디어를 떠올리고 정당한지 검토할 것

ex) 다익스트라, 거스름돈 등

 

- 거스름돈 문제에서 동전의 단위가 서로 배수 형태가 아닌 무작위인 경우에는 다이나믹 프로그래밍으로.

 

2. 구현 ( 내가 느끼는 난이도 : 극악 )

- 아이디어를 코드로. 경험이 바탕이 될테니 많이 풀어보기

- 머릿속으로 감은 오지만 막상 코드로 옮기지 못하는 경우의 문제들이 다 '구현'문제

ex) 완전 탐색 - 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

시뮬레이션 - 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

 

* 메모리 제약사항, 타입에 따른 크기 범위를 신경써야 함

API 개발 문제가 출제된 적이 있음. 카카오 공채 '카카오 문제풀이 서버와 통신하는 프로그램 모듈' 작성

 

3. DFS/BFS ( 내가 느끼는 난이도 : 좀 더 풀어보자 )

- 탐색 알고리즘

- 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

 

인접 행렬 방식 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

인접리스트 방식 : 리스트로 그래프의 연결 관계를 표현하는 방식 - ex) 다익스트라 최소거리 배열

 

DFS

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리.

없으면 스택에서 최상단 노드를 꺼냄

3. 2번의 과정을 반복

 

BFS

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입, 방문 처리

3. 2번의 과정을 반복

 

BFS가 좀 더 쉬운듯?

 

BFS - 시작지점에서부터 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색... ex) 미로 찾기

 

4. 정렬 ( 내가 느끼는 난이도 : 재밌음 )

- Selection : 가장 작은 것을 '선택'한다는 의미에서의 선택 정렬

- Insertion : 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서의 삽입 정렬

- Quick : 피봇 잡아서 partition

- Count : 최대 값이 작을 때 값들을 index로 사용하는 배열을 만들어서 제한적이지만 매우 빠른 정렬

 

5. 이진 탐색 ( 내가 느끼는 난이도 : 딱 떠오르면 진짜 쉬움 )

- 범위를 반씩 좁혀가는 탐색

- 이진 탐색은 자주 언급되는 문제로써 외워야 함. 팀 노트로 들고 있자.

 

연습문제 다시 한번 풀어봐야 함

 

6. 다이나믹 프로그래밍 ( 내가 느끼는 난이도 : 재밌음 )

- i번째를 이용해서 점화식 세우고 관계 찾아보기

- 관계만 찾는다면 앞에 것 하드코딩으로 넣어주고 점화식 이용해서 배열 만들어나가기

- divide and conquer(DAC 다빈치) 큰 문제를 작게 나누고, 효율적으로 해결하기

bottom-up, top-down => 탑다운은 memorization

 

문제를 푸는 첫번째 단계 : 주어진 문제가 DP임을 확인하기.. 이게 어렵다

재귀 함수로 비효율적인 프로그램을 작성한 뒤 작은 문제에서 구한 답이 큰 문제에서 사용될 수 있으면 개선 GOOD

나는 bottom-up이 편한 것 같다.

 

7. 최단 경로 알고리즘 ( 내가 느끼는 난이도 : 재밌지만 머리아픔 )

- 다익스트라(우선순위 큐) 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우

- 플로이드-워셜(삼중 포문) 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

ex) 알고리즘 강의 시간에 배웠던 min(d[i,j], d[i,k]+d[k,j]) 기억나지? 노가다로 6x6 구하고 그랬던 거

 

* 주의 C++ 라이브러리에 내장된 우선순위 큐는 Max Heap을 이용하므로 cost를 음수로 돌리는 센스 필요

 

8. 그래프 알고리즘 ( 내가 느끼는 난이도 : 재밌음 )

- 크루스칼 알고리즘 ( 서로소 집합, tree의 parent 찾기, cycle 판별(방향 그래프에선 DFS, 비방향에선 서로소 집합으로), 신장트리) 가장 적은 비용으로 모든 노드를 연결할 수 있음. 그리디 알고리즘의 하나.

 

1. 간선 cost에 따라 정렬하고

2. 작은 값부터 확인하여 사이클을 발생시키면 최소 신장 트리에 넣지 않고 발생시키지 않으면 넣음

 

- 위상 정렬 알고리즘 정렬 알고리즘의 하나.

순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘

방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'

ex) 컴퓨터공학과의 커리큘럼 : 자료구조-알고리즘-고급 알고리즘

순서를 지켜주자

 

1. 진입차수가 0인 노드를 큐에 넣는다.

2. 큐가 빌 때까지 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거

2-1. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

- 진입차수 배열 필요하겠지

 

 

요롱롱 밥먹으러 가자