본문 바로가기

💻 알고리즘/알고리즘

 (9)
[ 이코테 ] 크루스칼 알고리즘 (Krusckal) ▶ 최소 신장 트리 신장 트리 -> 모든 노드들이 다 연결되어 있지만, 사이클이 존재하지 않는 트리 최소 신장 트리 -> 원래의 그래프에서 나올 수 있는 신장 트리 중, 간선의 가중치 합이 가장 작은 트리 (Minimum Spanning Tree) ▶ 크루스칼 알고리즘 # 특정 원소가 속한 집합 찾기 (루트가 같은지 다른지 확인하기 위함) 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 =..
[ 이코테 ] Union-Find (서로소 집합) ▶ 서로소 집합 (Union Find) ▶ 사이클 판별 출처 : youtu.be/aOhhNFTIeFI
[ 이코테 ] 다익스트라 알고리즘 ▶ 최소힙 & 최대힙 ▶ 다익스트라 알고리즘 3번인 방문하지 않은 노드 중 짧은 노드를 찾을 때 최소힙을 이용해준다 import heapq import sys input = sys.stdin.readline # 무한을 의미하는 값 INF = int(1e9) n, m = map(int, input().split()) start = int(input()) #노드에 관한 정보를 담는 리스트 graph = [[] for _ in range(n + 1)] #최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n + 1) for _ in range(m): a, b, c = map(int, input().split()) #a번 노드에서 b번 노드로 가는 비용이 C라는 의미 graph[a].a..
[ 이코테 ] 다이나믹 프로그래밍 ▶ 메모이제이션 ▶ 탑다운 vs 보텀업 ▶ 피보나치 수열 피보나치 수열을 재귀함수를 이용해서 작성해주면 시간복잡도가 어마어마하게 커진다 아래 그림처럼 중복되는 과정이 많기 때문임 피보나치 수열은 다이나믹 프로그래밍의 사용 조건에 만족하기 때문에 다이나믹 프로그래밍을 사용해서 구현할 수 있다 피보나치 수열 보텀업 방식 피보나치 수열 탑다운(메모이제이션) 방식 탑다운 방식을 사용했을때 실질적으로 호출된 함수의 개수가 줄어든걸 볼 수 있다 따라서 메모이제이션 방식을 사용했을때 피보나치 수열의 시간 복잡도는 O(N)으로 처음에 재귀함수만 이용했을때 보다 시간이 훨씬 줄어든걸 확인할 수 있다 ▶ 개미 전사 즉 i번째 값은 i-1번째 값이 큰지, (i-2의 값 + i가 가진 값)이 큰지 확인하여 큰 값을 지정해주면..
[ 이코테 ] 이진 탐색 알고리즘 ▶ 이진 탐색 찾으려는 값이 중간점 보다 작다면, 중간점부터 이후의 값은 고려하지 않음 그리고 끝점을 중간점 -1 로 지정해준다 반대로 중간점보다 찾으려는 값이 크다면, 시작점부터 중간점까지 데이터를 무시 시작점을 중간점 + 1로 변경한다 ▶ bisect_left, bisect_right 라이브러리 배열에서 데이터 x가 들어갈 인덱스 번호를 반환하는 라이브러리 ▶ 파라메트릭 서치 파라메트릭 서치 유형의 문제를 풀때, 이진 탐색 알고리즘을 사용해야는 경우가 많다 ▶ 떡볶이 떡 만들기 n, m = map(int, input().split()) array = list(map(int, input().split())) start = 0 end = max(array) result = 0 while (start mi..
[ 이코테 ] 정렬 알고리즘 ▶ 선택 정렬 ( 선택 정렬 ) ▶ 삽입 정렬 ( 삽입 정렬 ) ▶ 퀵 정렬 쭉 오른쪽으로 피벗보다 큰 값을 찾고, 왼쪽으로 작은값을 찾다가 엇갈리는 경우가 생기게 된다! (왼쪽에서 피벗보다 작은값을 만나고 오른쪽에서 피벗보다 큰 값을 만날 때) 이 경우는 피벗과 작은 데이터의 위치를 변경해준다 array = [5, 7, 9, 3, 1, 6, 2, 4, 8] def quick_sort(array, start, end): if start >= end: return pivot = start left = start + 1 right = end while(left right): array[right], array[pivot] = array[pivot], array[right] else: array[left], ..
[ 이코테 ] DFS & BFS 알고리즘 ▶ Stack & Queue ▶ DFS def dfs(graph,v,visited): visited[v] = True print(v, end=' ') for e in graph[v]: if not visited[e]: dfs(graph,e,visited) #각 노드가 연결된 정보 (노드는 보통 1부터 사용되기 때문에 0번째는 비워둔다.) #2차원 리스트 graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] #각 노드가 방문됐는지 확인하기 위함 #보통 노드가 1부터 시작하고, 0번째는 사용하지 않기 때문에 노드는 8개지만 9개로 만들어준다 visited = [False] * 9 dfs(graph, 1, visited) ▶ BF..
[ 이코테 ] 구현 알고리즘 ▶ 상하좌우 n = int(input()) plans = input().split() x, y = 1, 1 dx=[0,0,-1,1] dy=[-1,1,0,0] move_type=['L','R','U','D'] for plan in plans: for i in range(len(move_type)): if plan == move_type[i]: nx = dx[i] + x ny = dy[i] + y # 공간을 벗어나는 경우 무시 if nx n or ny > n: continue x, y = nx, ny print(x, y) ▶ 시각 h = int(input()) count = 0 for i in range(h + 1): for j in range(60): for k in..

티스토리툴바