Algorithm/이론

기약분수 만들기

분자가 a, 분모가 b인 분수를 기약분수로 만드는 방법 → a와 b를 각각 최대공약수로 나누어 주면 된다! import math gcd = math.gcd(a, b) a // gcd b // gcd

LIS 가장 긴 증가하는 부분 수열

1. dp를 이용한 풀이 N = int(input()) arr = list(map(int, input().split())) dp = [1] * N for i in range(N): for j in range(i): if arr[j]

알고리즘 유형 7. 소수

N이 소수인지 판별하기 - 2부터 루트 N ​까지의 수로 모두 나누어 보고, 한 번이라도 나누어 떨어지면 소수가 아닙니다. - 반복문을 빨리 돌기 위해서는 2부터 루트 N 까지의 수들 중 (2를 포함한)홀수 또는 소수로만 나누는 방법을 생각할 수 있습니다. def is_prime(N): if N < 2: return False for i in range(2, int(N ** 0.5) + 1): if not(n % i): return False return True N보다 작은 소수 구하기 에라토스테네스의 체 알고리즘을 사용합니다. 1단계) N + 1 크기의 chk 배열을 만들고 True로 초기화합니다. True는 이 수가 소수가 맞다는 의미입니다. 2단계) 2부터 루트 N까지의 수들 중 소수(chk[i]..

그래프가 주어지는 유형

1. 노드간 연결 정보만 주어지는 유형 → 그래프 정보를 인접행렬 또는 인접리스트에 담아주세요. (아래 코드는 인접행렬) - 노드 개수 대비 간선 수가 많으면 인접행렬, 노드 개수 대비 간선 수가 적으면 인접리스트 adj = [[False for _ in range(v)] for _ in range(v)] for _ in range(e): n1, n2 = map(int, input().split()) adj[n1][n2] = adj[n2][n1] = True 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정..

알고리즘 유형 6. 동적 계획법

동적 계획법 Dynamic Programming - 줄여서 DP라고도 부릅니다. - 문제를 쪼개고, 부분 문제들의 답을 구하는 과정을 반복하며 푸는 방식입니다. - 동적 계획법을 구현하는 방법에는 재귀와 타뷸레이션(반복문)이 있습니다. 피보나치 수열이 동적 계획법 대표 문제입니다. F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) F(5)를 구하고 싶다면 F(4)와 F(3)이 필요합니다. F(5)라는 문제를 F(4)와 F(3)이라는 부분 문제로 쪼개어 풀어야하므로 동적계획법이 쓰인 것입니다. 메모이제이션 Memoization - 한 번 구한 부분 문제의 답을 따로 저장해두고 필요할 때 꺼내쓰는 기법입니다. - 캐싱(caching)이라고도 합니다. - 메모이제이션은 DP와는 별개의 ..

알고리즘 유형 5. 이분 탐색

선형탐색 Linear Search 앞에서부터 차례대로 찾는 것 # L에서 3찾기 L = [2, 5, 3, 4] for i in L: if i == 3: break 이분탐색 Binary Search 탐색 범위를 절반으로 줄여가면서 찾는 것 # L에서 3찾기 L = [2, 3, 4, 5] left = 0 right = len(L) - 1 mid = (left + right) // 2 while left 3: right = mid - 1 else: # L[mid] < 3 left = mid + 1 mid = (left + right) // 2 - 선형탐색보다 구현이 복잡하지만 시간이 짧게 걸립니다. - 배열 안의 값들이 반드시 정렬되어 있어야 합니다. 이분탐색 라이브러리 from bisect import bi..

알고리즘 유형 4. 그래프

그래프 구성 - 정점 (Vertex 또는 Node) - 간선 (Edge) 그래프의 연결 요소 Connected Component - 서로 완전히 분리된 요소들을 '연결 요소'라고 합니다. - 위 그림은 각각의 그래프 2개가 아닌, 연결 요소 2개로 이뤄진 그래프 1개 입니다. 그래프의 분류 1. 그래프의 방향성 방향 그래프 방향이 정해져 있음 무방향 그래프 어느 방향으로 가도 상관 없음 (양방향 그래프) 2. 그래프의 순환성 순환 그래프 순환하는 부분이 한 군데만 있어도 순환 그래프 비순환 그래프 순환하는 부분이 전혀 없음 * DAG (Directed Acycilc Graph) : 방향성 비순환 그래프 * 트리 (Tree) : 무방향 비순환 그래프 더보기 ※ 트리 Tree - 위와 같은 모양을 한 그래프..

알고리즘 유형 3. 탐욕법

탐욕법 Greedy Algorithm - 항상 현재 상태에서 최선의 경우만 탐욕스럽게 고르는 전략입니다. - 완전탐색과 달리 모든 경우를 살펴보지는 않습니다. - 그리디 문제들은 특별한 배경지식이 없더도 문제에서 규칙성을 찾으면 풀 수 있는 편입니다. - 다만 난이도를 아주 쉬운 문제부터 매우 어렵게까지, 출제자 마음대로 만들 수 있습니다. - 그리디 문제의 진짜 어려운 부분은 바로 '이 문제가 그리디 문제인지 판별하는 것'입니다. 탐욕법 대표 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 위 '회의실 배정'문제는 활동 선택 문제(Activity sel..

알고리즘 유형 2. 완전탐색

완전탐색 - 모든 경우를 다 살펴본다! - 거의 같은 의미인 '브루트 포스(무차별 대입)'라는 용어로도 불립니다. - 완전탐색은 모든 경우를 살펴보기에 시간이 오래 걸립니다. 시간을 단축시키고 싶다면 백트래킹을 사용합니다. 백트래킹이란 탐색 과정에서 더 이상 답이 되지 않는 분기를 발견했을 때 되돌아가는 기법을 의미합니다. - 완전탐색은 크게 반복문 / 재귀 / 큐로 구현할 수 있습니다. 관련 알고리즘 반복문 순열 조합 DFS 재귀 큐 BFS 순열 permutation n개의 수 중 r개를 뽑아 줄을 세우는 방법의 수 1. 라이브러리 사용하기 from itertools import permutations arr = [0, 1, 2, 3] for i in permutations(arr, 4): print(..

알고리즘 유형 1. 자료구조 (파이썬)

1. 배열 Array 기본 자료형인 리스트를 배열처럼 사용합니다. 시간 복잡도 임의 접근 O(1) 삽입 / 삭제 O(N) 2. 스택 Stack 기본 자료형인 리스트를 스택처럼 사용합니다. stk = [] stk.append(x) #리스트의 맨 뒤에 요소를 삽입합니다. stk.pop() #리스트의 맨 뒤 요소를 반환하고 삭제합니다. (괄호 안을 비워뒀을 경우) 스택은 한 쪽에서만 데이터를 넣고 뺄 수 있는 자료구조입니다. 이러한 스택의 특징을 FILO(First-In-Last-Out) 또는 LIFO(Last-In-First-Out)라고 부릅니다. 시간 복잡도 삽입 / 삭제 O(1) 3. 덱 Deque 덱을 import해서 사용합니다. from collections import deque dq = deque..