profile
ps 독학하면서 스스로에게 강의하며 정리 하는 곳, 지적과질문 환영
post-thumbnail

[LeetCode] 33. Search in Rotated Sorted Array

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

4일 전
·
0개의 댓글
·

[LeetCode] 275. H-Index II

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

2024년 3월 9일
·
0개의 댓글
·
post-thumbnail

[LeetCode] 400. Nth Digit

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

2024년 2월 24일
·
0개의 댓글
·
post-thumbnail

[LeetCode] 1011. Capacity To Ship Packages Within D Days

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

2024년 2월 23일
·
0개의 댓글
·

[LeetCode] 1079. Letter Tile Possibilities

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

2024년 2월 19일
·
0개의 댓글
·
post-thumbnail

[LeetCode] 44. Wildcard Matching

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

2024년 2월 18일
·
0개의 댓글
·
post-thumbnail

[LeetCode] 52. N-Queens II

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

2024년 2월 11일
·
0개의 댓글
·

[LeetCode] 733. Flood Fill

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

2024년 2월 9일
·
0개의 댓글
·
post-thumbnail

[LeetCode] 494. Target Sum

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

2024년 2월 9일
·
0개의 댓글
·
post-thumbnail

[LeetCode] 77. Combinations

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

2024년 2월 5일
·
0개의 댓글
·

[LeetCode] 60. Permutation Sequence

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

2024년 2월 1일
·
0개의 댓글
·
post-thumbnail

[LeetCode] 1863. Sum of All Subset XOR Totals

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

2024년 1월 17일
·
0개의 댓글
·
post-thumbnail

[LeetCode] 486. Predict the Winner

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

2024년 1월 10일
·
0개의 댓글
·

[LeetCode] 1545. Find Kth Bit in Nth Binary String

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

2024년 1월 10일
·
0개의 댓글
·
post-thumbnail

The Tower of Hanoi problem

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

2024년 1월 10일
·
0개의 댓글
·
post-thumbnail

[LeetCode] 11. Container With Most Water

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

2024년 1월 5일
·
0개의 댓글
·

[LeetCode] 1823. Find the Winner of the Circular Game

문제의 구조 자체가 Circular Linked List와 매우 유사하다. Node를 하나씩 순회하며 처음과 끝이 연결된 구조이고, Node를 삭제할 수 있다. 매 턴마다 K번씩 순회를 하는 과정을 N개만큼 반복한다. $O(KN)$Node 개수만큼의 공간이 필요하다.

2023년 12월 29일
·
0개의 댓글
·
post-thumbnail

[LeetCode] 713. Subarray Product Less Than K

Intuition contiguous한 subarray를 찾아야 하는 점에서 two pointer의 느낌을 받을 수 있었다. subarray의 양 끝을 조절하며 k와 곱을 비교해가면 문제를 풀 수 있을 것이라 생각했다. Approach subarray의 양 끝을 two

2023년 12월 16일
·
0개의 댓글
·
post-thumbnail

[LeetCode] 1444. Number of Ways of Cutting a Pizza

Intuition 문제를 좀 더 간단하게 생각해보면, k-1번 나눠서 그때마다 사과가 최소 1개 이상 있도록 만들어주는 문제이다. 그러기 위해 매번 선을 나눌때마다, 위아래 또는 양옆에 모두 사과가 있는 유효한 선인지를 검증하며 모든 경우의 수를 카운트하는 방식을 택했

2023년 12월 14일
·
0개의 댓글
·
post-thumbnail

[LeetCode] 1712. Ways to Split Array Into Three Subarrays

Intuition left, mid, right의 범위를 지정해주는 것이 우선적으로 필요하다. 한번에 지정하기는 힘들기 때문에, left를 먼저 지정하고 나머지 mid와 right를 지정하는 느낌으로 생각했다. Approach >본격적으로 시작하기에 앞서, 그때그때

2023년 10월 23일
·
0개의 댓글
·