명왕성의 공전기록

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(..

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..

비트마스킹(Bitmasking)이란, 컴퓨터 과학에서 비트 연산을 사용하여 특정 비트의 상태를 확인하거나, 변경하는 기법을 말한다. 백준 알고리즘 문제를 풀다가, 다른 사람의 비트마스킹 문제풀이가 멋지다 느껴 공부하게 되었다. 비트마스킹의 장점 - bit 연산이기 때문에, 시간 복잡도에서 유리. (일반적으로 O(1)로 동작) - 다른 자료구조(배열 | 문자열)보다 메모리 사용량이 적음. 비트 연산자 종류 & AND 연산. 비교하는 비트가 둘 다 참일 때 만족한다. a = 6(110), b = 5(101) 일 때, a & b == 4(100) | OR 연산. 비교하는 비트가 둘 중 하나라도 참이면 만족한다. a = 6(110), b = 5(101) 일 때, a | b == 7(111) ^ XOR 연산. 비..