목록전체 글 (308)
백준1194 - 달이 차오른다, 가자. (비트마스킹 & BFS) Python
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..
백준15787 - 기차가 어둠을 헤치고 은하수를 (비트마스킹) Python
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..
Python 문법 & 비트마스킹
비트마스킹(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 연산. 비..
백준1261 - 알고스팟 (다익스트라) Python
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. 우선순위 큐(최소 힙)으로 사용할 배열 선언 ..
프로그래머스 - lv.3 합승 택시요금 (다익스트라) Python
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) # 이때, 둘..
백준1916 - 최소 비용 구하기 (다익스트라) Python
https://www.acmicpc.net/problem/1916 해당 문제는 N개의 정점과, 그 도시들을 잇는 M개의 간선과 가중치가 주어질 때, 특정 두 정점의 최소 가중치(간선 | 경로의 비용 | 거리)를 구하는 문제다. 언뜻 너비우선탐색(BFS)와 비슷한 개념으로 풀이하면 될까 싶지만, 해당 문제는 다익스트라라는 개념으로 접근해야 한다. (개념에 대한 학습은 구글과 함께 했다. ^_^) 먼저 너비우선탐색 알고리즘과 다익스트라 알고리즘에 대해 비교하자면 다음과 같다. - 너비우선탐색 알고리즘은 가중치가 없는 그래프에서 최단 경로를 찾는 것에 적합. - 다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 것에 적합. - 너비우선탐색 알고리즘은 일반적으로 큐(Queue)로 구현. - 다익스..
백준12789 - 도키도키 간식드리미 (스택) Python
https://www.acmicpc.net/problem/12789 문제는 입력값이 '순번'을 담고 있을 때, 해당 순번이 '스택'을 이용하여 오름차순으로 정렬할 수 있는지를 묻는다. (스택이 무엇인지는 해당 포스팅에서 따로 다루진 않는다.) 풀이 과정은 다음과 같다. 먼저, 스택을 통과하여 결괏값을 저장하기 위한 리스트 | 스택의 역할을 할 리스트를 선언했다. 이때, 결괏값 리스트는 오름차순으로 정렬될 것이므로 미리 0을 포함시켜두었다. 이후 반복문을 통해, 해당 값이 결괏값 리스트의 마지막 값보다 1 큰지 검증하여 (오름차순이므로), 해당 검증이 옳다면 결괏값 리스트에 추가 | 그렇지 않다면 스택에 추가한다. 이때 스택에 마지막에 추가된 값이 다음 결괏값 리스트에 들어가야 할 정렬된 값일 수 있으므로..
백준1935 - 후위 표기식 2 (스택) Python
https://www.acmicpc.net/problem/1935 해당 문제는 피연산자 갯수 | 후위표기식 | 피연산자와 대응하는 값을 주고, 해당 식을 계산하는 문제다. 후위 표기식에 대한 설명 # 해당 문제에는 후위 표기식에 대한 설명이 없으므로 아래 설명으로 대체한다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다. 중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설..