Preparing for Coding Test with Python( Algorithm ), SQL( Data Analysis )
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법.
- 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
- 일반적으로 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형’이라는 특징이 있다.
- 그리디 알고리즘은 기준에 따라 좋은 것을 선택히는 알고리즘이므로, 문제에서 ‘가장 큰 순서대로’，‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해준다.
흔히 풀이법을 떠올리기는 쉽지만, 소스코드로 옮기기 어려운 문제를 구현으로 분류
- 완전 탐색: 모든 경우의 수를 전부 계산하여 해결하는 방법
- 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다.
- 일반적으로 지문이 길어 파악하는데 시간이 소요되며, 적절한 라이브러리를 활용할 줄 안다면 보다 쉽게 풀 수 있는 경우가 많다.
탐색을 이해하려면 -> DFS, BFS 알아야 한다 -> 이를 알기 위해 스택과 큐 자료구조에 익숙해야 한다.
파이썬에서 스택은 별도의 라이브러리 없이 파이썬 리스트를 활용하여 구현 가능
from collections import deque
- 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식 (파이썬 2차원 배열로 구현)
- 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식 (연결 리스트 자료구조를 이용하여 구현)
관련 적절한 비유: 넷플릭스에서 드라마 시청하고자 할 때, DFS는 하나의 시리즈를 정주행하는 것, BFS는 여러 시리즈를 한 화 씩 번갈아 보는 것으로 비유할 수 있다.
DFS는 깊이 우선 탐색이라고도 부르고, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
DFS는 스택 자료구조 (혹은 재귀함수)를 바탕으로 구현되며, 구체적인 동작은 아래와 같다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. (스택에 쌓여있는 건, 확인을 해봐야할 노드)
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라고 있다면, 그 노드를 스택에 넣고 방문 처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. (.pop)
- 더 이상 2번의 과정을 수행할 수 없을 떄까지 반복한다.
그런데 실제로는 스택이 없이도 구현 가능하며, 이때 시간 복잡도 O(N)
BFS는 너비 우선 탐색이라고 불리며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
BFS는 큐 자료구조를 활용하여 구현되며, 구체적인 동작은 아래와 같다.
- 탐색 시작 노드를 큐에 넣고 방문 처리한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 떄까지 반복한다.
시간 복잡도는 O(N)이며, 실제 수행 시간이 일반적으로 DFS에 비해 좋은 편이라는 것을 알면 좋다.
설계할 때 그래프(노드 별 연결 정보)를 어떻게 설계할지 먼저 구상한 뒤, 탐색 함수를 설계해야 한다.
선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
정렬이 이루어진 원소들은 항상 오름차순을 유지하고 있다는 특징을 이용하여 코드를 구현
기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식이다.
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)으로 설정한다.
- 왼쪽부터 피벗보다 큰 데이터를, 2) 오른쪽부터 피벗보다 작은 데이터를 찾아서 3) 뒤바꿔주다가, 4) 엇갈리면 작은 데이터와 피벗을 뒤바꿔준다.
정렬되어 있는 리스트에 탐색 범위를 절반씩 좁혀가면서 데이터를 탐색하는 방법
시간 복잡도는 O(log2N)을 보장한다.
출제 빈도가 높은 편이라 구현 코드를 암기하듯이 익혀두는 게 좋다고 권한다.
이진탐색 라이브러리
from bisect import bisect_left, bisect_right
bisect_left(array, x) = 정렬된 순서를 유지하면서 array에 x가 삽입될 가장 왼쪽 인덱스 알려줌
bisect_right(array, x) = 정렬된 순서를 유지하면서 array에 x가 삽입될 가장 오른쪽 인덱스 알려줌
이진탐색트리
메모리를 적절하게 활용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.
이미 계산된 영역(작은 문제)는 메모리에 저장하여 다음에 다시 계산하지 않고 불러오도록 한다.
- 탑다운: 재귀함수 (하향식, 메모이제이션)
- 보텀업: 다이나믹 프로그래밍(상향식)
이전에 계산한 결과를 일시적으로 기록해두는 넓은 개념. 여기서 결과 저장용 리스트를 DP 테이블이라고 한다.
한 번 계산한 결과를 저장만 해두고 꼭 쓰지 않을 수도 있다.
주어진 문제가 다이나믹 프로그래밍으로 해결할 수 있는지 알아내는 것이 중요하다.
먼저 그리디, 구현, 완전 탐색 유형으로 문제를 해결할 수 있는지 검토하고, 다른 풀이 방법이 떠오르지 않는다면 다이나믹 프로그래밍을 의심해본다.
- 일단 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤,
- 작은 문제에서 구한 답이 큰 문제에세 그대로 사용될 수 있다면,
- 코드를 개선하는 방향으로 문제에 접근한다. 코딩 테스트에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다. (끝도 없이 어려워질 수 있기 때문에 난이도 조절 차원에서)
다양한 문제 상황이 존재할 수 있다. (한 지점과 다른 지점의 최단 경로, 한 지점에서 다른 모든 지점까지의 최단 경로, 모든 지점에서 다른 모든 지점까지의 최단 경로)
문제 상황을 그래프(간선, 노드)로 표현
다익스트라 최단 경로 알고리즘
특정한 지점에서 다른 모든 지점으로 향하는 최단 경로를 계산한다. (정확히 구현하는 연습 자주 해둬야 고난도 문제 풀 때 응용 가능하다)
음의 간선이 없을 때 정상적으로 작동한다. (음수가 존재하면 무한 루프에 빠질 수 있음)
그리디 알고리즘으로 분류되는데, 매 상황에서 가장 비용이 적은 노드를 선택하여 임의의 과정을 반복한다.
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 초기화한다.
- 3, 4번 과정을 반복한다.
우선순위큐 라이브러리
import heapq
heapq.heappush(q, (0, start))
dist, now = heapq.heappop(q)
heapq는 삽입된 데이터의 첫 번째 원소를 기준으로 가장 작은 값을 우선순위로 하기 때문에,
최단거리 기준으로 우선순위를 부여하기 위해선 (거리, 노드) 이런 식으로 데이터를 구성해야 한다.
- 다익스트라: '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 히는 경우'
- 플로이드 워셜: '모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우'