개발 블로그

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 풀이를 하기 전에 이분 그래프에 대해 간략히 설명드리겠습니다. 이분 그래프 (Bipartite Grpah) 그래프의 한 종류로, 인접한 꼭짓점을 서로 다른 색으로 칠할 때 두 가지 색으로만 칠할 수 있는 그래프 꼭짓점들의 집합 V와 변들의 집합 E로 이루어진 그래프 G = (V, E)가 이분 그래프라면, 꼭짓점들의 집합 V가 두 집합 A, B(두 개의 그룹)로 나눠져 E에 속한 모든 변들이 ..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 오랜만에 알고리즘 트리 문제를 풀어봤습니다. 이 문제는 트리에서 임의의 두 정점 사이의 가장 긴 거리를 출력하는 문제입니다. 입력의 경우 시작 정점(from)이 주어지고, 시작 정점과 연결된 정점(to)과 두 정점 사이의 거리(dist)를 입력으로 받습니다. 더불어 해당 정점에서 입력을 종료하려면 -1을 입력으로 받아야 합니다. 첫 번째로, 우선 임의의 정점에서 가장 거리가 먼 노..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 트리(tree)란 ? 그래프(Graph)의 일종으로, 한 노드에서 시작해 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프입니다. 최상단 노드를 루트노드, 자식이 없는 노드를 리프노드라고 합니다. 이 문제는 노드의 개수 n이 주어지고, n에 해당하는 부모노드 인덱스를 입력으로 받습니다(부모 노드가 없는 경우에는 -1) 마지막으로 삭제할 노드를 입력 받고, 이러한 과정을 ..

벨만 포드 알고리즘이란? 벨만 포드 알고리즘은 다익스트라 알고리즘과 다른 점이 하나 있습니다. 다익스트라 알고리즘은 임의의 한 정점에서 다른 정점까지 가는 최소 비용을 구하는 알고리즘입니다. 이때, 간선의 가중치는 양수입니다. 하지만, 벨만-포드 알고리즘은 다익스트라 알고리즘과 정의는 같지만, 간선의 가중치가 음수가 되는 경우도 있습니다. 다익스트라 알고리즘 모르시는 분들은 참고하실 수 있도록 해당 링크 남기겠습니다. https://daily1313.tistory.com/237 다익스트라(Dijkstra) 최단 경로 알고리즘 다익스트라 알고리즘이란 무엇인가? 음의 가중치가 없는 그래프의 한 정점(V)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘입니다. 기존에는 O(V^2)의 시간복잡도를 가졌으나,..

다익스트라 알고리즘이란 무엇인가? 음의 가중치가 없는 그래프의 한 정점(V)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘입니다. 기존에는 O(V^2)의 시간복잡도를 가졌으나, 시간이 지나 우선순위 큐를 이용하여 더욱 개선된 알고리즘이 생겨났으며 O((V+E)logV)(V : 정점의 개수, E : 간선의 개수)의 시간 복잡도를 가질 수 있게 되었습니다. O(VlogV)(각 노드마다 미방문 노드 중 출발점으로 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 걸리는 시간) + O(ElogV) (각 노드마다 이웃한 노드의 최단거리를 갱신할 때 걸리는 시간)으로 보시면 될 것 같습니다. 출처 : https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9..

신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미 트리의 조건 : 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않아야 함 사이클(cycle)이란 ? 그래프에서 시작 노드에서 출발해서 다른 노드를 거쳐 다시 시작 노드로 돌아갈 수 있는 경로가 존재한다면, 이는 하나의 사이클이 됩니다. 최소 신장 트리 최소한의 비용으로 신장 트리를 찾기 위한 방법 1, 2, 3번 지역에 도로를 2개 놓아 전체 지역을 연결시키도록 하는 경우에서는 1->2, 2->3을 연결하는 것이 가장 저렴하게 연결할 수 있는 방법입니다. 즉, 최소 신장 트리는 말 그대로 최소한의 비용(가중치의 합이 최소==간선의 비용)으로 신장 트리를 찾아내는 알고리즘이고, 그리디 알고리즘으로 분류됩니다. ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 두 개의 포인터를 이용해서 원하는 값을 추출하는 투 포인터 알고리즘 문제 입니다. 연속된 수들의 부분합 중에서 합이 S이상이 되는 것들 중에서 수열의 최소 길이를 구해야 합니다. 테스트 케이스를 예시로 설명 드리겠습니다. 10 15 5 1 3 5 10 7 4 9 2 8 start, end 변수를 두어 이를 조작하여 원하는 수열의 최소 길이를 구해야 합니다. sum(부분합) < S(원..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 일반적인 BFS탐색 문제와 크게 틀에서 벗어나진 않지만, 벽(1)을 한 번 이동할 수 있는 조건에서 큰 차이를 보입니다. 그리고 이 조건으로 인해 조금 더 어려워졌습니다. 저는 입력을 2차원 배열로 받고, 구하고자 하는 최단경로를 3차원으로 만들어줘서 풀었습니다. 왜냐하면 벽을 부순 경우가 최단 경로가 될 수 있고, 부수지 않은 경우가 최단 경로가 될 수 있기 ..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net BFS +DFS알고리즘을 활용하면 되지만 조건이 굉장히 까다로운 문제입니다. 벽을 부순 후 벽을 기준으로 이동할 수 있는 영역이 몇 개 인지 탐색하는 문제입니다. 이것을 일일이 탐색한다면 시간 복잡도가 O((MN)^2)으로 매우 오래 걸리게 됩니다. 그래서 이동할 수 있는 영역에 대해서 그룹을 짓고 그룹의 크기가 담겨있는 vector를 만들어 줍니다. 그리고 해당 벽을 기점으..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 이 문제를 해결하기 위해 적용한 것은 에라토스테네스의 체, 투 포인터 알고리즘입니다. 에라토스테네스 체는 2의 배수(2는 제외, 소수이므로)부터 특정 수의 배수까지 걸러주는 알고리즘입니다. 출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 수학에서 에라토스테네스의 체는 ..