명왕성의 공전기록

https://www.acmicpc.net/problem/14235 이 문제는 최대 힙을 활용하여 해결할 수 있는 문제다. 파이썬에서는 최대 힙을 제공하지 않지만, 선물의 가치를 음수로 저장하는 방법으로 최소 힙으로 최대 힙 구현이 가능하다. 이때 힙에 원소 저장 시 음수로 저장하고, 반환할 때 양수로 전환하여 반환한다는 것만 주의하면 된다. 전체 소스 코드 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) : int(data.pop(0)) pq, result = [],..

https://www.acmicpc.net/problem/2234 해당 문제는 좌표마다의 벽의 정보가 주어지고, 이를 활용하여 방의 개수, 가장 넓은 방의 넓이, 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 구하는 문제다. 예시와 같이 좌표 0,0가 11 인 경우를 예를 들면, 11은 1 + 2 + 8 로 이루어진 수며 이는 동쪽을 제외한 모든 벽이 막혀있다고 볼 수 있다. 그리고 11을 이진수로 바꾸면 1011 비트로 표현할 수 있는데, 이는 순서대로 '남쪽', '동쪽', '북쪽', '서쪽' 벽의 유무를 표현하고 있다. 따라서 좌표마다 비트마스킹을 하여 벽의 유무를 파악하고, 벽이 존재하지 않는 경로를 따라 DFS 알고리즘을 통해 해당 좌표가 가진 방의 크기를 구해나가면 된다. 풀이 과정..

https://www.acmicpc.net/problem/1194 해당 문제는 '0'에서부터 '1'로 향하되, 특정 소문자 알파벳인 열쇠를 지나쳐야 대문자 알파벳인 문을 통과할 수 있는 제약이 주어진 문제다. 따라서 길찾기에서는 BFS 알고리즘 로직을, 보유 열쇠 저장은 비트마스킹을 사용해야 메모리를 최대한 적게 사용하며 해당 풀이를 구현할 수 있다. 풀이 과정은 다음과 같다. 1. 입력값을 받아온 뒤, 이를 2차원 배열 크기인 n, m과 2차원 배열 matrix로 구분하고 시작점인 '0'의 좌표를 찾는다. def solution (data) : n,m = map(int, data.pop(0).split()) matrix = list(map(lambda x : list(x), data)) x,y = No..

https://www.acmicpc.net/problem/15787 해당 문제는 열차마다 20개의 승객 좌석이 주어졌고, 좌석은 승객이 탄 경우 | 타지 않은 경우로 나눌 수 있기 때문에 어제 포스팅한 비트마스킹 풀이로 접근했다. 2023.11.17 - [개발/Python | Java] - Python 문법 & 비트마스킹 풀이 과정은 다음과 같다. 1. 각 열차마다 승객의 상태를 확인하기 위한 배열을 선언한다. arr = list(map(lambda x : list(map(int, x.split())), data)) n, _ = arr.pop(0) # n은 열차의 갯수, _은 명령의 갯수 trains = [0] * (n+1) 2. 주어진 명령들을 처리하고 해당 배열에 업데이트해나간다. for cmd in..

https://www.acmicpc.net/problem/1261 해당 문제는 '벽을 부술 수 있는 미로'라는 점에서, 처음 접해보는 문제였다. 막힌 벽이 존재할 경우, 원하는 경로까지 갈 수 없기 때문에 일반적인 BFS 알고리즘으로는 접근이 불가능하다. 따라서, '부수는 벽'을 가중치로 하여 '최소 부순 벽'을 도출할 수 있게끔 다익스트라 알고리즘으로 접근했다. 풀이 과정은 다음과 같다. 1. 주어진 입력값을 분리시킨다. def solution (data) : X, Y = map(int, data.pop(0).split()) matrix = list(map(lambda x : list(map(int,list(x))) , data)) 다익스트라 알고리즘 2. 우선순위 큐(최소 힙)으로 사용할 배열 선언 ..

https://school.programmers.co.kr/learn/courses/30/lessons/72413 문제는 n개의 지점, 시작 지점 s, a의 도착 지점, b의 도착지점, [시작지점, 도착지점, 택시비]를 원소로 갖는 2차원 배열이 주어질 때, a,b가 s에서 출발하여 각각 도착지점까지 택시를 타고 간다고 했을 때의 최저 예상금액을 구하는 문제다. 예전에 프로그래머스 문제들을 탐방하다가 보았던 문제인데, 다익스트라 개념을 알고나서 바로 도전했다. 문제에서 나올 수 있는 A,B가 택시를 탈 때 나오는 경우는 아래와 같이 세 가지로 나눌 수 있다. # A->B 라면, A에서 B까지 가는 경우를 말한다. 1. A,B가 합승 없이 따로 목적지까지 가는 경우와 (X->A + X->B) # 이때, 둘..

https://www.acmicpc.net/problem/1916 해당 문제는 N개의 정점과, 그 도시들을 잇는 M개의 간선과 가중치가 주어질 때, 특정 두 정점의 최소 가중치(간선 | 경로의 비용 | 거리)를 구하는 문제다. 언뜻 너비우선탐색(BFS)와 비슷한 개념으로 풀이하면 될까 싶지만, 해당 문제는 다익스트라라는 개념으로 접근해야 한다. (개념에 대한 학습은 구글과 함께 했다. ^_^) 먼저 너비우선탐색 알고리즘과 다익스트라 알고리즘에 대해 비교하자면 다음과 같다. - 너비우선탐색 알고리즘은 가중치가 없는 그래프에서 최단 경로를 찾는 것에 적합. - 다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 것에 적합. - 너비우선탐색 알고리즘은 일반적으로 큐(Queue)로 구현. - 다익스..

https://www.acmicpc.net/problem/12789 문제는 입력값이 '순번'을 담고 있을 때, 해당 순번이 '스택'을 이용하여 오름차순으로 정렬할 수 있는지를 묻는다. (스택이 무엇인지는 해당 포스팅에서 따로 다루진 않는다.) 풀이 과정은 다음과 같다. 먼저, 스택을 통과하여 결괏값을 저장하기 위한 리스트 | 스택의 역할을 할 리스트를 선언했다. 이때, 결괏값 리스트는 오름차순으로 정렬될 것이므로 미리 0을 포함시켜두었다. 이후 반복문을 통해, 해당 값이 결괏값 리스트의 마지막 값보다 1 큰지 검증하여 (오름차순이므로), 해당 검증이 옳다면 결괏값 리스트에 추가 | 그렇지 않다면 스택에 추가한다. 이때 스택에 마지막에 추가된 값이 다음 결괏값 리스트에 들어가야 할 정렬된 값일 수 있으므로..