본문 바로가기

Algorithm175

[최단 경로 알고리즘 - 1] 다익스트라 알고리즘 * 최단 경로 알고리즘이란? 최단 경로 알고리즘이란 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로를 찾는 경우에는 다양한 종류가 있는데, 각 종류 별로 효율적인 알고리즘이 존재한다. '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등의 사례가 존재한다. 최단 경로 문제는 보통 그래프를 이용해서 표현하며 각 지점은 그래프에서 '노드'로 표현하고, 지점간 연결된 도로는 그래프에서 '간선'으로 표현된다. 최단 경로 알고리즘에는 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 존재한다. 이 중 다익스트라에 대해서 먼저 알아보자. * 다익스트라(Dijkstra) 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 .. 2021. 10. 31.
[LeetCode] 207. Course Schedule (swift, python) Course Schedule - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 위상정렬을 활용해서 해결할 수 있는 문제. 각각의 강의마다 선수 강의의 수를 저장하는 indegree 배열과 해당 강의를 듣고 나서 들을수 있는 후속 강의들을 저장하는 graph 배열을 만들어준다. 예제와 같이 [[1, 0]]과 같이 주어질 경우 각각의 배열에는 다음과 같이 저장된다. [0] : [1] → 0번 강의를 들어야 1번 강의를 들을 수 있다. [1] : [] → 1번 .. 2021. 10. 15.
[LeetCode] 200. Number of Islands (swift) Number of Islands - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 2차원 배열에 대해서 for문을 돌면서 맵이 "1"이고 아직 방문하지 않은 곳 이면 dfs를 돌아준다. [row][column]으로 이루어진 visited 배열을 만들어서 dfs를 돌 때 "1"인 곳에 방문이 되었으면 visited를 true로 체크한다. 한 번의 dfs 탐색을 하는 경우의 수가 섬의 개수를 의미한다. 코드 class Solution { func numIsla.. 2021. 10. 13.
[LeetCode] 797. All Paths From Source to Target (swift) All Paths From Source to Target - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 0번 부터 시작하여 n-1번까지 가는 경로를 모두 찾으면 되는 문제다. 입력 받은 graph에서 0번 꼭짓점과 연결된 꼭짓점부터 dfs를 탐색하도록 했다. // 0번 부터 탐색 시작 for vertex in graph[0] { dfs(vertex, [0, vertex], graph) } 비슷한 방식으로 dfs 함수 내에서 vertex와 연결된 꼭짓점으.. 2021. 10. 13.
[고득점 Kit (DFS/BFS)] 여행경로 (python, swift) 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 풀이 dfs를 이용해서 문제를 해결했다. 먼저 "ICN"부터 시작해서 전체 티켓을 체크한다. 티켓을 체크해가며 여행 경로를 담아두고 전체 티켓을 다 사용했을 때 현재 찾은 경로와 이전에 찾은 경로를 비교 하여 현재 찾은 경로가 알파벳 순서가 앞설 경우 찾은 경로를 변경한다. python은 단순히 이전에 찾은 경로 배열과 현재 찾은 경로 배열을 연산자 비교를 통해서 어떤 경로가 알파벳 순서를 앞서는지 알 수 있지만 swift에서는.. 2021. 10. 12.
[고득점 Kit (DFS/BFS)] 단어 변환 (python, swift) 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 풀이 문제에서 가장 짧은 변환 과정이라고 했으므로 최단 거리를 찾기 위해 bfs를 활용했다. 큐에는 총 3가지 정보를 넣어줬다. (현재 단어, 변환 횟수, 현재 단어의 인덱스)이다. 초기에는 인덱스에 -1을 넣어줬다. 인덱스의 경우는 checked 배열에서 사용하기 위해 넣어줬다. 주어진 words의 for문을 돌면서 현재 단어에서 다음 단어로 변환을 한 적이 있는지를 체크한다. 큐를 돌면서 target 단어를 만나면 .. 2021. 10. 11.

티스토리툴바