서로소 집합 (Disjoint Sets) : 공통 원소가 없는 두 집합 > 서로소 집합 자료구조 (union-find 자료구조) - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 - 연산 * union 연산 : 2개의 집합을 하나의 집합으로 합치는 연산 * find 연산 : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산 - 트리 자료구조를 이용하여 집합을 표현한다 > 서로소 집합 계산 알고리즘 1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다 (1) A와 B의 루트 노드 A', B'를 각각 찾는다 (2) A'를 B'의 부모 노드로 설정한다 (B'가 A'를 가리키도록 한다) 2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반..

다익스트라 알고리즘 (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..

다이나믹 프로그래밍 (Dynamic Programming) 큰 문제를 작은 문제로 나누어 해결하는 방법 다음의 조건을 만족할 때 사용할 수 있다 - 큰 문제를 작은 문제로 나눌 수 있다 - 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 메모이제이션(Memoizations) - 다이나믹 프로그래밍을 구현하는 방법 중 한 종류 - 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 - 값을 저장하는 방법이므로 캐싱(Cashing)이라고도 한다 Code with Python > 피보나치 함수 : 탑다운 다이나믹 프로그래밍 탑다운(Top-Down) : 큰 문제를 해결하기 위해 작은 문제를 호출, 재귀함수 이용 d = [0] * 100 # ..

이진 탐색 (Binary Search) 데이터가 정렬되어 있어야만 사용할 수 있으며, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하며 원하는 데이터를 찾는 과정 Steps : 정렬된 10개의 데이터 중 값이 4인 원소 이진 탐색 시간 복잡도 - 시간 복잡도 : O(logN) - 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점 - 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘아가면 이진 탐색과 같이 O(logN)의 속도를 내는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다 - 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심해보자 Code with Python 1. 재귀 함수로 구현한 ..

정렬(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[..

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) - 가..

스택 (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..

리스트 컴프리헨션 (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) ..

구현 문제 : 문제 해결 분야에서 구현 문제는 '풀이를 떠올리기 쉽지만 소스로 작성하기는 어려운 문제'를 말한다! 예) 코드가 지나치게 길어지는 문제, 특정 소수점까지 출력하는 문제, 문자열을 문자 단위로 끊어서 리스트에 넣는(파싱하는) 문제 등 - 사소한 조건 설정이 많을 수록 구현하기 어렵다 - 이 책에서는 완전 탐색, 시뮬레이션을 모두 구현 유형으로 묶어서 다룬다 * 완전 탐색 : 모든 경우의 수를 다 계산하는 방법 * 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계식 차례로 직접 수행하는 방법 파이썬에서의 구현 > 자료형 - 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없다 - 매우 큰 수의 연산도 기본적으로 지원한다 - 실수형 변수는 유효숫자에 따라 원하는 값이 나오지 않을 수 있다 ..

Greedy Algorithm (그리디 알고리즘) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘의 특징 - 그리디 알고리즘 유형 문제는 매우 다양하기 때문에 많은 유형을 풀어봐야 한다! - 현재 상황에서 가장 좋은 것만 선택해도 문제가 해결되는지 파악한 후, 적용한다 - 보통 코딩 테스트에서 문제를 풀기 위한 최소 아이디어를 떠올릴 능력을 요구하는 문제이다 * 기준에 따라 좋은 것을 선택하므로 문제에서 '가장 큰 순서대로' 같은 기준을 알게 모르게 제시한다 * 자주 정렬 알고리즘(기준을 만족시킬 수 있음)과 짝을 이뤄 출제 그리디 알고리즘의 정당성 - 정확한 답을 구할 수 있다는 보장이 있을 때, 매우 효과적이고 직관적인 알고리즘이다 - 그 해법이 정당한지 검토할 수 있어야 한다 간..