본문 바로가기

Algorithm202

LeetCode 200 - Number of Islands (Medium) 문제 LeetCode - 200번 풀이 과정 섬의 개수를 세어주는 DFS 탐색 문제입니다. 간단한 문제이지만 히든 케이스 때문에 조금 헤맸습니다. LeetCode 문제는 깔끔하지만 입력 제한 사항이 명시되어있지 않은 경우가 있어서 난감한 상황이 종종 발생하는 것 같습니다. (입력으로 주어지는 grid 가 비어있는 경우가 존재할 것이라고 생각을 못했습니다..) 때문에 문제를 풀 때는 여러 edge case 를 고려하는 연습이 필요해보입니다. 코드 /** * @param {character[][]} grid * @return {number} */ var numIslands = function (grid) { const dx = [0, 0, 1, -1]; const dy = [1, -1, 0, 0]; if (.. 2021. 3. 2.
LeetCode 64 - Minimum Path Sum (Medium) 문제 LeetCode - 64번 풀이 과정 이동 방향이 고정되어 있는 상태에서 목표 지점에 도달하기 위한 최소 비용을 찾는 문제입니다. 각 칸을 하나의 정점으로 생각하면 이동 방향이 오른쪽 혹은 아래로 고정되어 있으므로 이를 그래프로 모델링하여 다익스트라 알고리즘이나 플로이드와 같은 최단 경로 알고리즘을 사용할 수도 있을 것 같습니다. 하지만 그보다 간단하게 동적 계획법 을 활용하여 문제를 해결할 수 있습니다. 만약 dp(x, y) = (x, y)에서 출발해서 (m, n)에 도달 할 수 있는 최단경로 라고 정의한다면 다음과 같은 점화식을 세울 수 있습니다. dp(x, y) = min(dp(x+1, y), dp(x, y+1)) + cost(x, y), 이때 cost는 현재 (x, y) 에서 필요한 비용 평.. 2021. 3. 2.
LeetCode 55 - Jump Game (Medium) 문제 LeetCode - 55번 풀이 과정 현재 위치에서 움직일 수 있는 거리가 주어져있고, 이를 통해 마지막 위치 도달 가능성을 판단하는 동적 계획법 문제입니다. 따라서 dp(x) = x에서 마지막 index에 도달 가능한지 여부 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. dp(x) = at least one for all dp(x + jump) , 이때 jump는 x에서 점프 가능한 거리 즉, 현재 위치에서 도달 가능한 위치 중 어느 하나라도 마지막 위치에 도달하는 경로를 가지고 있다면 현재 위치에서도 마지막에 도달할 수 있는 것입니다. Javascript 에서는 함수형 프로그래밍 기법에 기반한 메모이제이션 패턴이 있습니다. 이번 문제에서는 클로저 를 활용해서 Top-down 방식의 메.. 2021. 3. 2.
LeetCode 70 - Climing Stairs (Easy) 문제 LeetCode - 70번 풀이 과정 전형적인 동적 계획법 문제입니다. 현재 계단에서 올라갈 수 있는 칸의 수가 1~2 이므로 dp(n) = n번째 계단에서 마지막 계단에 도달하는 경우의 수 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. dp(n) = dp(n-1) + dp(n-2) 이는 피보나치 수열과 같은 형태를 가지고 있는 것을 알 수 있네요. 이번 문제에서는 보통 Javascript로 메모이제이션을 구현할 때 주로 사용하는 클로저 패턴이 아니라 다른 언어에서 사용하는 전역 스코프 변수를 미리 할당받아 사용하였습니다. 이후 문제부터는 Javascript 에 익숙해지기 위해 메모이제이션을 구현할 때 클로저를 활용할 예정입니다. 코드 /** * @param {number} n * @re.. 2021. 3. 2.
LeetCode 1 - Two Sum (Easy) 문제 LeetCode - 1번 풀이 과정 문제는 두 수의 합으로 target 값을 만들어내는 경우를 찾는 것입니다. 저는 브루트 포스 를 사용하여 모든 두 숫자 조합을 만들어본 다음 답을 찾아냈습니다. 문제 해설에서는 해시 테이블 을 사용하는 방법도 있었는데 이는 모든 수를 인덱스 값과 함께 해시 테이블 에 저장한 뒤 (target - 배열의 각 숫자) 에 해당하는 수가 해시테이블 에 존재하는지 여부를 따져 시간복잡도를 줄이는 방법도 제시하고 있습니다. 만약 (target - 배열의 각 숫자) 가 현재 해시테이블 에 존재한다면 그대로 답을 만들어 반환하고 존재하지 않으면 현재 인덱스의 값을 해시 테이블 에 추가해줍니다. 코드 브루트 포스 /** * @param {number[]} nums * @param.. 2021. 3. 2.
프로그래머스 Level 3 - 단어 변환 문제 프로그래머스 - 단어 변환 풀이 과정 시작 단어에서 목표 단어로 변형하는 최단 경로(비용)을 찾는 문제입니다. 각 단어는 최대 한 문자만 변경이 가능하고 주어진 리스트에 포함된 단어일 경우에만 해당 단어로 변환을 시도해볼 수 있습니다. 따라서 각 탐색마다 단어의 자리수를 하나씩 탐색하여 a to z 중 변환이 가능한 단어가 있는지 따져줍니다. 이때 Python 에서는 ord & chr 를 통해서 문자의 아스키코드 값을 활용할 수 있는데 문자열을 쉽게 처리하기 위해 활용하였습니다. 또한 중복된 변환을 피하기 위해 visit 은 딕셔너리로 선언하여 문자열 해싱 을 통해 이미 변환을 시도했던 단어인지 효율적으로 판단하도록 했습니다. 코드 from collections import deque def bfs.. 2021. 3. 1.

티스토리툴바