명왕성의 공전기록

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 문제 풀이 방식 이분탐색에서 활용하기 위한 최소 범위와 최대 범위를 설정한다. 이..

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 문제 풀이 방식 먼저, 손님들에게 방을 배정하는 방식을 배열로 구현하려 했다. 이미 손님들을 배정한 방 중에서, 입력값으로 들어온 시간으로 방 배정이 불가능한 경우에는 방을 새로 배정해야 하므로 배열에 종료 시간을 추가하고, (이미 배정한 방 중 가장 빠른 퇴실 시간 + 청소 시간 입력값의 입실 시간인 경우) 이전에 선행되어야 하..