본문 바로가기

전체 글314

LeetCode 678 - Valid Parenthesis String (Medium) 문제 LeetCode - 678번 풀이 과정 주어진 문자열에서 괄호쌍이 올바르게 짝지어졌는지 판단하는 문제입니다. 다만 이 문제에서는 와일드카드(*) 가 존재하여 약간의 다른 방식의 접근이 필요합니다. 우선 이 와일드카드를 어떤 식으로 처리할지 결정해야합니다. 각각의 와일드 카드는 ( 혹은 ) 혹은 빈칸 으로 사용될 수 있으므로 현재 괄호 스택을 가지고는 어떤 방식으로 사용해야할지 알 수 없습니다. 따라서 해당 와일드 카드는 다음 세 가지 경우로 사용 방법을 나눌 수 있습니다. * 보다 앞서 발견된 ( 문자의 ) 역할 * 보다 늦게 발견된 ) 문자의 ( 역할 아무 역할도 하지 않는 빈칸 다시 말해 ) 문자에 대응되는 ( 가 이전에 스택에 존재하지 않을 경우 * 를 대신 사용하도록 하면 됩니다. 따라서 큐.. 2021. 3. 2.
LeetCode 1094 - Car Pooling (Medium) 문제 LeetCode - 1094번 풀이 과정 문제 분류는 탐욕 알고리즘 이지만 입력 값의 범위가 크지 않기 때문에 브루트 포스 로도 충분히 해결할 수 있는 문제였습니다. 우리가 찾아야 하는 것은 한 시점에 필요한 최대 capacity 입니다. 따라서 시간을 0.5 단위로 증가시키며 겹치는 최대 구간을 찾도록 합니다. 이때 0.5씩 증가시켜준 이유는 거리가 1 단위이기 때문입니다. (저와 같은 방법으로 구현한 분의 코드를 보니 시작 지점을 포함하고 종료 시간을 제외하여 1씩 증가시켜도 되도록 구현한 방법이 있었는데 그게 더 간단해보입니다.) 코드 /** * @param {number[][]} trips * @param {number} capacity * @return {boolean} */ var car.. 2021. 3. 2.
LeetCode 49 - Group Anagrams (Medium) 문제 LeetCode - 49번 풀이 과정 주어진 입력에서 Anagram을 찾는 문제입니다. Anagram은 순서에 상관없이 두 단어를 구성하는 문자의 종류와 개수가 동일한 관계를 말합니다. Anagram을 판단하는 직관적인 방법은 두 단어를 정렬한 뒤 같은 지 비교하는 것입니다. Javascript 에서 String 을 정렬하기 위해서는 spread 연산을 통해 Array로 바꿔준 이후 sort 함수를 사용합니다. 코드 /** * @param {string[]} strs * @return {string[][]} */ var groupAnagrams = function (strs) { const anagram = new Map(); for (let word of strs) { let sorted = [... 2021. 3. 2.
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.
Node.js 환경에서 네이버 Open API 활용하기 네이버 오픈 API란? 네이버는 개발자들이 활용할수있도록 다양한 기능들을 오픈 API 형태로 제공하고 있습니다. 이번 포스팅에서는 네이버 Open API에 대한 설명과 이를 활용할 수 있는 방법들에 대해 소개하겠습니다. 네이버 개발자 홈페이지에 가보면 다음과 같이 오픈 API를 정의하고 있습니다. 네이버 오픈API는 네이버 플랫폼의 기능을 외부 개발자가 쉽게 이용할 수 있게 웹 또는 SDK 형태로 공개한 기술들입니다. 쉽게 말해 네이버에서 외부 개발자들이 자사의 다양한 서비스들을 이용할 수 있도록 외부에 공개해놓은 것입니다. 저희는 해당 API를 사용하기 위해 주어진 형식에 맞춰 요청을 보내주기만 하면 됩니다. 네이버 개발자 홈페이지에 가면 활용 가능한 오픈 API들을 확인할 수 있습니다. 네이버 오픈 .. 2021. 3. 2.

티스토리툴바