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는 스택포인터다. 여는 괄호가 등장했으므로 스택에 여는 괄호를 의미하는 -1(임의숫자)을 push해준다. 이때 중요한...

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)...

Intuition 모든 subset의 xor을 체크해야하기 때문에 문제의 description에서 부터 모든 경우의 수를 확인해야 함을 알 수 있다. 이를 위해 재귀를 고려해보았다. Approach 각 원소는 있거나(1), 없거나(0) 둘 중에 하나의 경우이다. 앞

Intuition optimally하게 play하는 것이 이 문제에서 가장 관건이었다. 처음에는 greedy하게 시도했으나, optimal한 플레이를 할 수 없었다. 이를 재귀를 통해 모든 경우의 수를 끝까지 살펴보고 leaf node에서 top으로 올라오는 과정에서

Intuition n의 최댓값이 20이기 때문에, $S_{20}$까지의 모든 문자열을 만들어 확인해보는 것이 가능하지만, 문제의 description에서 base case와 점화식이 주어지므로 재귀를 고려해볼 수 있다. Approach $Sn$문자열은 1이 위치한 $

Description 하노이 탑 문제는 재귀로 풀이할 수 있는 대표적인 문제이다. 하노이 탑 문제를 탑 다운 방식으로 쪼개보면, >1. A막대의 가장 밑에 있는 disk를 제외한 나머지 disk들이 B막대에 위치하고 (일련의 과정들에 의해) >2. A막대의 가장 밑에 있는 disk가 C막대로 이동하고 >3. B막대의 n-1개의 disk들을 C로 이동시...

Intuition 투포인터 문제인 느낌을 잡게되고 Narrowing down 방식으로 접근하게 되면, 아래의 area를 최댓값으로 만드는 경우를 찾는 것이라는 것을 쉽게 알 수 있다. 다른 걸 불필요하게 볼 필요 없다. 뒤의 j-i는 1씩 동일하게 감소하므로 사실상 상수 취급한다. 신경써야할 부분은 min의 값이 변경되는 것인데, min의 값이 변경되려면...