목록전체 글 (305)
백준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*+가 된다. 중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설..
백준15815 - 천재 수학자 성필 (스택) Python
https://www.acmicpc.net/problem/15815 해당 문제는 '후위 표기식'을 연산하는 문제다. 문제에서 말하는 설명을 이해하면 후위 표기식은 우선 순위에 따라 이미 정렬된 문자열을 다루는 것이기 때문에 abc*+ 의 경우, b * c 를 먼저 처리한 뒤 a + (b * c)를 하여 값을 연산한다고 볼 수 있다. 그리고 이는 스택으로 풀이가 가능한데, 빈 스택에 연산자가 들어오기 전까지 스택에 정수를 추가하다가, 연산자가 들어올 경우 스택 마지막에 위치한 두 정수를 꺼내 연산한 뒤 다시 스택에 넣어주는 과정을 반복하는 방식으로 풀이가 가능하다. 문제 풀이 방식 import sys data_temp = sys.stdin if sys.platform == 'linux' else open(..
백준2713 - 규현이의 사랑을 담은 문자메시지 Python
https://www.acmicpc.net/problem/2713 문제 자체가 어려운 편은 아니나, 구현 자체에 오랜 시간을 소요한 문제였다. 문자열 첫 번째에 '공백'이 나오는 가능성을 배제하고 첫 코드를 작성하여, 백준에 첫 질문을 만들게 한 문제기도 하다. 문제에서 하나의 테스트 케이스를 해결하는 과정을 요약하면 아래와 같다. 1. 공백 순서를 신경써서 행렬 높이, 행렬 너비, 문자열을 찾는다. 2. 행렬 높이 * 행렬 너비 크기의 2차원 배열을 만든다. 3. 주어진 규칙에 따라 알파벳을 정수 변환 후, 이진수로 변환한다. 이때, 하나의 알파벳이 이진 수 변환 시 길이는 5여야 하며, 이를 만족하지 않을 경우 0으로 채운다. 4. 이차원 배열을 문제에서 주어진 규칙에 따라 채운다. 5. 채운 이차원..
프로그래머스 Lv.3 - 거스름돈 (DP) Python
https://school.programmers.co.kr/learn/courses/30/lessons/12907 해당 문제는 각 돈의 종류로 특정 값을 만들 수 있는 모든 경우의 수를 출력하는 문제다. 이 또한 지난 포스팅과 같이 다이나믹 프로그래밍으로 풀이가 가능하다. 즉 위 문제 예시와 같이, n = 5원 / money = [1,2,5]라면 리스트 money에 있는 동전으로 만들 수 있는 0원 ~ 5원까지의 경우의 수를 구해나가며 5원을 만들 수 있는 경우의 수를 구할 수 있다. 먼저 경우의 수를 담을 리스트를 선언한다. 이때, 앞서 언급한 것과 같이 0원 ~ 5원을 만들 수 있는 경우의 수를 담아야 하므로 리스트의 길이는 n+1 이고 초깃값은 0이다. 하지만, 0원을 만드는 경우는 '모든 돈을 사..