알고리즘
[Algorithm] 다양한 그래프 알고리즘 : 서로소 집합(union-find), 크루스칼 알고리즘(Kruskal Algorithm), 위상 정렬(topology sort)
서로소 집합 (Disjoint Sets) : 공통 원소가 없는 두 집합 > 서로소 집합 자료구조 (union-find 자료구조) - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 - 연산 * union 연산 : 2개의 집합을 하나의 집합으로 합치는 연산 * find 연산 : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산 - 트리 자료구조를 이용하여 집합을 표현한다 > 서로소 집합 계산 알고리즘 1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다 (1) A와 B의 루트 노드 A', B'를 각각 찾는다 (2) A'를 B'의 부모 노드로 설정한다 (B'가 A'를 가리키도록 한다) 2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반..
[Algorithm] 최단 경로 알고리즘 : 다익스트라(Dijkstra), 플로이드 워셜(Floyd-Warshall) 알고리즘 파이썬 예제 코드
다익스트라 알고리즘 (Dijkstra SAlgorithm) - 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 - '음의 간선'이 없을 때 정상적으로 동작한다 - 그리디 알고리즘 - 힙(Heap) 자료구조를 사용하여 구현할 것이다 - 시간 복잡도 : O(ElogV) > 원리 1. 출발 노드 설정 2. 최단 거리 테이블을 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신 5. 3, 4번을 반복 > Code with Python import heapq import sys input = sys.stdin.readline INF = i..
[Algorithm] 다이나믹 프로그래밍(Dynamic Programming) : 메모이제이션(Memoization), 탑다운(top-down) / 보텀업(bottom-up)
다이나믹 프로그래밍 (Dynamic Programming) 큰 문제를 작은 문제로 나누어 해결하는 방법 다음의 조건을 만족할 때 사용할 수 있다 - 큰 문제를 작은 문제로 나눌 수 있다 - 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 메모이제이션(Memoizations) - 다이나믹 프로그래밍을 구현하는 방법 중 한 종류 - 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 - 값을 저장하는 방법이므로 캐싱(Cashing)이라고도 한다 Code with Python > 피보나치 함수 : 탑다운 다이나믹 프로그래밍 탑다운(Top-Down) : 큰 문제를 해결하기 위해 작은 문제를 호출, 재귀함수 이용 d = [0] * 100 # ..
[Algorithm] 이진 탐색 (Binary Search) : 과정 및 예제 코드
이진 탐색 (Binary Search) 데이터가 정렬되어 있어야만 사용할 수 있으며, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하며 원하는 데이터를 찾는 과정 Steps : 정렬된 10개의 데이터 중 값이 4인 원소 이진 탐색 시간 복잡도 - 시간 복잡도 : O(logN) - 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점 - 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘아가면 이진 탐색과 같이 O(logN)의 속도를 내는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다 - 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심해보자 Code with Python 1. 재귀 함수로 구현한 ..
[Algorithm] 정렬 (Sorting) : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 파이썬 정렬 라이브러리 예제 코드 및 시간 복잡도
정렬(Sorting) 이란? 데이터를 특정한 기준에 따라 순서대로 나열하는 것 선택 정렬 (Selection Sort) 가장 작은 데이터를 선택하여 맨 앞 데이터와 바꾸고, 그 다음 작은 데이터를 선택하여 앞에서 두 번째 데이터와 바꾸는 것을 반복하여 수행하는 정렬 > Steps > Code with Python array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 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[..
[Algorithm] DFS (깊이 우선 탐색) / BFS (너비 우선 탐색) : 파이썬 예제 코드 + 인접 행렬, 인접 리스트
DFS, BFS를 설명하기 전에, 그래프 표현의 2가지 방식은 인접 행렬과 인접 리스트에 대해 알아봅니다! 인접 행렬 (Adjacency Matrix) - 2차원 배열에 각 노드가 연결된 형태를 기록 - 연결되지 않은 노드의 비용은 무한으로 작성한다 INF = int(1e9) graph = [ [0, 1, 1, 1], [0, 0, 1, 0], [0, 0, 0, 0], [0, 0, 1, 0] ] 인접 리스트 (Adjacency List) - 모든 노드에 대해 연결된 노드에 대한 정보를 연결하여 저장 adj = [[] for _ in range(4)] adj[1].append(2) adj[1].append(3) adj[1].append(4) adj[3].append(3) adj[4].append(3) - 가..
[Algorithm] 파이썬에서 스택(Stack)과 큐(Queue)의 사용
스택 (Stack) - 선입후출(First-In Last-Out) 구조 또는 후입선출 구조 - 박스 쌓기에 비유할 수 있다 🔥 스택 with Python - 별도의 라이브러리 없이 기본 리스트에서 append(), pop() 메서드를 이용하여 사용 가능하다 stack = [] stack.append(5) stack.append(2) stack.append(3) stack.pop()# 3 stack.append(1) stack.append(4) stack.pop()# 4 print(stack[::-1]) # 최상단 원소부터 출력 # [1, 2, 5] 큐 (Queue) - 선입선출(First-In First-Out) 구조 - 대기 줄에 비유할 수 있는 '공정한' 자료구조라고 할 수 있다 🔥 큐 with Py..
[Algorithm] 리스트 컴프리헨션 (List Comprehension)
리스트 컴프리헨션 (List Comprehension) 파이썬의 꽃이라고도 할 수 있죠! [대괄호] 안에 for문과 if문을 넣어 간단하게 리스트를 생성하는 방법을 말한다 2차원 배열을 생성할 때도 편리하고, 여러 줄로 작성할 코드를 한 줄로 줄여준다 예시 😢 리스트 컴프리헨션 없이 '20 이하 2의 배수 리스트' 생성하기 list_a = [] for i in range(1, 20): if i % 2 == 0: list_a.append(i) print(list_a) # [2, 4, 6, 8, 10, 12, 14, 16, 18] 😆 리스트 컴프리헨션으로 '20 이하 2의 배수 리스트' 생성하기 list_a = [i for i in range(1, 20) if i % 2 == 0] print(list_a) ..
[Algorithm] 구현 문제 (Implementation) with 방향 이동(dx, dy)
구현 문제 : 문제 해결 분야에서 구현 문제는 '풀이를 떠올리기 쉽지만 소스로 작성하기는 어려운 문제'를 말한다! 예) 코드가 지나치게 길어지는 문제, 특정 소수점까지 출력하는 문제, 문자열을 문자 단위로 끊어서 리스트에 넣는(파싱하는) 문제 등 - 사소한 조건 설정이 많을 수록 구현하기 어렵다 - 이 책에서는 완전 탐색, 시뮬레이션을 모두 구현 유형으로 묶어서 다룬다 * 완전 탐색 : 모든 경우의 수를 다 계산하는 방법 * 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계식 차례로 직접 수행하는 방법 파이썬에서의 구현 > 자료형 - 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없다 - 매우 큰 수의 연산도 기본적으로 지원한다 - 실수형 변수는 유효숫자에 따라 원하는 값이 나오지 않을 수 있다 ..
[Algorithm] 그리디 알고리즘 (Greedy Algorithm), 탐욕법
Greedy Algorithm (그리디 알고리즘) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘의 특징 - 그리디 알고리즘 유형 문제는 매우 다양하기 때문에 많은 유형을 풀어봐야 한다! - 현재 상황에서 가장 좋은 것만 선택해도 문제가 해결되는지 파악한 후, 적용한다 - 보통 코딩 테스트에서 문제를 풀기 위한 최소 아이디어를 떠올릴 능력을 요구하는 문제이다 * 기준에 따라 좋은 것을 선택하므로 문제에서 '가장 큰 순서대로' 같은 기준을 알게 모르게 제시한다 * 자주 정렬 알고리즘(기준을 만족시킬 수 있음)과 짝을 이뤄 출제 그리디 알고리즘의 정당성 - 정확한 답을 구할 수 있다는 보장이 있을 때, 매우 효과적이고 직관적인 알고리즘이다 - 그 해법이 정당한지 검토할 수 있어야 한다 간..