본문 바로가기

🔅코딩테스트 공부🔅/❗알고리즘 추가 공부10

[알고리즘] 위상정렬 + 문제풀이 위상 정렬 => O(V+E) 순서가 정해져 있는 작업을 차례대로 수행할 때 사용되는 알고리즘 (방향그래프) 진입차수(indegree) : 노드로 들어오는 간선의 개수 진입차수가 0인 것을 queue에 넣고 그 노드에서 출발하는 간선 삭제 queue가 빌 때까지 반복 코드 from collections import deque v,e = map(int, input().split()) # v 노드 e 간선 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(.. 2023. 3. 2.
[알고리즘] 최소 스패닝 트리 + 문제풀이 신장트리 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 즉, 사이클 없이 모든 노드가 연결됨 (=트리) 최소 신장 트리 알고리즘 => E(logE) 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘 간선 개수 = 노드 개수 - 1 대표적으로 크루스칼 알고리즘이 있음 간선을 가중치에 따라 오름차순 정렬 사이클이 발생하지 않는 경우 MST에 포함 코드 n,m = map(int, input().split()) #n=노드 m=간선 edges = [] parent = [i for i in range(n+1)] #부모를 본인으로 초기화 result = 0 def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def .. 2023. 3. 2.
[알고리즘] UNION FIND(서로소 집합 알고리즘) union find(=서로소 집합 알고리즘) union 연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합침 find 연산 : 특정한 원소가 속한 집합이 어떤 집합인지 알려줌 서로소 집합은 트리 구조를 이용해 표현하며, 부모 테이블을 항상 가지고 있어야 함 무방향 그래프에서 사이클 판별 가능 => 두 노드의 루트 노드가 같으면 cycle union find 코드 def find_parent(parent, x): #루트노드가 바로 부모노드가 됨 => 경로압축 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def find_parent1(parent, x): #부모노드가 제대로 출력 => 경로압축 x if pa.. 2023. 2. 27.
[알고리즘] 최단경로(다익스트라, 플로이드워셜, 벨만포드) 1. 다익스트라 알고리즘 O(ElogV) 한 지점에서 다른 특정 지점까지의 최단 경로를 구할 때 사용 음의 경로가 있으면 사용할 수 없음(=가중치가 양수일 때만 사용 가능) heap(우선순위 큐)를 이용함으로써 시간복잡도를 줄일 수 있음 2. 다익스트라 알고리즘 코드 import heapq INF = int(1e9) n,m = map(int, input().split()) #n은 노드의 개수 m은 간선의 개수 start = int(input()) #출발점 graph = [[] for _ in range(n+1)] distance = [INF] * (n+1) for _ in range(m): a,b,c = map(int, input().split()) graph[a].append((b,c)) #a노드에서 .. 2023. 2. 24.
[알고리즘] 분할과 정복 + 문제풀이 1. 분할정복법(Divide Conquer)이란? 큰 문제를 나눌 수 없을 때까지 작은 문제로 분할해 문제의 답을 얻는 것 Divide => Conquer => Combine 재귀적인 분할을 이용하며, 알고리즘 수행시간은 점화식으로 표현 가능 ※ 재귀할 경우 바닥조건 정해주는 거 잊지 말기 2. 예시1) 거듭제곱 계산하기 2.1 선형 재귀 호출을 하는 경우 a = int(input()) #밑 n = int(input()) #지수 def power(a,n): if n == 1: return a else: return a * power(a, n-1) print(power(a,n) 2.2 선형 이중 재귀 호출을 하는 경우 a = int(input()) #밑 n = int(input()) #지수 def powe.. 2023. 2. 13.
[알고리즘] 다이나믹 프로그래밍 + 문제풀이 다이나믹 프로그래밍 (= 동적계획법) 메모리 공간을 약간 더 사용함으로써 연산 속도를 비약적으로 증가시킴 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 정답이 그것을 포함하는 큰 문제에서도 동일할 경우 사용 가능 메모제이션(=>한 번 구현한 결과를 메모해두고, 다시 호출하면 그대로 가져옴) 상향식(Bottom Up)방식 분할 정복 vs 다이나믹 프로그래밍 공통점 : 큰 문제를 작게 나눔 차이점 : 분할과 정복은 한 번 해결된 문제를 다시 처리하지 않으나, DP는 처리함] 문제 풀이 현황(기록용) 1 백준 24416번 브론즈1 O 20230209 2 백준 9095번 실버3 △ 20230216 3 백준 1463번 실버3 O 20230216 2023. 2. 9.
[알고리즘] DFS, BFS + 문제풀이 인접 행렬 : 2차원 배열로 그래프의 연결관계 표현 인접 리스트 : 리스트로 그래프의 연결 관계 표현 DFS 루트 노드에서 시작해서 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법 깊은 부분을 우선적으로 탐색 스택, 재귀함수 이용 def dfs(graph, v, visited): visited[v] = True print(v, end=' ') for i in graph[v]: if not visited[i]: dfs(graph, i, visited) graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] visited = [False] * 9 dfs(graph, 1, visited) BFS 가까운 노드부터 탐색하는.. 2023. 2. 7.
[알고리즘] 정렬 + 문제풀이 버블정렬 O(N^2) loop를 돌며 인접한 데이터 간의 swap 연산 진행 특정 루프의 전체 영역에서 swap이 한 번도 진행되지 않으면 정렬이 완료된 것 n = int(input()) num = [] for i in range(n): a = int(input()) num.append(a) for i in range(n-1): for j in range(n-1-i): if num[j] > num[j+1]: num[j],num[j+1] = num[j+1],num[j] for i in num: print(i) 선택정렬 O(N^2) 남은 정렬 부분의 가장 작은(or 가장 큰) 데이터를 선택해 가장 앞에 있는 데이터와 바꿈 arr = [7,5,9,0,3,1,6,2,4,8] for i in range(len(a.. 2023. 2. 2.
[알고리즘] 이진탐색 + 문제풀이 순차탐색 리스트 안에 있는 특정 데이터를 찾기 위해 모든 데이터를 차례대로 확인하는 방법 정렬되지 않은 list에서 사용하며, 시간복잡도는 O(N) 이진탐색 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터 탐색 배열 내부의 데이터가 정렬되어 있어야만 사용 가능, 시간복잡도는 O(logN) 데이터의 개수나 값이 1,000만 단위 이상으로 넘어갈 때 사용하면 좋 + 이진탐색트리 왼쪽 노드는 부모 노드보다 작고, 오른쪽 노드는 부모 노드보다 큼 1. 재귀함수를 이용한 이진탐색 코드 def binary_search(array, target, start, end): if start > end: return None mid = (start + end)//2 if array[mid] .. 2023. 2. 1.

티스토리툴바