*<이것이 취업을 위한 코딩 테스트다 with 파이썬> 을 참고하여 작성한 게시물입니다.
그리디
-
현재 상황에서 지금 당장 좋은 것만 고르는 방법. 그리디 문제에서는 대개 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 제시해준다.
-
대부분의 문제는 그리디를 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분하지만, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.
-
문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
n, m, k = map(int, input().split()) data = list(map(int, input().split()) data.sort() first = data[n-1] second = data[n-2] count = int(m/(k+1))*k count += m%(k+1) result = 0 result += (count) * first result += (m-count) * second print(result)
구현
-
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정.
-
완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형.
n=int(input()) x, y= 1,1 plans = input().split() dx=[0,0,-1,1] dy=[-1,1,0,0] move_types=['L','R','U','D'] for plan in plans: for i in range(len(move_types)): if plan == move_types[i]: nx = x+dx[i] ny = y+dy[i] if nx<1 or ny<1 or nx>n or ny>n: continue x, y = nx, ny print(x, y)
- 좌표 설정시 (x,y) -> (col, row)
- dx=[-1,1,0,0] dy=[0,0,-1,1] -> 상, 하, 좌, 우
DFS
-
깊이 우선 탐색. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 최대한 멀리 있는 노드를 우선으로 탐색하는 알고리즘.
-
ex. 얼음 틀 모양이 주어졌을 때 생성되는 총 아이스크림의 개수.
-
스택 자료 구조를 이용하여 다음과 같이 동작함. 1)탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2)스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3)2번의 과정을 더 이상 수행할 수 없을때까지 반복한다.
def dfs(graph, v, visited): visited[v]=True for i in graph[v]: if not visited[i]: dfs(graph, i, visited)
BFS
-
너비 우선 탐색. 가까운 노드부터 탐색하는 알고리즘.
-
ex. 미로를 탈풀하기 위해 움직여야하는 최소 칸의 개수.
-
큐 자료 구조를 이용하여 다음과 같이 동작함. 1)탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2)큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다. 3)2번의 과정을 더 이상 수행할 수 없을때까지 반복한다.
from collections import deque def bfs(graph, start, visited): queue = deque([start]) visited[start] = True while queue: v = queue.popleft() for i in graph[v]: if not visited[i]: queue.append(i) visited[i]=True -
인자가 두개 이상일때: q=deque(), q.append((x,y))
-
인자가 한 개일때: q = deque([x]), q.append(x)
-
deque : 양방향 queue.
정렬
-
데이터를 특정한 기준에 따라서 순서대로 나열.
-
선택 정렬: 데이터가 무작위로 여러개 있을때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번쨰 데이터와 바꾸는 과정을 반복한다. 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꿈. 시간 복잡도 O(N^2)
for i in range(len(array)): min_index = i #가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if array[min_index]>array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i]
-
삽입 정렬: 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입한다. 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어있을 때 훨씬 효율적임. 시간 복잡도 O(N^2), 최선의 경우 O(N)
for i in range(1,len(array)): for j in range(i, 0, -1): if array[j]<array[j-1]: array[j], array[j-1] = array[j-1], array[j] else: break -
퀵 정렬: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈. 피벗을 사용. 시간 복잡도 O(NlogN)
def quick_sort(array): if len(array)<=1: return array pivot = array[0] tail = array[1:] left_side = [x for x in tail if x<=pivot] right_side = [x for x in tail if x>pivot] return quick_sort(left_side) + [pivot] + quick_sort(right_side) -
계수 정렬: 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘으로, 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때만 사용할 수 있음. 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다. 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성하고, 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다. 시간 복잡도 O(N+K), 그러나 공간복잡도에서 심각한 비효율성을 초래할 수 있음.
count = [0] * (max(array) +1) for i in range(len(array)): count[array[i]] += 1 for i in range(len(count)): for j in range(count[i]): print(i, end=' ') -
파이썬 정렬 라이브러리: sorted(), sort() (시간 복잡도 O(NlogN)
이진탐색
-
배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘. 시작점, 끝점, 중간점에 대해서 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.
def binary_search(array, target, start, end): if start>end: return None mid = (start + end) //2 if array[mid] == target: return mid elif array[mid]>target: return binary_search(array, target, start, mid-1) else: return binary_search(array, target, mid+1, end)
DP
-
메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법. 1)큰 문제를 작은 문제로 나눌 수 있다. 2)작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 이러한 조건을 만족할때 DP를 사용할 수 있음.
-
완전 탐색으로 접근했을 때 시간이 매우 오래 걸리면 DP를 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인. 탑다운보다는 바텀업으로 구현하는 것을 권장.
d = [0] * 100 d[1] = 1 d[2] = 1 n = 99 for i in range(3, n+1): d[i] = d[i-1] + d[i-2] print(d[n])
최단 경로
-
다익스트라 : 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우. 그래프에서 여러개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하므로 그리디 알고리즘으로 분류됨. 다음과 같이 동작한다. 1)출발 노드를 설정한다. 2)최단 거리 테이블을 초기화한다. 3)방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4)해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5)위 과정에서 3, 4번을 반복한다. : 각 노드에 대한 현재까리의 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다.
import heapq import sys input = sys.stdin.readline() INF = int(1e9) n, m = map(int, input().split()) start = int(input()) graph = [[] for i in ragne(n+1)] distance = {INF} * (n+1) for _ in range(m): a,b,c = map(int, input().split()) graph[a].append((b,c)) def dijkstra(start): q=[] heapq.heappush(q,(0,start)) while q: dist, now = heapq.heappop(q) if distance[now] < dist: continue for i in graph[now]: cost = dist+i[1] if cost<distance[i[0]]: distance[i[0]]=cost heapq.heappush(q,(cost,i[0]))
- heapq: 이진트리 기반의 최소 힙 자료 구조 지원(부모 노드가 자식 노드보다 값이 작다). heappush(q, (우선순위, 값)) 기준. 우선순위는 값이 낮을수록 높음. 우선순위가 높은 순서대로 배열.
-
플로이드 워셜 알고리즘: 모든 지점에서 다른 모든 지점까지의 최단 거리를 모두 구해야 하는 경우.
INF = int(1e9) n = int(input()) m = int(input()) graph = [[INF} * (n+1) for _ in range(n+1)] for a in range(1,n+1): for b in range(1,n+1): if a==b: graph[a][b]=0 for _ in range(m): a,b,c = map(int, input().split()) graph[a][b] = c for k in range(1,n+1): for a in range(1, n+1): for b in range(1, n+1): graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
그래프 이론
-
인접 행렬: 2차원 배열을 사용하는 방식. 인접 리스트: 리스트를 사용하는 방식. 두가지 모두 매우 많이 사용되며, 메모리와 속도 측면에서 구별되는 특징을 가짐. (속도 측면에서는 인접 행렬이 앞서고, 메모리 측면에서는 인접 리스트가 앞선다.)
-
ex) 최단 경로를 찾는 문제에서 노드의 개수가 적다면 플로이드 워셜 알고리즘, 노드와 간선의 개수가 모두 많으면 우선순위 큐를 이용하는 다익스트라 알고리즘을 이용하면 유리.
-
서로소 집합: 공통 원소가 없는 두 집합. -> 경로 압축 기법을 사용할 수 있다. 사이클 판별에 사용할 수 있음.
def find_parent(parent,x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a<b: parent[b] = a else: parent[a] = b v, e = map(int, input().split()) parent = [0] * (v+1) for i in range(1,v+1): parent[i] = i cycle = False for i in range(e): a, b = map(int, input().split()) if find_parent(parent, a) == find_parent(parent,b): cycle = True break else: union_parent(parent,a,b) -
크루스칼 알고리즘: 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장 트리(하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프)를 찾아야 할 때 이용. (ex. 도시 사이에 사이클 없이 최소 비용으로 도로를 설치하는 문제) 가장 적은 비용으로 모든 노드를 연결할 수 있으며, 다음과 같이 동작한다. 1)간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2)간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 이때, 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시키고 사이클이 발생한다면 최소 신장 트리에 포함시키지 않는다. 3)모든 간선에 대하여 2번의 과정을 반복한다.
def find_parent(parent,x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a<b: parent[b] = a else: parent[a] = b v, e = map(int, input().split()) parent = [0] * (v+1) edges = [] result = 0 for i in range(1,v+1): parent[i] = i for _ in range(e): a, b, cost = map(int, input().split()) edges.append((cost,a,b)) edges.sort() for edge in edges: cost, a, b = edge if find_parent(parent,a) != find_parent(parent, b): union_parent(parent, a, b) result += cost
-
위상 정렬: 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'. (ex. 선수과목을 고려한 학습 순서 설정). 다음과 같이 동작한다. 1)진입차수가 0인 노드를 큐에 넣는다. 2)큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거하고, 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
from collections import deque v, e = map(int, input().split()) indegree = [0] * (v+1) graph=[[] for i in range(v+1)] for _ in range(e): a, b = map(int, input().split()) graph[a].append(b) indegree[b] +=1 def topology_sort(): result = [] q = deque() for i in range(1,v+1): if indegree[i]==0: q.append(i) while q: now = q.popleft() result.append(now) for i in graph[now]: indegree[i] -=1 if indegree[i] == 0: q.append(i)
