명왕성의 공전기록

https://www.acmicpc.net/problem/15989 해당 문제는 다이나믹 프로그래밍을 활요해야 풀이해야 시간제한 내에 풀 수 있는 문제다. 비슷한 문제를 풀이하고 풀이 과정을 포스팅한 링크를 남긴다. 2023.11.09 - [개발/algorithm] - 프로그래머스 Lv.3 - 거스름돈 (DP) Python 해당 문제의 접근 방법을 소개하기 앞서, 0부터 6까지 [1,2,3]을 활용해서 만들 수 있는 경우를 표로 나타내면 다음과 같다. 0 1 2 3 4 5 6 1을 사용 1 1+1 1+1+1 1+1+1+1 1+1+1+1+1 1+1+1+1+1+1 1,2를 사용 2 2+1 2+1+1 2+2 2+1+1, 2+2+1 2+1+1+1+1 2+2+1+1 2+2+2 1,2,3을 사용 3 3+1 3+1+..

https://www.acmicpc.net/problem/13565 해당 문제는 DFS 알고리즘에 대해 이해하고 있다면 쉽게 해결할 수 있다. 문제 풀이 과정 이 문제에서 유의할 점이 있다면 백준의 여타 다른 DFS 문제와 달리 모든 좌표에 DFS 알고리즘을 동작시키는 것이 아니다. outer side인 첫 번째 배열에서만 값이 이동가능한 좌표인 경우(0인 경우) DFS 알고리즘을 동작시킨 뒤, 마지막 배열에 방문 기록이 존재하는지 파악 후 답안을 출력했다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") .toString() .trim..

https://www.acmicpc.net/problem/2583 해당 문제는 DFS 알고리즘에 대해 이해하고 있다면 풀이가 쉽다. 문제 풀이 방식은 다음과 같다. 주어진 N,M의 값으로 기본값을 0으로하는 이차원 배열을 선언하고 주어진 직사각형의 좌표를 통해 해당 좌표 내에 포함된 영역을 1로 수정한다. 즉 0은 이동할 수 있는 공간, 1은 이동할 수 없는 공간으로 표현되고 있는 셈이다. 이후 추가적으로 방문 기록을 담기 위한 이차원 배열을 선언한다. DFS 알고리즘 로직을 깊이에 대한 값을 리턴할 수 있게 구현한 뒤에, 결괏값을 구할 수 있다. const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? ..

https://www.acmicpc.net/problem/16946 해당 문제는 DFS 알고리즘을 응용하여 해결할 수 있는 문제다. 풀이 과정은 다음과 같다. 1. DFS 알고리즘을 활용해, 벽이 아닌 방의 크기를 구해나간다. 이때, 방문여부 처리를 하여 이전에 방문했던 곳을 다시 방문치 않게 하며, 방 번호 변수를 선언하여 각 공간마다 구분할 수 있게 방 번호를 매기고, DFS 알고리즘 종료 시 리턴되는 방 번호(깊이)와 방 크기를 함께 저장한다. def solution (data) : n,m = map(int, data.pop(0).split()) arr = [list(map(int, list(x))) for x in data] # 방향 directions = [[-1,0],[0,-1],[1,0],..

https://www.acmicpc.net/problem/2468 해당 문제는 주어진 2차원 배열에서, 수심에 따른 안전 지역의 갯수를 구한 뒤 최댓값을 출력하는 문제다. 구역을 나누는 방식에는 DFS 알고리즘이 익숙하기 때문에 해당 알고리즘으로 접근했다. 풀이 방식은 다음과 같다. 먼저 수심에 따른 안전지대의 갯수를 구하는 것이므로, 수심의 범위를 제한하는 과정이 필요하다. 그리고 수심의 범위는 2차원 배열이 가진 최솟값과 최댓값 사이이기 떄문에, 해당 이차원 배열에서 나올 수 있는 수심 즉 깊이는 2차원 배열이 가진 최솟값 이상 최댓값 이하이기 때문에, 아래와 같이 미리 변수를 선언해두었다. n = int(data.pop(0)) matrix = [list(map(int, v.split())) for ..

https://www.acmicpc.net/problem/9694 문제는 거리를 가중치하여 한 정점(0)에서부터 특정한 정점(N-1)까지의 최단 거리를 찾고, 최단 거리가 존재하는 경우 최단 거리까지 경유하는 정점하는 정점들을 반환, 없는 경우 -1을 반환하는 문제다. 문제에서 나와있듯, 한 정점에서 특정한 정점까지의 최단 거리이기 때문에 다익스트라 알고리즘으로 접근했고, 다익스트라 알고리즘이 실행되는 과정에서 각 정점들의 방문 기록을 남겼다. 입력값으로 주어진 하나의 테스트 케이스가 처리되는 과정을 담은 소스 코드는 다음과 같다. (다익스트라 알고리즘에 관한 내용은 종종 다뤘기에 해당 포스팅에서는 생략하고 아래 링크로 대체한다.) 2023.11.14 - [개발/algorithm] - 백준1916 - 최..

https://www.acmicpc.net/problem/11404 해당 문제는 모든 도시에서, 각 모든 도시로 가야할 때의 최소비용을 요구하는 문제다. 따라서 지난 포스팅에서 언급한 플로이드-워셸 알고리즘을 활용하여 해결할 수 있다. 2023.11.22 - [개발/algorithm] - 프로그래머스 - Lv.3 순위 (플로이드-워셸) Python 문제에서 시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있다와 만약 갈 수 없는 경우 0을 출력하라는 주의 사항만 유의하면 된다. 전체 소스 코드 import sys data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r') input_data = data_temp.read()..

https://school.programmers.co.kr/learn/courses/30/lessons/49191 해당 문제는 선수의 수 n과 경기 결과를 담은 이차원 배열이 주어질 때, 정확하게 순위를 매길 수 있는 선수의 수를 리턴하는 문제다. 이때 선수 A,B,C가 있고, A가 B를 이기고, B가 C를 이겼다고 한다면, A가 C를 이긴다는 점을 주의깊게 보아야 한다. 이를 해결하기 위해선 먼저 경기 결과를 그래프로 구현한다. 이때, 모든 경로를 자신을 제외하고는 무한대로 설정했는데, 이는 아래 플로이드 워셸 동작 방식에서 설명한다. def solution(n, results): graph = [[float('inf')] * (n+1) for _ in range(n+1)] for i in range(..