명왕성의 공전기록

https://www.acmicpc.net/problem/1213 해당 문제는 좌우 대칭이 같은 문자열을 출력하는 펠린드롬 문제다. 문제 해결 방식 먼저 테이블에 각각의 알파벳의 갯수를 담은 뒤, 홀수의 수를 가진 알파벳이 두 개 이상이라면 펠린드롬을 만들 수 없기 때문에 실패 메세지를 출력했다. 만약 알파벳이 홀수인 경우가 없거나 하나만 존재한다면 펠린드롬을 만들 수 있는 경우이므로 먼저 정렬을 취한 뒤 앞 문자열을 생성하고 이를 반전시켜 문제를 풀이할 수 있었다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() ...

https://www.acmicpc.net/problem/17836 해당 문제는 좌표 (1,1)에서 좌표 (n,m)까지 이동하는 문제다. 이때 1로 이루어진 벽은 이동할 수 없다. 여기까지는 일반적인 미로찾기 문제와 비슷하나, 해당 문제에는 '검'이라는 존재가 등장하는데, 이 '검'을 획득한 경우 벽을 모두 부술 수 있다는 특징이 있다. 문제 풀이 방식 결국은 최단 거리를 구하는 것이 목표이므로, 내가 원하는 좌표까지의 수행 시간을 반환하는 BFS 알고리즘을 구현한 뒤 해당 로직으로 하여금 검을 획득한 뒤 목표 좌표까지의 거리와 검을 거치지 않고 목표 좌표까지의 거리를 비교하는 방식으로 답을 구했다. 이때 '검'은 벽을 무시하기 때문에, 검을 획득한 뒤 목표 좌표까지의 거리는 검까지의 거리 + 검의 좌표..

https://www.acmicpc.net/problem/3584 해당 문제는 테스트케이스마다 트리를 이루는 n개의 정점과 이를 이루는 간선, 그리고 정점 두 개의 번호가 주어질 때, 해당 두 정점의 최소 조상을 구하는 문제다. 문제 해결 방식 먼저 주어진 테스트케이스에 따라 tree를 구현한 뒤, 특정 노드에서부터 부모 노드를 찾아 기록한 뒤 기록한 내용은 뒤집어 반환하는 DFS 알고리즘을 구현했다. 이는 최정상 노드부터 자기 자신 노드에까지 도달하기 위해 거쳐온 노드들을 포함한 기록이기도 하다. 문제에서 요구하는 두 노드를 해당 알고리즘을 거치게 한 뒤 얻은 거쳐온 노드들의 기록 배열을 활용하여 비교하는 방식으로 문제를 해결했다. import sys data_temp = sys.stdin if sys..

https://www.acmicpc.net/problem/1967 해당 문제는 트리의 지름을 구하는 문제로, 노드와 노드 사이의 가장 긴 거리를 출력하는 문제다. 문제 해결 방식 트리로 이루어진 문제이기 때문에 너비우선탐색 알고리즘인 BFS 알고리즘으로 최정점인 노드 1에서의 가장 거리가 먼 노드를 찾은 뒤, 그 노드로부터 가장 먼 노드 사이의 거리를 구하는 방식으로 정답을 구했다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim() .split("\n"); function solution(data) { const n =..

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 알고리즘에 대해서도 설명한다. 다익스트라 알고리즘과 크루스칼 알고리즘의 차이점 적용 대상 다익스트라 : 주로 가중치가 있는 방향 그래프에서 사용되며, 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제에 적용 크루스칼 : 주로 가중치가 있는 무방향 그래프에서 사용. 최소 스패닝 트리(최소..