Longest Increasing Subsequence 문제 내용 주어진 Array에서 가장 긴 연속된 순서의 길이를 찾아라. Array내의 Position을 수정할 순 없지만, 중간에 있는 값을 삭제 할 수는 있다. 접근 방법 Brute Force 상위와 같은 배열이 주어졌을 경우 다음과 같이 Array를 찾을 수 있다. 9보다 작은 값이 이전에 있었는가? 없었다면 dp 1을 유지한다. 2보다 더 작은 값이 있는가? 없음으로 유지한다. 5보다 작은 값이 있는가? 2가 더 작았다. 그럼 2의 dp + 1을 해준다. 3도 같은 방법으로 dp의 값을 올려준다. 7의 경우 2,5,3 중 가장 높은 dp의 값에 + 1을 해준다. 101은 4가 된다. 18도 4가 된다. 위의 방식은 Time Complexity가..

Decode Ways 문제 내용 대문자 A부터 Z까지를 1부터 26까지의 숫자와 대응시켰을 때 주어진 숫자로 만들어 낼 수 있는 문자의 갯수는 몇개인가? 접근 방법 우선 Brute force 접근의 경우는 모든 경우를 분기 시키는 것이 가능하다. 만약에 '112'가 주어졌다고 하면 'aab','ai','kb' 이렇게 3개의 선택을 할 수 있다. 이 선택의 순서를 dfs방식으로 하게 되면, 최악의 경우 '11111111'

Arithmetic Slices 문제 내용 number array가 주어진다. 각 number의 연속적인 차가 동일할 경우 부분 집합의 갯수를 return해라 접근 방법 문제 내용을 보면 [1,3,5,7,9] [7,7,7,7] [3,-1,-5,-9] 가 동일한 차를 갖고 있다고 한다. 예를 들어서 [7,7,7,7]은 [0,0,0]의 차를 동일하게 갖고 있다. 이 array는 left : [7,7,7] right : [7,7,7] 전체 [7,7,7,7] 이렇게 3개의 부분 집합을 만들 수 있다. 이 부분 집합의 갯수를 다음과 같이 추상화 해보자. 부분 집합 갯수 구하기 차의 집합을 [a,a] 라고 생각해 보자. 위에서 [7,7,7,7]은 [0,0,0]으로 구성되어 있음으로 이 동일 갑을 'a'라고 치환한 ..

Shortest Path Visiting All Nodes 문제 내용 주어진 Node를 모두 Visite하는데 얼마의 step이 필요한가? 각 Node는 중복으로 방문이 가능하다. 접근 방법 개인적으로 이해하는데 시간을 오래 끌었다. Youtube나 google을 조회해 봐도 Floyd-Warshall 알고리즘이나 Dijkstra 를 이용한 방법이 검색되었다. 한마디로 이해하기 어렵고 주어진 시간내에 개발하기도 어려웠다. 그래서 Discussion을 찾아보는데 Smart BFS를 사용한 방법으로 본 문제를 풀었다는 이야기를 많이 보았다. 그래서 여기서 말하는 Smart BFS가 무었인지 알아보고 이를 통해서 문제를 풀어보고자 한다. BFS 접근 방법 BFS는 queue를 이용해서 접근 범위를 넓혀가는 방..

DFS 또는 Backtracking을 하거나 하는 방식으로 문제를 풀게 되면, 완전검색(Exhaustive Search)을 고려하게 된다. 처음 문제를 보았을때 이것이 완전검색을 원하는 것인지 아니면 최적의 P를 찾아낼 수 있는지를 판단하는 것이 중요하다. 가장 쉬운 판단법은 전제사항을 유심히 보는 것이다. 대부분 문제를 보면 숫자의 범위가 0에서 100,000이상의 범위를 갖게 된다. 그런데 이 문제만 이상하게 24, 32이런식으로 매우 작은 수로 범위를 갖는 경우가 나타난다. 이럴때는 완전검색을 고려해볼 필요가있다. 문제를 하나 풀어보면서 Masking과 DP를 어떻게 활용하는지 같이 알아보자. https://leetcode.com/problems/partition-to-k-equal-sum-subs..

Jump Game II 문제 내용 주어진 숫자 Array가 있다. 해당 Array index 0에서 출발한다고 할때, Jump가 가능한 범위는 arr[i]라고 할 수 있다. 예를 들어 arr[0]이 3이면 arr[1], arr[2], arr[3]으로 자리를 옮길 수 있게 된다. Array의 마지막 Index까지 갈수 있는 최소의 Jump 횟수를 구하시오. 접근 방법 DP를 이용해서 문제를 풀면 된다. 그런데 이렇게 간단히 최적화 되는 문제가 아니다 보니 글을 남기게 되었다. DP로 접근하고 이후 Greedy로 접근해 보겠다. DP 접근 다음과 같은 문제가 주어졌다고 생각해 보겠다. dp는 현재 index에서 마지막 index 7인 '2'까지 최소한의 jump를 기록 한다고 정의하자. 뒤에서 부터 접근해 ..

Different Ways to Add Parentheses 문제 내용 숫자와 +,-,* 3개의 Operation으로 구성된 문장이 있다. 임의로 ()

Super Egg Drop 문제 내용 N개의 달걀이 있다. K 층으로 이루어진 빌딩이 있다. 달걀은 해당 빌딩의 특정 층 F에서 깨지기 시작한다. N개의 달걀을 이용해서 F 층을 찾을 수 있는 가장 적은 시도 횟수를 갖는 방법 횟수를 찾아라 접근 방법 문제 자체를 이해하는데 굉장히 난해했다. 이 문제는 굉장히 오래된 문제인데, 아직도 Youtube나 Article을 보면 적당히 설명이 된 글이 많지 않았다. 어떤 글은 너무 쉬운 부분만 설명하거나, 또 어떤 글은 굉장히 어려운 말로 설명되어있었다. 우선 문제를 이해하자. 5층으로 이루어진 빌딩이 있고 달걀 1개가 주어졌다면 몇번 욺직여야 f를 찾을 수 있을까? 한개의 달걀로 f를 무조건 찾을 수 있는 방법은 5층에서 부터 2층사이에 달걀을 던지면 안된다는..

Edit Distance 문제 내용 두개의 word가 주어 진다. 예) 'abc', 'abd' 다음 3개준 하나의 Operation이 가능하다고 할때 delete : char 하나를 삭제한다 input : char 하나를 넣는다. replace : char 하나를 바꾼다. 두개의 word가 같아 질 수 있도록 최소한의 Operation 횟수를 구하라. 접근 방법 처음에는 이와 비슷한 문제인 2021.07.05 - [Problem Solving] - One Edit Distance 를 사용해서 Two Points를 이용한 해결 방법을 모색하였다. 그러나 최종적으로 이와 같은 접근법으로는 해결 할 수없다는 것을 알 수 있었다. 본 문제는 Levenshtein 알고리즘을 알고 있느냐에 따라서 쉽게 문제를 해결..