Intuition 작은 문자열부터 원래문자열까지 하나씩 늘려가며 문제를 해결할 수 있을 것이라 예측했다. Approach 문제 재해석 >Def.) arri:=word1[:i]가 $word2[:j]로 convert 되는데 필요한 최소 cost 위와 같이 부분 문제를 정

Intuiton longest와 subsequence의 키워드로 DP풀이를 고려해볼 수 있다. text1과 text2의 문자를 하나씩 비교하며 같을 때마다 Longest Common Subsequence(이하 LCS)의 길이가 +1될 것이라고 예상했다. Approach

Intuition 임의의 두 문자가 같거나 다른지에 따라 관계식에 변화가 있을 것이라고 추정했다. Approach >Ai : [i:j]의 범위에서 Longest Palindromic Subsequence(이하 LPS) 위와 같이 문제를 정의한다. 길이가 1인경우에는

Intuition 각 원소들의 사용여부에 대해 모든 경우의 수를 따져본다. Approach [1,5,11,5] 의 배열을 예시로 들겠다. 전체합의 반인 11을 만들 수 있는지 확인해야한다. 첫번째 원소 1의 경우 사용하지 않게 되면 0을 만들 수 있고, 사용하면 1을

제곱수들만의 합으로 특정 숫자를 구성한다. 이때, 최소한의 숫자가 몇개인지 구하는 문제이다.LIS의 변형 느낌이다.이번 문제는 쉽기때문에 간단하게 요약 작성하였다1을 만들기 위해서는 1만 있으면 된다.2는 1+1, 0+2 모두 가능하지만, 문제 조건상 전자만 가능하다.

Intuition $argminx\sum\left\vert arri-x \right\vert$을 찾는 문제로 귀결된다. 이때 $x$는 중간의 적당한 어떤 값인 평균이나 중앙값 중 하나일 것이라고 추측했다. Approach 중앙값일 때 결과값이 최소화되고 중앙값에서 멀어

pushed의 원소들을 stack에 push하면서 popped의 원소들과 비교해본다.예시를 들어보겠다. sp는 stack pointer, pushp와 popp는 각각 push pointer, pop pointer다.1,2,3은 popp의 4와 일치하지 않으므로 모두 s

Intuition stack 에 여는괄호 '(' 를 넣으면서 닫는괄호 ')' 가 나올 때마다 경우에 맞게 처리해주는 방식으로 풀이했다. Approach '(()())' 을 예시로 설명해보겠다. 그림으로 표현해보면 아래와 같은 상황이다. sp는 스택포인터다. 여는 괄호

Intuition $O(log(m+n))$의 시간 복잡도 내에 문제를 해결해야 하기 때문에, 실제로 두 배열을 합치는 방식은 배제한다. 실제로 정렬을 수행하지 않으면서 median을 찾는 방법을 고안해야한다. 중앙값이 $N$개의 원소들을 정렬했을 때 $N\over2$

Intuition 문제에서 한번 회전된 배열이 input으로 들어오는 경우, 이진탐색을 적용할 수 없다. 즉, 회전되기 전의 배열을 구해야한다. Approach 회전되기 이전의 배열을 구하기 위해 회전이 된 기준점인 pivot을 이진탐색을 통해 탐색했다. >우선, numsSize가 1인 경우의 pivot은 0일수밖에 없고, 회전이 되어있지 않은 케이스는 ...

Intuition citations.length에 따라 h의 최댓값이 결정되는 점에 주목하여 이진탐색을 진행했다. Approach [3,3,100] 이라는 배열이 있을 때, 배열의 길이가 3이므로 h는 최소1, 최소3 의 범위 내에서 구할 수 있다. 1부터 3까지의

Intuition 이진탐색으로 output후보를 탐색하면서, 그때그때마다 해당 후보가 정답범위에 있는지를 체크하기로 했다. Approach 예를 들어 12는 10에서 2만큼 차이가 나고, 또 두자리수이기 때문에 10에서 1씩 커질때마다 digits는 2씩 증가한다. 따

Intuition 가능한 capacity를 이진탐색을 통해 후보를 정한 다음, 그때그때 그것이 가능한지 체크한다. 이때, 점점 capacity가 작아지도록 이진탐색하여 최솟값을 찾는다. Approach >어떤 시점 x부터는 capacity가 모두 가능해진다. 이 x를 찾기 위해 이진탐색을 진행할 것이다. 위의 표에서는 편의를 위해 최댓값을 $2^{31}$...

Intuition 같은 문자끼리는 구분하지 않으므로 개수를 기준으로 풀이하면 될 것이라 생각했다. Approach&Solution 교수님 풀이 예를 들어, 우리가 모든 문자를 다 써야하는 문제라면 단순히 팩토리얼 계산으로도 쉽게 해결할 수 있다. (특히, 이 문제의

Intuition '*'가 등장할 때마다 이를 분기로 삼고 재귀를 호출하는 방식으로 진행하면 되겠다고 생각했다. 그리고 이렇게 가능성 있는 케이스를 모두 살펴보고 한번이라도 가능한 케이스가 발견되면 true를 반환하면 될 것이라고 생각했다. Approach >문자열 s와p 둘 중 하나라도 끝날때까지 문자열을 순회한다. 이때, 두 문자가 같지 않은 경우는 따...

Intuition 퀸이 공격할 수 있는 가로,세로, 대각선 방향을 체크하면 되겠다고 생각했다. Approach 퀸을 배치할 때마다, 이전에 놓인 퀸 중 가로, 세로, 대각선 방향으로 공격할 수 있는 퀸이 존재하는지 확인해야 한다. >이를 위해 이 체스판 좌표의 특징(

Intuition 4-directionally라는 문제 조건에 맞춰, 재귀함수를 상하좌우로 호출하면 될 것이라고 생각했다. Approach >본격적으로 문제를 풀기에 앞서 2차원 배열을 반환하기 위한 세팅을 해줘야한다. 관련 설명은 [LeetCode] 77. Combinations에 기술했다. >특정 좌표에 문제에서 원하는 color로 색칠을 해주는 함수...

Intuition 배열을 순회하며 각 원소마다 +인 경우와 -인 경우를 모두 확인한다. Approach&Solution Time Complexity $\therefore O(2^n)$ 지적 및 질문 환영

Intuition 모든 조합의 경우의 수를 확인하기 위해 재귀로 접근한다. Approach 본격적으로 시작하기에 앞서 leetcode에서 2차원 배열을 반환받는 방식이 조금 특이하기에 이것부터 짚고 넘어가야한다. skeleton code에 int* returnSize와

Intuition 만들 수 있는 문자열의 경우의 수를 보는 문제인데, 중복이 안되는 것이다. Approach & Solution 중복 여부를 알기위해 mask 배열을 사용했다. Complexity Time Compelxity recursion의 과정을 tree구조로 표현했을 때, 첫번째 깊이에서 n 두번째에서 n-1개씩 n개 세번째 n-2개씩 n(n-1)...