명왕성의 공전기록

https://www.acmicpc.net/problem/1253 해당 문제는 원소의 갯수와 원소가 주어질 때, 두 가지 원소의 합이 배열 내 원소 중 하나와 일치하는 경우가 몇 가지인지 출력하는 문제다. 최대로 등장할 수 있는 원소의 갯수가 2천 개이기 때문에, 이분탐색으로 접근했다. 문제 풀이 방식은 다음과 같다. 문제에서 주어진 수가 정렬되어 있다는 얘기가 없으므로 이분탐색을 위해 오름차순으로 정렬했다. 이후 배열 내 원소 중 하나인 n을 미리 선택한 뒤, 이분탐색으로 두 가지 수를 합쳤을 경우 n을 만족하는지를 파악하는 방식으로 로직을 구현했다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux"..

https://www.acmicpc.net/problem/1414 해당 문제는 최소 스패닝 트리 구현 시 불필요한 가중치의 총합을 구하는 문제다. 때문에 크루스칼 알고리즘으로 접근했다. 크루스칼 알고리즘 관련 포스팅 2023.12.14 - [개발/algorithm] - 크루스칼 알고리즘과 Find-Union 알고리즘 Python 문제 풀이 과정 주어진 가중치의 값이 영문으로 주어지기 때문에 숫자값으로 변환하고, 이 과정에서 만약 시작점과 도착점이 같다면 불필요한 가중치값으로 판단했고, 추가적으로 크루스칼 알고리즘 동작 시 시작점과 동작점의 의 root가 같다면 불필요한 가중치로 판단하여 결괏값에 포함시켰다. import sys data_temp = sys.stdin if sys.platform == 'l..

https://www.acmicpc.net/problem/1197 해당 문제는 그래프가 주어졌을 때, 최소 스패닝 트리(모든 정점이 연결된 트리)의 가중치를 구하는 문제다. 처음에는 다익스트라 알고리즘이나 플로이드 워셸 알고리즘으로 접근했다가 도저히 답을 찾지 못해 구글의 도움을 얻었고, 이때 알게 된 크루스칼, Union-Find 알고리즘을 적용하게 되었다. 크루스칼, Find-Union 알고리즘에 대한 설명은 아래 포스팅으로 대체한다. 2023.12.14 - [개발/algorithm] - 크루스칼 알고리즘과 Find-Union 알고리즘 Python 크루스칼 알고리즘, Find-Union 알고리즘을 통해, 각 노드들이 하나의 루트 원소를 가지게끔하여 최종적으로 최종적인 최소 비용을 구할 수 있었다. 소..

백준에서 그래프 관련 문제 중 어떤 노드에서 모든 노드를 거쳐 돌아왔을 때의 비용을 구하는 문제를 풀던 과정에 알게 된 크루스칼 알고리즘, Find-Union 알고리즘에 대해 소개한다. 내가 알고 있는 그래프 알고리즘 중 최소 비용을 구하는 알고리즘 중 하나는 다익스트라 알고리즘이 있는데, 해당 알고리즘과 먼저 비교해본 뒤, 크루스칼 알고리즘과 함께 크루스칼 알고리즘 구현 시 사용되는 Union-Find 알고리즘에 대해서도 설명한다. 다익스트라 알고리즘과 크루스칼 알고리즘의 차이점 적용 대상 다익스트라 : 주로 가중치가 있는 방향 그래프에서 사용되며, 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제에 적용 크루스칼 : 주로 가중치가 있는 무방향 그래프에서 사용. 최소 스패닝 트리(최소..

https://school.programmers.co.kr/learn/courses/30/lessons/12978 해당 문제는 마을의 갯수, [시작점, 도착점, 거리]를 요소로 하는 배열, 음식점에서 배달 가능한 거리라고 했을 때, 음식점이 있는 마을인 1번 마을에서, 몇 개의 마을에 배달이 가능한지 묻는 문제다. 문제 풀이 방식 특정 노드에서, 각 노드까지의 최소 가중치를 구해야 하므로, 다익스트라 알고리즘으로 접근했다. 다만, 다익스트라 알고리즘 구현 과정에서, 거리가 K를 초과하는 경우는 결괏값에 포함되지 않기 때문에 해당 경우는 연산하지 않는 방식으로 불필요한 연산을 최소화하려 했다. 다익스트라 관련 포스팅 2023.11.14 - [개발/algorithm] - 백준1916 - 최소 비용 구하기 (..

https://www.acmicpc.net/problem/1068 해당 문제는 각 노드의 부모 노드를 담은 데이터와 삭제할 노드가 주어진다. 그리고 삭제할 노드를 제외하였을 때의 자식의 개수가 0인 리프 노드의 갯수를 출력해야 한다. 문제 해결 방식 최대한 단순하게 생각했다. DFS을 통해 순차적으로 노드들을 방문하되, 각 노드가 가진 자식 수를 찾아 저장하는 방식을 택했다. (이때, 여기서 자식 수는 삭제할 노드를 포함하지 않은 수다.) 이후 노드가 가진 자식 수가 0인 경우(리프 노드인 경우)의 갯수를 헤아려 반환했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev..

https://www.acmicpc.net/problem/9934 해당 문제는 입력값으로 깊이값 K와 순회한 이진트리 데이터를 주고, 이를 활용하여 각 노드마다 2개의 자식 노드를 갖는 완전이진트리를 구성하여 출력하는 문제다. 문제 풀이 방식 완전이진트리라는 특징을 이용하여 최정점에서부터 다음 깊이의 두 노드들을 파악해가는 방식으로 진행했다. 먼저 [1,6,4,3,5,2,7] 라는 데이터가 주어졌을 경우, 가장 깊이가 0인 최정점 노드는 해당 배열 가운데에 위치한 3 이다. 이후 다음 깊이가 1인 노드의 경우를 파악하는 방식은 단순한데, 최정점 노드가 위치한 3의 좌우에 위치한 배열들에서 가운데에 위치하는 것이 깊이 0 노드의 자식 노드들이 된다. (즉, [1,6,4] 에서의 6. [5,2,7]에서의 2..

https://school.programmers.co.kr/learn/courses/30/lessons/43238 해당 문제는 입국하고자 하는 사람의 수 n, 각각의 심사관이 처리할 수 있는 시간을 담은 배열 times가 주어질 때, 걸리는 시간을 가장 최소화한 값을 구하는 문제다. 심사를 원하는 인물이 최대 10억 명, 걸리는 시간이 최대 10억 분이므로, 자연스레 이분탐색으로 풀이를 해야 한다. 추가적으로 아래는 위와 비슷한 문제지만, 백준에서 출제한 이분탐색으로 최댓값 구하는 문제니 필요하다면 참고하길 바란다. 2023.12.08 - [개발/algorithm] - 백준2805 - 나무 자르기 (이분탐색) node.js 문제 풀이 방식 이분탐색에서 활용하기 위한 최소 범위와 최대 범위를 설정한다. 이..