결국 빛나리라

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 서로소 집합이란 공통원소가 없는 두 집합을 의미한다. 서로소 집합은 서로소 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 자료구조로, 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 Union, 특정 원소가 속한 집합은 어느 집합인지 알려주는 Find 연산을 수행할 수 있다. ▶ 트리자료구조를 이용한 서로소 집합 계산 알고리즘 step 1. 서로 연결된 두 노드 A,B를 확인한다. 두 노드의 루트 노드 A'과 B'을 찾는다. step 2. 일반적으로 두 루트 노드 중 더 번호가 작은 원소의 부모노..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 플로이드 워셜 알고리즘이란? 모든 노드에서 다른 모든 노드까지의 최단경로를 계산하는 알고리즘으로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 2차원 테이블에 최단거리 정보를 저장하고 점화식에 따라 거리 정보를 갱신하는 원리로 다이나믹 프로그래밍 유형에 속한다. 점화식은 각 단계 즉 k의 노드를 점검할 때마다 a에서 b로 가는 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧을 때 해당 값으로 거리정보를 갱신하는 원리를 사용한다. 따라서 점화식은 다음과 같다. Dab= min(Dab, Dak+ Dk..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 힙이란? 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 최소 힙은 가장 작은 우선순위부터 꺼내는 방식이고 최대 힙은 값이 높은 데이터부터 꺼내는 방식이다. 리스트를 사용하는 경우 삽입시간은 O(1), 삭제는 O(N)시간이 걸리는 반면 힙을 사용하는 경우 삽입하고 삭제하는데 O(logN)만큼의 시간을 보장한다. ▷구현 >최소힙 구현 > 최대힙 구현 ▶ 힙을 활용한 다익스트라 알고리즘 힙을 사용하여 개선된 다익스트라 알고리즘을 구현할 수 있다. 알고리즘이 동작하는 원리는 이전 포스팅에서 기록한 ..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 최단경로 알고리즘이란? 최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘으로 한 지점에서 다른 지점, 모든 지점에서 다른 모든 지점까지의 최단 경로 등을 구하는 등 여러 유형의 문제가 있다. 각 지점은 노드로 표현되고 지점 간 연결된 선은 간선으로 표현한다. ▶ 다익스트라 최단 경로 알고리즘이란 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 계산한다. 현실세계의 간선은 음의 부호를 가진 간선으로 표현되지 않기 때문에 이러한 음의 간선이 없을 때 정상적으로 작동한다. 해당 알고리즘은 매 상황에서 가..