본문 바로가기

🏃 algorithm/leetcode93

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.

이전 1 ··· 13 14 15 16 다음

티스토리툴바