본문 바로가기
반응형

개발/Algorithm

 (98)
[백준] 특정 거리의 도시 찾기(python) 백준 온라인 저지, 특정 거리의 도시 찾기 TL;DR 다익스트라 알고리즘(Dijkstra Algorithm) 너비 우선 탐색(BFS) 문제 요약 1. 1번부터 N번까지 N개의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 2. 특정 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하라. 3. 최단 거리가 K인 도시를 오름차순으로 출력한다. 존재하지 않는다면 -1을 출력한다. - 1 : N개의 노드와 M개의 간선, 간선의 가중치는 1인 그래프로 생각할 수 있다. - 다익스트라 알고리즘을 사용하여 X 노드로부터 다른 노드들까지의 최단 경로를 확인한 뒤, 경로가 K인 노드들을 반환하면 될 것 같다. 입출력 형태..
[리트코드] Network Delay Time(python) 리트코드, Network Delay Time_네트워크 지연 시간 TL;DR 너비 우선 탐색(BFS) 다익스트라 알고리즘(Dijkstra Algorithm) 문제 요약 1. 1부터 n까지 노드가 있는 네트워크가 주어진다. 주어진 네트워크는 출발 노드, 도착 노드, 출발 노드로부터 도착 노드까지 걸리는 시간을 의미한다. 2. 주어진 k 노드로부터 신호를 전달한다고 했을 때 모든 n개의 노드들 도는데 걸리는 시간을 반환하라. 3. 만약 모든 노드를 순회할 수 없다면 -1을 반환하라. - 주어진 k 노드로부터 그래프에 존재하는 모든 노드를 순회할 때의 시간을 반환하면 된다. 이는 가장 k 노드로부터 가장 먼 거리의 노드까지 걸리는 시간을 반환하면 된다. - 모든 노드를 순회할 수 있다면 BFS에서 조회할 수 있..
[백준] 막대기(python) 백준, 막대기 TL;DR 스택(Stack) 문제 요약 1. 높이가 서로 다른(같을 수 있음) 막대기를 일렬로 세운 후 오른쪽에서 봤을 때 보이는 막대기의 개수를 알아내는 프로그램을 작성하라. - 일렬로 세운 막대기를 가장 오른쪽에서 봤을 때 보이는 막대기의 수를 반환하면 된다. - 가장 오른쪽에 있는 막대기보다 크기가 작은 막대기들은 보이지 않을 것이고, 큰 막대기들이 보일 것이다. 입출력 형태 - 주어진 예시에서 1번 막대기는 2번 막대기에 가려지고 4, 5번 막대기는 6번 막대기에 의해 가려져서 보이지 않는다. 따라서 보이는 막대기는 2, 3, 6번 막대기가 되어 총 3개가 된다. 풀이 막대기의 길이를 스택에 입력받는다. 가장 마지막에 들어오는 원소가 스택의 최상단에 위치할 것이다. 스택에서 하나씩 ..
[리트코드] Reconstruct Itinerary(python) 리트코드, Reconstruct Itinerary_경로 재구성 TL;DR 깊이 우선 탐색(DFS) 문제 요약 1. 출발지와 도착지가 [출발지, 도착지] 형태로 주어진 배열에 대해서 경로를 재구성해서 반환하여라. 2. 'JFK'에서 출발하기 때문에 모든 입력에는 'JFK'가 있는 것이 보장된다. 3. 존재하는 여러 경로 중 가장 최소의 알파벳 순서로 된 경로를 반환해야 한다. 4. 모든 티켓은 최소 하나의 유효한 경로가 존재하며, 하나의 티켓은 한 번만 사용해야 한다. - 모든 티켓을 사용하여 만들 수 있는 경로 중 가장 최소이며, 알파벳 순서로 돌아다니는 경로를 반환하면 된다. 입출력 형태 - 예시 1의 경우, 그림에서 주어지는 그림과 같이 순서대로 이동하는 것이 유효한 최소 알파벳 순서의 경로이다. -..
[백준] 고무오리 디버깅(python) 백준, 고무오리 디버깅 TL;DR 스택(Stack) 구현(Implementation) 문제 요약 1. 문제를 받은 상태에서 고무오리를 받으면 문제를 해결한다. 2. 문제가 없는 상태에서 고무오리를 받으면 두 문제를 추가한다. 3. 주어진 입력에 대해서 문제를 모두 해결하였으면 '고무오리야 사랑해'를 아니라면 '힝구'를 출력한다. - 문제와 고무오리가 입력으로 주어질 때 문제가 스택에 있고 고무오리를 입력으로 받는다면 스택을 비우는 방식으로 문제를 해결할 수 있을 것이다. - 스택이 비어있을 때 고무오리가 입력으로 들어온다면 두 문제를 스택에 추가해야 한다. 입출력 형태 문제를 모두 해결한 경우와 그렇지 않은 경우의 예시를 가져왔다. - 예제 입력 1에서는 (문제 - 고무오리), (문제, 문제 - 고무오리..
[백준] 수들의 합2(python) 백준, 수들의 합 2 TL;DR 투 포인터(two pointer) 문제 분석 1. N개의 자연수 배열에 대해서 i부터 j까지 연속된 수들의 합이 M이 되는 경우의 수를 구하는 프로그램을 작성하라. 2. 1
[프로그래머스] 행렬의 곱셈(python) 프로그래머스, 행렬의 곱셈 TL;DR 리스트(list) 문제 분석 1. 입력받은 2차원 행렬 arr1, arr2을 곱한 결과를 반환하는 함수를 완성하라. - 행렬의 곱셈을 구현하는 함수를 작성하는 것이 해결해야 하는 문제이다. 입출력 형태 - 행렬의 곱셈은 arr1의 행과 arr2의 열을 각각 곱하여 더하는 방식이다. - 예시 1의 결과의 첫 번째 줄만 살펴보면 행렬의 곱셈에 따라 (1 * 3) + (4 * 3) = 15가 되어 [15, 15]의 결과를 얻을 수 있다. 풀이 def solution(arr1, arr2): answer = [[] for _ in range(len(arr1))] for i in range(len(arr1)): # arr1의 행 tmp = [0] * len(arr2[0]) fo..
[리트코드] Subsets(python) 리트코드, Subsets_부분집합 TL;DR 깊이 우선 탐색(DFS) 문제 1. 주어진 중복이 없는 정수 배열 nums에 대해서 생성할 수 있는 모든 부분 집합을 반환하라. 2. 정답 배열은 복사된 부분 집합을 포함해서는 안되며 정렬 순서에는 큰 상관이 없다. 입출력 형태 - 주어진 숫자 배열로 만들 수 있는 모든 부분 집합을 반환하면 된다. - 공집합 또한 부분 집합의 일부이므로 포함시켜야 한다. 풀이 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: answer = [] def dfs(index: int, subsets: List[int]): answer.append(subsets) for i in range(index, l..

티스토리툴바