소피it블로그

자료 출처: https://youtu.be/aOhhNFTIeFI 1. 신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 2. 최소 신장 트리 최소한의 비용으로 구성되는 신장 트리 3. 크루스칼 알고리즘 대표적인 최소 신장 트리 알고리즘으로, 그리디 알고리즘으로 분류된다. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 사이클이 발생한 경우: 최소 신장 트리에 포함시키지 않음 사이클이 발생하지 않은 경우: 최소 신장 트리에 포함시킴 위의 과정을 모든 간선에 대하여 반복한다. 최소 신장 트리에 포함된 간선의 비용을 모두 더한 값이 최종 비용이다. 4. 파이썬 구현 # 특정 원소가 속한 집합 찾기 def fi..

자료 출처: https://youtu.be/aOhhNFTIeFI 1. 서로소 집합 자료구조 공통 원소가 없는 두 집합으로, Union Find 자료구조라고도 한다. 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합침 찾기(Find): 특정 원소가 속한 집합이 어느 집합인지 알려줌 2. 여러 개의 합치기 연산 합집합(Union) 연산을 확인하고 서로 연결된 두 노드 A, B를 확인한다. A, B의 루트 노드인 A', B'를 각각 찾는다. A'를 B'의 부모 노드로 설정한다. 모든 합집합 연산이 처리될 때까지 위의 과정을 반복한다. 3. 무방향 그래프 내에서 사이클을 판별하기 위한 용도 (방향 그래프에서는 DFS를 이용) 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다 루트 ..

자료 출처: https://youtu.be/acqm9mM1P6o 1. 플로이드 워셜 알고리즘 최단 경로 알고리즘으로, 모든 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘 다익스트라 알고리즘의 경우 한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘인데 반해, 플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 구한다는 점이 차이점이다. 거쳐가는 노드를 기준으로 알고리즘을 수행하는 것은 다익스트라 알고리즘과 동일하나, 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정이 필요 없다는 점이 다르다. 2차원 테이블에 최단 거리 정보를 저장한다. 다이나믹 프로그래밍 유형에 속하며, 삼중 반복문을 사용한다. 시간 복잡도는 O(N^3) 노드의 개수가 ..

자료 출처: https://youtu.be/acqm9mM1P6o 동빈북을 사두고 생각보다 어려워서 많이 못 봤는데, 이 강의 시리즈를 보다보니 이해가 쉽게 가고 재밌어서 대강 쭉 봤다. 요즘 블로그에 정리하는 내용들도 강의 요약본이나 마찬가지인데, 어려운 알고리즘들은 계속 읽어보며 완전히 이해가 될 때까지 못 넘기겠어서 하나하나 코멘트를 다는 중. 투머치이긴 하지만 내가 이해하기 위한 것이기 때문에 그냥 적으려 한다. 1. 최단 경로 알고리즘 개요 한 지점에서 다른 한 지점까지 한 지점에서 다른 모든 지점까지: 다익스트라 알고리즘 모든 지점에서 다른 모든 지점까지: 플로이드 워셜 알고리즘 이 때 각 지점은 노드로, 지점 간을 연결하는 도로는 간선으로 표현한다. 2. 다익스트라 최단 경로 알고리즘 특정 노..

자료 출처: https://youtu.be/5Lu34WIx2Us 이전까지는 다이나믹 프로그래밍이 뭔지 아예 모르고 이름만 많이 들어봤었는데, 이 강의 덕에 개념이 잡혔다. 문제를 아주 많이 풀어봐야 할 것 같다. 1. 다이나믹 프로그래밍 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법으로, 이미 계산된 결과는 별도의 메모리 영역에 저장한다. 조건 최적 부분 구조 (Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있는 경우. 즉, 작은 문제의 답을 모아 큰 문제를 해결할 수 있음 중복되는 부분 문제 (Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결해야 함 다이나믹 프로그..

자료 출처: https://youtu.be/i5yHkP1jQmo 1. 트리 계층적인 구조를 표현할 때 사용할 수 있는 자료구조로, 다음과 같은 요소를 갖는다. 트리의 크기가 n일 때 전체 간선의 수는 n-1 개이다. 루트 노드 (root node) 단말 노드 (leaf node) 크기 (size): 트리에 포함된 모든 노드의 개수 깊이 (depth): 루트 노드부터의 거리 높이 (height): 깊이 중 최댓값 차수 (degree): 각 노드의 자식방향의 간선의 개수 2. 이진 탐색 트리 (Binary Search Tree) 이진 탐색을 쉽게 할 수 있게 해주는 트리로, 다음을 만족한다. 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 데이터의 조회 과정은 다음과 같다. 루트 노드부터 방문하여 탐색을..