Algorithm120 최단거리 개념 및 문제 접근 방법 0. 개요 - 최단 거리 알고리즘은 그래프 탐색 알고리즘 중 하나이다. - 최단 거리 알고리즘의 종류와 개념 그리고 문제 접근 방법에 대해서 알아보자. 1. 최단 거리 개념과 종류 a) 최단 거리의 의미 - 최단 거리 문제에서 최단 거리는 다음 2가지 경우 중 하나에 해당한다. → 지나온 간선(edge)의 개수가 가장 적은 경로를 찾는 경우 (가중치가 없는 그래프) → 지나온 간선(edge)의 가중치(weight) 합이 가장 작은 경로를 찾는 경우 (가중치가 있는 그래프) b) 최단 거리의 종류 - 최단 거리 문제는 기본적으로 시작점과 도착점이 주어진다. - 시작점과 도착점을 기준으로 최단 경로(간선의 개수 또는 간선 가중치의 합)를 구하는 것이 문제의 핵심이다. - 시작점과 도착점의 구성 방식에 따라서.. 2022. 7. 18. DFS/BFS 개념 및 문제 접근 방법 0. 개요 - DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다. - DFS와 BFS가 어떻게 다른지, 언제 사용되는지 알아보자. 1. DFS(Depth First Search) a) DFS의 탐색 방법 - DFS는 다음과 같은 탐색 순서를 갖는다. - DFS는 하나의 방향을 결정하면 그 방향을 따라 끝까지 도달한다. ▶ 트리의 경우, 왼쪽에 위치한 노드를 우선적으로 탐색한다. ▶ 그래프의 경우, 가중치 또는 특정 기준을 따라 탐색 방향의 우선순위를 결정한다. - 위의 그림을 토대로 DFS는 다음과 같은 탐색 순서를 갖는다. ▶ 0번을 시작으로 왼쪽에 위치한 노드를 우선적으로 탐색한다. (0 ~ 3번 노드로 탐색) ▶ 3번 노드가 끝이므로 이전 단계로 돌아간다. (1번 노드로 돌아감) ▶ 1번 노드에서.. 2022. 7. 5. DP(동적 계획법) 개념 및 문제 접근 방식 0. 개요 - DP(동적 계획법)은 어떤 공식이나 특정 형태가 아닌 방법론에 가까운 개념으로써의 알고리즘이다. - 그래서 이론적으로 DP를 이해하기는 쉽지만, 문제에 적용하기가 쉽지 않다. - 필자가 그랬기에, DP 개념과 문제 접근 방식을 이해하기 쉽게 설명해보려 한다. 1. DP(동적 계획법)란? - DP에 대해 검색해보면 다음과 같은 대표적인 표현이 등장한다. → "하나의 큰 문제를 작은 문제로 나누고, 그 작은 문제를 해결하여 큰 문제의 답을 도출해내는 기법" → "작은 문제를 해결하는 과정에서 중복되는 연산을 수행하지 않는 기법" - 도대체 이게 무슨 말일까? - 피보나치 문제를 예시로 DP의 특징과 문제 접근 방식에 대해 알아보자. 2. DP 문제 접근 방식 - 피보나치 문제를 이용하여 DP .. 2022. 6. 20. LeetCode 77(Combinations, java) 0. 문제 https://leetcode.com/problems/combinations/ Combinations - 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 1. 문제 설명 - 문제에서 정수 n과 k가 주어진다. - 1부터 n까지의 수를 이용하여 중복 없이 k개의 짝을 이루는 모든 조합을 구하는 것이 문제의 핵심이다. 2. 문제 해설 a) 첫 번째 접근 - 이 문제는 전형적인 back tracking 문제다. - back tracking은 정답에 부합하는 .. 2022. 5. 6. LeetCode 994(Rotting Orange, java) 0. 문제 https://leetcode.com/problems/rotting-oranges/ Rotting Oranges - 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 1. 문제 설명 - 문제에서 이중 배열(grid)이 주어진다. - 이중 배열에는 빈 공간(= 0), 신선한 오렌지(= 1), 상한 오렌지(= 2)와 같은 3가지 값이 저장되어있다. - 상한 오렌지에 인접한 신선한 오렌지는 1분이 지날 때마다 상한다. - 인접한 오렌지 중 상한 오렌지가 존재하.. 2022. 5. 6. LeetCode 542(01 Matrix, java) 0. 문제 https://leetcode.com/problems/01-matrix/ 01 Matrix - 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 1. 문제 설명 - 문제에서 이중 배열(mat)이 주어진다. - 이중 배열의 원소 중 1이 입력된 위치를 찾고, 해당 위치부터 0까지의 최단 거리를 찾아낸다. - 최단 거리가 잘못 입력된 원소를 수정하여 올바른 값을 가진 이중 배열을 반환하는 것이 이 문제의 핵심이다. 2. 문제 해설 - 글쓴이는 이 문제를 풀기.. 2022. 4. 30. LeetCode 116(Populating Next Right Pointers in Each Node, java) 0. 문제 https://leetcode.com/problems/populating-next-right-pointers-in-each-node/ Populating Next Right Pointers in Each Node - 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 1. 문제 설명 - 문제에서 완전 이진트리(root)가 주어진다. - 모든 노드는 next 속성이 있는데, 이는 우측 노드를 가리키는 포인터 역할을 한다. - 모든 노드의 next 값은 nul.. 2022. 4. 29. LeetCode 617(Merge Two Binary Trees, java) 0. 문제 https://leetcode.com/problems/merge-two-binary-trees/ Merge Two Binary Trees - 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 1. 문제 설명 - 문제에서 이진트리 2개(root1, root2)가 주어진다. - 두 이진트리를 병합하여 하나의 이진트리를 반환하는 것이 문제의 핵심이다. 2. 문제 해설 a) 첫 번째 접근 - 이 문제는 두 트리의 노드를 탐색하여, 각 노드의 값을 병합하는 과정을.. 2022. 4. 28. LeetCode 695(Max Area of Island, java) 0. 문제 https://leetcode.com/problems/max-area-of-island/ Max Area of Island - 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 1. 문제 설명 - 문제에서 이중 배열(= grid)이 주어진다. - 이중 배열의 값으로 1과 0이 주어지는데, 0은 바다를 의미하고 1은 땅을 의미한다. - 상하좌우로 연결된 1의 값을 계산하여, 그중 가장 큰 값(= 가장 큰 땅)을 반환하는 것이 문제의 핵심이다. - 이 문제는.. 2022. 4. 27. 이전 1 2 3 4 ··· 14 다음
