본문 바로가기

개발

(99)
[알고리즘] 크루스칼 이전 포스팅에서 union-find알고리즘을 살펴보았다. union-find알고리즘은 무방향 그래프 내에서의 사이클을 판별할 때도 사용할 수 있는 특징이 있다. 신장트리란? 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이 조건은 트리의 성립 조건이기도 하다. 그래서 이러한 그래프를 신장 트리라고 부른 것이다. 크루스칼 알고리즘 가능한 한 최소한의 비용으로 신장 트리를 찾는 것을 최소 신장 트리 알고리즘이라고 한다. 최소 신장 트리 알고리즘 중 하나로는 크루스칼 알고리즘이 있다. 크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있는데, 이 알고리즘은 그리디 알고리즘으로 분류된다. 크루스칼 알고리즘의 구현 방법 먼저 모든 간선에 대해..
[알고리즘] 유니온 파인드(Union-Find) 유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로 상호 배타적 지비합, Disjoint-set이라고도 한다. 여러 노드 중 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지를 확인하는 알고리즘이다. 서로소 집합 자료구조의 연산 알고리즘은 다음과 같다. 1. union(합집합): 서로 연결된 두 노드 A, B를 확인한다. - A와 B의 루트 노드를 찾는다. - A와 B의 루트 노드 중 Union-Find알고리즘 서로소 집합 알고리즘이라고도 불린다. 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다. 이 자료구조는 union과 find 2개의 연산으로..
[알고리즘] 다익스트라 알고리즘 문제를 풀다 보면, 노드와 간선이 주어지고 가장 짧은 길 찾기 등과 같은 문제들을 자주 볼 수 있다. 이러한 문제를 해결하기 위한 알고리즘이 바로 최단 경로이다. 최단 경로를 구하는 방식은 다익스트라, 벨만 포드, 플로이드 와샬, SPFA로 크게 4가지 정도가 있다. 이전에 플로이드 와샬에 대해 정리한 적이 있으니, 오늘은 다익스트라에 대해 정리해보자. 다익스트라 알고리즘이란? 여러 개의 노드와 간선이 있을 때, 특정한 지점에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라는 기본적으로 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 떄문에 그리디 알고리즘으로도 분리된다. 이 설명은 뒤에 더 보겠다. 다익스트라 알고리즘 원리 다익스트라 알고리즘은 ..
[알고리즘] 플로이드-워셜 플로이드 워셜이란? 그래프 상에 각각의 노드에서 출발하여, 특정 노드까지의 최단거리를 모두 구해주는 알고리즘이다. + 다익스트라는 한 지점에서 모든 지점까지의 최단거리를 구해주지만, 플로이드 워셜은 모든 지점에서 모든 지점까지의 최단거리를 구할 수 있다. 특징 세개의 중첩 반복문을 사용하고, O(v^3)의 시간 복잡도를 가진다. 구하는 방법과 원리 보통 이 알고리즘을 사용하는 문제는, 한 지점에서 다른 지점까지의 거리를 모두 알려준다. 주어진 정보를 활용하여 최단거리를 구해야 하는데, 이때 a지점에서 b지점까지의 거리와, a지점에서k + b지점에서k까지의 거리를 비교하여 더 적은 값을 최단거리로 잡는다. 이 부분에 대한 코드만 보면 이렇다. for k in range(1, n+1): for a in ra..
정렬 알고리즘 보호되어 있는 글입니다.
dfs로 조합 구하기 보호되어 있는 글입니다.
우선순위 큐, 힙 우선순위 큐란? 우선 순위를 가진 항목들을 push하고, 우선 순위에 따라 pop하는 자료구조이다. 큐라고 하니 내가 아는 일직선의 큐 형태를 떠올리지만, 그것과는 전혀 다른 트리 형태의 힙 자료구조로 구현된다. (그래서 우선순위 큐와 힙을 동의어로도 많이 쓴다고 한다.) 힙이란? 힙은 완전 이진트리의 형태로 우선 순위에 따라 push, pop되는 자료구조이다. 크게 최대 힙, 최소 힙 두 가지 종류가 있다. 최대 힙이란? 말 그대로 힙 데이터 요소의 우선 순위가 큰 값으로 이루어져 있는 완전 이진트리이다. 최대 힙의 삽입 방식 1. 완전 이진트리를 유지하며 순차적으로 삽입된다. 2. 삽입 이후에 루트 노드까지 순차적으로 값을 비교하며, 값이 부모보다 크다면 현재 노드와 교체한다. 최대 힙의 삭제 방식 ..
[BOJ] 뒤집기_1439 내가 짠 코드. 다른 사람이 짠 코드 효율성에서도 내 코드가 더 길고, 속도도 느리고, 메모리도 더 많이 차지한다. 내가 푼 방식 1. 연속된 0과 1의 구간을 구하여 배열에 추가한다. 2. 둘 중 더 짧은 배열의 길이를 출력한다. 다른 사람 코드 리뷰 요즘 카카오, 쏘마 코테 등을 보면서 코딩 테스트에는 어느정도 수학적 사고를 요구한다고 느꼈다. count + 1 // 2 도 엄청난 수학적 사고가 필요한 것은 아니지만, 그래도 왜 이렇게 되는지 꼼꼼히 잡고 넘어가자. 문자가 바뀌는 시점을 모두 count한 후, 그 값에 +1 후 // 2 연산을 수행하였다. 이게 어째서 가능한 걸까?? (음,, 진짜 왜 이렇게 되는거지?? 그냥 귀납적으로 받아들이면 되는건가,,,?) 리뷰 일단 저렇게 풀거면 굳이 배열에..