글 작성 제목과 내용을 간결하게 정리해 주세요. 제목 내용 <h2>GCD / LCM - 유클리드 호제법</h2><p>최대공약수(GCD)와 최소공배수(LCM)를 구하는 알고리즘</p><pre><code class="language-python">def gcd(a, b): # a = min(a, b) / b = max(a, b) if b == 0: return b if a % b == 0: return b else: return gcd(b, a % b) def lcm(a, b): # a = min(a, b) / b = max(a, b) return int(a * b / gcd(a, b)) </code></pre><h2>소수 찾기- 에라토스테네스의 체</h2><p>임의의 자연수 n에 대해 그 이하의 소수를 가장 간단하고 빠르게 찾는 알고리즘</p><ul><li>핵심 : n의 제곱근 까지만 확인</li></ul><pre><code class="language-python">def eratosthenes(n, arr): for i in range(2, int(n ** 0.5) + 1): if arr[i]: j = 2 while i * j <= n: arr[i * j] = False j += 1 # arr의 인덱스가 True이면 해당 인덱스의 수는 소수임 arr = [True for _ in range(n + 1)] </code></pre><h2>정렬</h2><p><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/06c01314-3454-4992-b108-f949874ce366/Untitled.png" alt="Untitled"></p><h3>선택 정렬</h3><pre><code class="language-python">''' 선택 정렬 : 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘 - 가장 윈시적이고 기초적인 방법이며 비효율적임 시간 복잡도 : O(N^2) ''' # 스왑 메소드 def swap(a, b): temp = a a = b b = temp return (a, b) # 정렬할 리스트 입력 list = list(map(int, input("선택 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' '))) n = len(list) # 선택 정렬 index = 0 for i in range(0, n): min = 9999 for j in range(i, n): if min > list[j]: min = list[j] index = j list[i], list[index] = swap(list[i], list[index]) # 정렬된 리스트 출력 for i in list: print(i, end=' ') </code></pre><h3>버블정렬</h3><pre><code class="language-python">''' 버블 정렬 : 옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 알고리즘 (앞에서 부터 큰 값을 뒤로 보내는 것과 같음) - 구현이 가장 쉽지만 가장 비효율적인 알고리즘 : 매번 스왑을 해야하기 때문 시간 복잡도 : O(N^2) ''' # 스왑 메소드 def swap(a, b): temp = a a = b b = temp return (a, b) # 정렬할 리스트 입력 list = list(map(int, input("버블 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' '))) n = len(list) # 버블 정렬 for i in range(0, n): for j in range(1, n-i): if list[j-1] > list[j]: list[j - 1], list[j] = swap(list[j-1], list[j]) # 정렬된 리스트 출력 for i in list: print(i, end=' ') </code></pre><h3>삽입정렬</h3><pre><code class="language-python">''' 삽입 정렬 : 각 숫자를 적절한 위치에 삽입하는 알고리즘 (뒤로 가면서 앞의 숫자 크기를 보고 그 사이에 적절히 삽입) - 선택, 버블 정렬에 비해 필요한 경우에만 위치를 바꿔 좀 더 효율적임 - 미리 어느정도 정렬이 되어 있다면 아주 빠르게 끝낼 수 있음 시간 복잡도 : O(N^2) (최악의 경우) ''' # 스왑 메소드 def swap(a, b): temp = a a = b b = temp return (a, b) # 정렬할 리스트 입력 list = list(map(int, input("삽입 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' '))) n = len(list) # 삽입 정렬 # while 문 for i in range(1, n): key = list[i] # key : 정렬할 원소 j = i - 1 while j >= 0 and list[j] > key: list[j+1] = list[j] j = j - 1 list[j+1] = key # for 문 '''for i in range(0, n-1): #for j in range(0, i+1): # print(list[j], end=' ') for j in range(0, i+1): if list[i-j] > list[i-j + 1]: list[i-j], list[i-j + 1] = swap(list[i-j], list[i-j + 1]) #print("")''' # 정렬된 리스트 출력 for i in list: print(i, end=' ') </code></pre><h3>퀵정렬</h3><pre><code class="language-python">''' 퀵 정렬 : 대표적인 '분할 정복' 알고리즘(Divide and conquer algorithm)으로, 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나누는 것을 반복 하는 알고리즘. [규칙] - 기준 값인 피벗(Pivot)이 필요 (보통 첫 번째 원소를 피벗으로 사용함) - 기준 값보다 큰 값을 배열의 왼쪽부터, 작은 값을 오른쪽부터 찾음. - 작은 값의 인덱스가 큰 값의 인덱스보다 크면, 작은 값과 큰 값을 교환. - 작은 값의 인덱스가 큰 값의 인덱스보다 작으면, 피벗 값과 작은 값을 교환. - 위 과정을 기준 값의 좌우측에 반복 시간 복잡도: O(N * logN) (평균) O(N^2) (최악) -> 피벗값에 따라 최악의 경우가 생길 수 있음 [ex) 이미 정렬된 배열] ''' # 스왑 메소드 def swap(a, b): temp = a a = b b = temp return (a, b) # 재귀를 이용하여 퀵 정렬 수행 def quickSort(start, end): if start>=end: # 원소가 1개인 경우 그대로 둠 return pivot = start # 피벗은 첫번째 원소 i = start + 1 j = end while i <= j: # 엇갈릴 때까지 반복 while(i <= end and list[i] <= list[pivot]): #끝에 도달하거나 피벗보다 큰 값을 찾을 때까지 반복 i = i + 1 while(j > start and list[j] >= list[pivot]): #피벗에 도달하거나 피벗보다 작은 값을 찾을 때까지 반복 j = j - 1 if(i > j): # 엇갈린 상태(작은 값의 인덱스가 큰 값의 인덱스보다 작으면, 피벗 값과 작은 값을 교환) list[pivot], list[j] = swap(list[pivot], list[j]) else: # 엇갈리지 않은 상태 (작은 값의 인덱스가 큰 값의 인덱스보다 크면, 작은 값과 큰 값을 교환) list[i], list[j] = swap(list[i], list[j]) quickSort(start, j - 1); # 피벗보다 작은 값들에 대해서도 새로운 피벗을 설정하여 퀵정렬 실행 quickSort(j + 1, end); # 피벗보다 큰 값들에 대해서도 새로운 피벗을 설정하여 퀵정렬 실행 # 정렬할 리스트 입력 list = list(map(int, input("퀵 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' '))) n = len(list) # 퀵 정렬 quickSort(0, n-1) # 정렬된 리스트 출력 for i in list: print(i, end=' ') </code></pre><h3>병합정렬</h3><pre><code class="language-python">''' 병합 정렬 : 퀵 정렬과 같은 분할 정복 알고리즘을 사용하는 정렬 알고리즘. 일단 반으로 나누고 나중에 정렬하는 방식 - 퀵 정렬과 다르게 피벗 값에 상관없이 정확히 반을 나누어 정렬하므로 최악의 경우에도 O(N * logN)의 시간 복잡도를 보장한다. [방법] - 다 쪼개진 원소들을 합치면서 정렬을 수행 - 합쳐진 배열은 정렬이 됨 - 최종적으로 합쳐지면 정렬이된 전체 배열을 얻음 시간 복잡도 : O(N * logN) ''' # 스왑 메소드 def swap(a, b): temp = a a = b b = temp return (a, b) # 재귀를 이용하여 퀵 정렬 수행 def mergeSort(list): if len(list) < 2: return list mid = len(list) // 2 low_arr = mergeSort(list[:mid]) high_arr = mergeSort(list[mid:]) mergedList = [] l = h = 0 while l < len(low_arr) and h < len(high_arr): if low_arr[l] < high_arr[h]: mergedList.append(low_arr[l]) l += 1 else: mergedList.append(high_arr[h]) h += 1 mergedList += low_arr[l:] mergedList += high_arr[h:] return mergedList # 정렬할 리스트 입력 list = list(map(int, input("병합 정렬할 숫자를 띄어쓰기로 구분하여 입력 : ").split(' '))) n = len(list) # 병합 정렬 print() list = mergeSort(list) # 정렬된 리스트 출력 for i in list: print(i, end=' ') </code></pre><h3>계수정렬</h3><pre><code class="language-python">count = [0] * (max(arr) + 1) for num in arr: count[num] += 1 </code></pre><h2>DFS</h2><pre><code class="language-python">def dfs(graph, node, visited): visited[node] = True #print(node, end=' ') for v in graph[node]: if not visited[v]: dfs(graph, v, visited) </code></pre><h2>BFS</h2><pre><code class="language-python">from collections import deque def bfs(graph, start, visited): q = deque() q.append(start) visited[start] = True while q: node = q.popleft() # print(node, end=' ') for v in graph[node]: if not visited[v]: visited[v] = True q.append(v) </code></pre><h2>이진 탐색</h2><p>기본</p><pre><code class="language-python">def binary_search(array, target, start, end): while start <= end: mid = (start + end) // 2 if array[mid] == target: return mid elif array[mid] > target: end = mid - 1 else: start = mid + 1 </code></pre><p>파라메트릭 서치 - 떡볶이 떡 만들기 예</p><ul><li>이진 탐색을 이용한 최적화 (타겟에 가까운 값 구하기)</li></ul><h2>최단 경로 - 다익스트라</h2><pre><code class="language-python">import heapq INF = int(1e9) #무한을 의미하는 상수 # 노드의 개수 n, 간선의 개수 m n, m = map(int, input().split()) # 시작 노드 번호 start start = int(input()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기 graph = [[] for _ in range(n + 1)] # 방문한 적이 있는지 체크하는 목적의 리스트 만들기 # visited = [False] * (n + 1) # 우선순위 큐를 통해 확인 가능해 졌으므로 제거 # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n + 1) def dijkstra(graph, start, distance): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] < dist: continue for i in graph[now]: cost = distance[now] + i[1] if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (cost, i[0])) </code></pre><h2>최단 경로 - 플로이드 워셜</h2><pre><code class="language-python">INF = int(1e9) # 무한을 의미하는 상수 # 노드의 개수 및 간선의 개수 입력 n = int(input()) m = int(input()) # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a in range(1, n + 1): graph[a][a] = 0 # 각 간선에 대한 정보를 입력받아, 그 값으로 초기화 for _ in range(m): # A에서 B로 가는 비용은 C라고 설정 a, b, c = map(int, input().split()) graph[a][b] = c def floyd_warshall(graph, n): 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]) </code></pre><h2>최소 신장 트리 - 크루스칼</h2><pre><code class="language-python"># 특정 원소가 속한 집합을 찾기 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 # 노드의 개수와 간선(union 연산)의 개수 입력받기 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 print(result) </code></pre><h2>위상 정렬</h2><pre><code class="language-python">from collections import deque # 노드의 개수와 간선의 개수 입력받기 v, e = map(int, input().split()) # 모든 노드에 대한 진입차수는 0으로 초기화 indegree = [0] * (v + 1) # 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화 graph = [[] for _ in range(v + 1)] # 방향 그래프의 모든 간선 정보를 입력받기 for _ in range(e): a, b = map(int, input().split()) graph[a].append(b) # 정점 A에서 B로 이동 가능 # 진입차수를 1 증가 indegree[b] += 1 # 위상 정렬 함수 def topology_sort(): result = [] # 알고리즘 수행 결과를 담을 리스트 q = deque() # 큐 기능을 위한 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) </code></pre><hr><h1>추가</h1><h2>최장 증가 부분 수열 (LIS)</h2><pre><code class="language-python"># 시간복잡도: O(n^2) def lis(p): n = len(p) dp_length = [1] * n for i in range(n): for j in range(i + 1, n): if p[i] < p[j]: dp_length[i] = max(dp_length[j], dp_length[i] + 1) return max(dp_length) # 가장 긴 값 반환 # 시간복잡도: O(n log n) -> 2진 탐색 활용 def binary_search(arr, target, start, end): while start <= end: mid = (start + end) // 2 if arr[mid] == target: return mid elif arr[mid] > target: end = mid - 1 else: start = mid + 1 return start def lis(p): dp = [] for i in p: idx = binary_search(dp, i, 0, len(dp) - 1) if idx == len(dp): dp.append(i) else: dp[idx] = i return len(dp) # bisect 모듈의 bisect_left 함수를 사용 => binary_search함수 대신 사용 from bisect import bisect_left idx = bisect_left(dp, i) </code></pre> 글 종류 이론 정리 알고리즘 이론에 대한 정리글입니다. 문제 풀이 알고리즘 문제 풀이입니다. 알고리즘 분류 수정 취소