문제 중간 번호가 될 수 없는 구슬의 개수를 구하는 문제 1. n 구슬의 개수 (1 ≤ n ≤ 99, n은 홀수) 2. m 무게 정보의 개수 (1 ≤ M ≤ N(N-1)/2) 3. 설명 만약 문제의 입력이 다음과 같이 주어지면
그래프? 정점과 간선들로 이루어진 집합. 즉 트리 역시 그래프에 속한다고 할 수 있다. - 그래프를 표현하는 세가지 방법 1.간선 리스트 말그대로 배열에 간선들을 저장한다. 가장 간단하게 구현되지만 한 정점의 간선에 대한 정보를 얻으려면 모든 간선리스트를 탐색해야 하기 때문에 벨만-포드 알고리즘과 크루스칼 알고리즘 같은 일부 알고리즘이 아...
빨간색, 파란색 고르는것은 항상 매트릭스가 생각나 두개의 버튼 n에서 m을 만들기 위한 최소 버튼 클릭수를 계산하는 문제 내 마음대로 번역 바시야(Vasya)는 신기한 장치를 찾았습니다. 패널의 앞부분은 빨간 버튼, 파란 버튼, 양의 정수를 보여주는 디스플레이가 있습니다. 1) 빨간 버튼을 누르면, 장치는 디스플레이의 숫자에 2를 곱합니...
image.png 문제 파악 일반적인 최소 스패닝 트리는 트리의 가중치 합이 최소가 되어야 한다. 그러나 이 문제의 요구 조건은 스패닝 트리를 이루는 가중치의 최대값과 최소값의 차이가 최소가 되어야 하는 것이다. 생각한 방식은 min값과 max값을 계속 갱신해 나가면서 스패닝 트리를 만드는 것인데 이렇게 되면, 가중치를 정렬함으로써 간선을 효율적...
크루스칼 알고리즘 크루스칼 알고리즘이란 크루스칼 알고리즘과 프림 알고리즘은 최소 스패닝 트리를 만들기 위해 자주 쓰이는 알고리즘이다. 크루스칼 알고리즘의 원리는 매우 간단하다. 그래프의 간선들을 가중치 순으로 정렬해 가장 작은 가중치부터 그리디 알고리즘과 같이 선택해 트리에 포함시키는 것이다. 이 때 사이클이 생기면 안되므로 만약 간선이 추가됨으로...
플로이드 워셜 알고리즘이란 다익스트라 알고리즘과 벨만 포드 알고리즘은 특정 시작 정점을 기준으로 다른 정점들까지 가는 최단 거리를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 알고리즘은 모든 정점들간의 최단 거리를 구할 때 사용하는 알고리즘이다. 그 구현 방식은 세 알고리즘 중 가장 간단하게 느껴진다. 플로이드 워셜 알고리즘의 구현 플로...
image.png 벨만 포드 알고리즘이란 한 정점을 기준으로 다른 정점과의 최단 거리를 찾아주는 알고리즘이다. 다익스트라 알고리즘과의 차이는 다익스트라 알고리즘의 경우 음수 사이클이 존재하는 경우 제 기능을 하지 못한다. 그러나 벨만 포드 알고리즘의 경우 음수 사이클을 감지해낼 수 있다. 벨만 포드 알고리즘의 구현 벨만 포드 알고리즘은...
image.png 문제 파악 두 선수의 기록 시간이 동일하면서 최소 시간으로 운동 종목을 선택하는 문제이다. 종목을 선택하는 것을 간선으로 보는 것을 제외하고선, 그래프로 보는 사고가 생각나지 않아 해결하지 못했다. 문제 풀이 문제 풀이의 핵심은 이 전에 풀었던 문제인 어린이날 문제와 유사하다. 어린이날 문제는 간선을 선택으로 정점을 나...
image.png 문제 파악 최단 거리를 구하는 문제지만 특이한 조건들로 인해 간단히 접근할 수 없다. 먼저 정점들이 소방서, 불난 곳, 불나지 않은 곳으로 나뉘어져 있다. 불난 곳들과 소방서 사이의 최단 거리를 구해야 한다. 따라서 정점마다 가장 가까운 소방서가 다르고 이에 따라 다익스트라 알고리즘을 여러번 돌리는 과정이 필요하게 되어 시간 제...
image.png 문제 풀이 다익스트라 알고리즘의 새로운 간선의 가중치를 더하는 부분을 곱하기로 바꿔주면 된다. 이 때 우선순위 큐의 초기값으로 0이 아닌 1 또는 -1을 넣어줘야 하는 것을 주의 해야 한다. 초기값이 0이 아니라 노이즈가 없는 경우 1이기 때문이다. 느낀점 복잡한 소수점 계산의 경우 long double 형을 사용할 ...
다익스트라 알고리즘이란 다익스트라 알고리즘은 그래프의 정점들 사이에 가중치가 주어졌을 때 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라를 비롯한 대부분의 최단 거리 알고리즘은 음수 가중치를 갖는 간선이 있는 경우 음수 싸이클을 돌면서 가중치의 총합을 발산하는 경로가 생길 수 있어서 최단 거리를 계산할 수 없다. 다익...
image.png 문제 파악 답이 될 수 있는 숫자를 구성하는 숫자가 정해져 있으므로, 답을 구성할 수 있는 숫자들을 그래프의 노드로 보고 BFS로 탐색하면서 최소가 되는 답을 찾을 수 있지 않을까 생각했다. 그러나 문제점은 이런 방식으로 탐색할 경우 답이 존재하지 않는 경우 종료하는 지점을 설정하는 것이 불가능 하다는 것이다. 문제 풀...
image.png 문제 파악 배열의 원소를 최소 횟수로 뒤집어 정렬된 배열을 만드는 문제이다. 배열의 최대 크기가 8이고 배열이 한 번 뒤집힐 때마다 다른 상태가 되며 정렬된 상태로 나아가야 된다는 점에서 착안해 배열의 현재 순서를 string으로 나타내 그래프의 노드로 표현하려고 했다. 이 과정에서 그래프의 순서를 뒤집는 경우의 수 를 따지면서...
문제 파악 image.png 그래프의 한 정점에서 인접한 정점끼리는 감시 카메라를 공유하는데, 이 때 모든 갤러리를 감시하는 감시 카메라의 최소 대수를 구하는 문제이다. 직관적으로 생각했을 때는 정점 별로 감시 카메라를 둔다고 가정했을 때 인접 정점들을 확인하면서 감시 카메라가 설치 되었는지 안되었는지를 체크 하면서 하나씩 늘려나가야 되는데 그 시작...
강결합 컴포넌트란 강연결 요소라고도 불리는 강결합 컴포넌트는 유향 그래프 내에서 정의되는 개념이다. 유향 그래프에서 두 정점 사이에서 양 쪽 모두 이동할 수 있는 경로가 존재하면 두 정점은 같은 강결합 컴포넌트(SCC)에 속해 있다고 말한다. 만약 같은 SCC에 속한 두 정점 중 한 정점이 또 다른 정점과 같은 SCC에 속해 있으면 세 정점간 오고 가는 ...
DFS를 통한 간선의 분류 DFS 스패닝 트리 깊이 우선 탐색을 수행하면 그 과정에서 그래프의 모든 간선을 최소 한 번씩은 만나게 된다. 그 중 처음 만나는 정점과 연결되는 간선은 따라가게 되는데, 이러한 간선들을 모아서 보면 트리 형태를 띠게 된다. 이러한 트리는 당연히, 모든 정점을 지나치므로 스패닝 트리가 되고 이를 DFS 스패닝 트리라고 ...
image.png 문제 파악 내가 생각한 접근법은 단어를 vertex로 보는 것이었다. 그러나 이렇게 그래프를 만든 뒤 오일러 서킷을 찾는 알고리즘을 실행시키면, 같은 단어를 두 번 사용하는 경우까지 따지게 되어 문제의 조건을 만족하지 못한다는 문제점이 생긴다. 그래서 해밀턴 경로를 찾는 알고리즘을 생각해 보았지만 해밀턴 경로를 찾는 알고리즘은 ...
오일러 서킷이란 오일러 서킷은 그래프의 각 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 말한다. 대표적인 오일러 서킷의 사례는 한 붓 그리기이다. 오일러 서킷이 존재하려면 각 간선이 모두 한 컴포넌트 안에 있어야 하고 ( 서로 연결될 수 없는 위치에 간선이 존재해서는 안된다) 각 vertex에 연결된 엣지의 수 가 짝수여야 한다. 만약 홀수...
문제 정의 특정 개수의 문자열을 받고, 그 정보를 바탕으로 알파벳 사전 순서를 결정하는 문제이다. 그래프와는 관련이 없어 보이는 문제이지만, 위상 정렬의 특성을 확인하면 문제를 해결할 수 있다. 위상 정렬은 의존성을 가진 그래프, 즉 순서를 가진 그래프를 순서에 모순이 생기지 않도록 정렬해 주는 특성을 가지고 있다. 알파벳 사전 순서를 예로 들면 d...