명왕성의 공전기록

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

https://www.acmicpc.net/problem/1654 해당 문제는 랜선의 갯수 N, 필요한 랜선의 갯수M 그리고 N개의 랜선 각각의 길이가 주어질 때, 필요한 랜선의 갯수 M을 만들 수 있는 최대 길이의 랜선을 구하는 문제다. 문제 풀이 방식 이분탐색에서 활용하기 위한 범위를 설정한다. 최소 범위는 0, 최대 범위는 주어진 랜선의 길이 중 가장 큰 것으로 초기화한다. (최대 범위가 랜선의 길이 중 가장 큰 값일 경우 가져갈 수 있는 랜선의 갯수는 최소가 되기 때문) 이후 while문에서는 중간값을 구한 뒤, 해당 중간값을 자를 랜선의 길이로 하여 만들 수 있는 총 갯수를 구한다. 그리고 이 갯수를 counts라고 할 때, 해당 값이 문제에서 필요로 하는 랜선의 갯수 m보다 크거나 같을 경..

https://www.acmicpc.net/problem/2805 해당 문제는 나무의 갯수 N, 필요한 나무의 길이 M 그리고 N개의 나무 각각의 길이가 주어질 때, 필요한 나무의 길이 M을 만들기 위한 최대의 절단기 길이를 구하는 문제다. 처음에는 문제의 장르가 이분탐색으로 설정되어 있음에도 어떻게 접근해야 할지 난해했다. 하지만 머리를 굴리다, 특정 길이로 잘랐을 때 얻을 수 있는 나무의 길이를 계산한 뒤 이를 활용하여 이분탐색의 범위를 조절하는 방식으로 해결했다. 문제 풀이 방식 이분탐색에서 활용하기 위한 범위를 설정한다. 최소 범위는 0, 최대 범위는 주어진 나무의 길이 중 가장 큰 것으로 초기화한다. (최대 범위가 나무의 길이 중 가장 큰 값일 경우 가져갈 수 있는 나무의 양도 최대가 되기 ..

https://school.programmers.co.kr/learn/courses/30/lessons/72411 해당 문제를 요약하면 다음과 같다. order 에는 문자열의 조합이 주어지고, course에는 만들고자 하는 조합의 크기가 주어진다. 여기서 문자열을 조합(combination)하여 course에 나타난 길이별로 가장 빈도가 높은 조합을 반환하는 문제다. (만약 빈도가 같은 조합이 여러 개라면 모두 출력한다.) 문제 풀이 방식 문자열을 course에 나오는 각 길이별로 조합하였을 때, 해당 빈도수를 담기 위해서는 객체를 활용하는 것이 효율적이므로, 이를 활용했다. 다만, '각 길이별 가장 높은 빈도의 문자열'을 추출해내는 것이 중요하므로, 길이별로 각각의 객체를 구현하는 것이 나중에 데이터를..

https://school.programmers.co.kr/learn/courses/30/lessons/155651 해당 문제는 어제 정렬을 활용하여 '가능한 회의의 횟수'를 출력하는 문제와 비슷한 문제지만, 다른 점이 있다면 이 문제의 경우는 '최소 객실의 수를 요구'한다. 2024.01.05 - [개발/algorithm] - 백준1931 - 회의실 배정 (정렬) Python 문제 풀이 방식 먼저, 손님들에게 방을 배정하는 방식을 배열로 구현하려 했다. 이미 손님들을 배정한 방 중에서, 입력값으로 들어온 시간으로 방 배정이 불가능한 경우에는 방을 새로 배정해야 하므로 배열에 종료 시간을 추가하고, (이미 배정한 방 중 가장 빠른 퇴실 시간 + 청소 시간 입력값의 입실 시간인 경우) 이전에 선행되어야 하..

https://www.acmicpc.net/problem/1931 해당 문제는 N개의 회의와 각각의 회의의 회의 시작 시간, 끝 시간이 존재할 때 회의실을 사용할 수 있는 최대의 경우를 출력하는 문제다. 문제 풀이 방식 먼저 회의실을 사용하지 않는 경우인 배열(result)을 기본값을 0(어떤 값이든 들어올 수 있는 값)으로 초기화하여 정의했다. 이후 회의실은 시간순에 따라 순차적으로 되기 때문에 정렬이 우선적으로 필요한데, 이때 끝시간이 짧은 것을 우선 순위로 두어야 한다. (만약 [1 5, 2 3, 3 4] 값이 입력값으로 주어질 때 시작 시간을 우선 순위로 두어 정렬할 경우, 회의를 한 번 밖에 할 수 없기 때문임.) 이후 배열에 들어가 있는 마지막 값(가장 최근 회의의 끝 시간)과 시작 시간을 비..

https://www.acmicpc.net/problem/18223 해당 문제는 최단 경로라는 그 말마따나, 최단 경로 문제를 해결하기에 용이한 다이크스트라 알고리즘으로 접근했다. 풀이 방식은 다이크스트라 알고리즘을 구현할 수 있다면 어렵지 않은데, 민준이가 곧장 마산으로 가는 경우가 민준이가 건우 위치를 경유하여 마산으로 가는 경우를 비교하여 답안을 출력하면 된다. 전체 소스 코드 import sys data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r') input_data = data_temp.read().splitlines() import heapq def solution (data) : arr = [list(map(int..

https://www.acmicpc.net/problem/7562 해당 문제는 가로 한칸, 세로 두 칸 혹은 가로 두 칸, 세로 한 칸씩 움직이는 체스판의 '나이트'가 목적지에 도착하기 위해 몇번을 움직여야 하는지 출력하는 문제다. 문제 해결 방식 최소 움직임을 요구하기 때문에, BFS 알고리즘을 활용해서 접근했다. queue 역할을 위한 배열을 선언한 뒤, (x좌표, y좌표, 거리)를 대입한 뒤 BFS 알고리즘을 통해 해결하면 되는데, 이때 나이트가 움직일 다음 위치만 신경써주면 된다. 전체 소스 코드 const fs = require("fs"); const input = fs .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt") ..