멘타트 훈련

하나의 문자열을 쪼갰을때 각각의 파티션은 중복된 문자가 없어야함. 가장 많이 쪼갤 수 있는 경우의 수 . 출력은 쪼개진 각각의 파티션 문자 갯수 리턴.Input: s = "ab

주어진 숫자가 아래 휴대폰 키패드에서 어떤 문자의 조합이 될 수 있는지 출력하기. (주어진 숫자 자릿수는 0이상 4이하)keypadBacktracking 문제. 우선 각 키패드 숫자를 key로 하고 사용가능한 문자열을 value로 하는 해시 table생성 하고. 백트래

주어진 배열(nums)에서 가장큰 두 값으로 다음을 계산해서 리턴하기 (nums\[i]-1)\*(nums\[j]-1)Input: nums = 3,4,5,2 Output: 12https://leetcode.com/problems/maximum-product-of

2차원 배열이 주어지고 각 row에 해당하는 배열의 1갯수가 작은 순서대로 k개만큼 출력하기, 출력하는 값은 row의 index번호.배열을 sorting해도 되지만 그러면 무조건 O(N log N)이다. 문제가 sorting된 배열에서 가장큰 값 k개만 요구하므로, 모

배열에서 가장 큰값 두개(y >= x)를 꺼내서 아래와 같은 연산 반복, 배열의 크기가 1이 되면 남은 값 리턴 (0이되면 0리턴)y == x 이면 둘다 제거y > x 이면 y - x 값을 다시 배열에 추가.https://leetcode.com/problems

주어진 배열의 각 요소에 해당하는 랭킹(값 크기순)을 출력하라. (단 1,2,3위는 메달이름, 4위부터는 순위를 문자열로 저장.)더 좋은 해결책이 있을것 같으나, N번 heap_push(logN), N번 heap_pop(logN)하여, 총 O(N\*logN)으로 해결하

주어진 integer값를 다음의 조건에 부합하는 경우에 swap하여 가장 큰 수로 변환.각 자리수는 짝수 끼리 혹은 홀수끼리만 swap할 수 있음.https://leetcode.com/problems/largest-number-after-digit-swaps-

주어진 배열에 값을 add할때마다 배열에서 k번째로 큰 값을 리턴하라.https://leetcode.com/problems/kth-largest-element-in-a-stream/배열을 min heap으로 만든 뒤, heap_size를 k가 될때 까지 pop

주어진 배열에서 k 개의 subsequece 중에서 그 합이 가장 큰 조합을 출력하라. 기존 배열의 순서가 바뀌면 안됨.https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-su

주어진 배열에 포함된 요소로 어떤 set을 만든다고 가정. set의 요소를 배열에서 모두 지운다고할때, 배열의 사이즈가 절반 이하가 되는 set중 그 set 의 크기가 가장 작은것은? 가령 {3,5}의 set은 아래 arr배열을 2,2,7만 남기기 때문에 절반 이하가

좌표평면에 좌표들이 주어질때, 원점에서 가장 가까운 순서대로 k개 만큼 출력하기.heapifyhttps://leetcode.com/problems/k-closest-points-to-origin/크기순으로 k개만큼만 출력하는 전형적인 heap(우선순위큐)문제.

m x n 2차원 배열이 있을때 각 행에서 1개씩 뽑아서 더한 값의 경우의 수 중 K번째로 작은 값을 구하기.https://leetcode.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows

후위 표기법으로 수식을 계산하기.https://leetcode.com/problems/evaluate-reverse-polish-notation/이전에 구현했던 구현 방법 그대로 사용 가능 -> 후위 표기법 스택 계산기

Stack Easy 문제 풀이 수식에서 가장 많은 괄호 Depth갯수 구하기.https://leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/

3개의 돌더미가 주어지고, 매 게임마다 두개의 돌더미에서 돌을 하나씩 뺄때, 두개이상의 돌더미가 0개가 되는 최대 게임 횟수.https://leetcode.com/problems/maximum-score-from-removing-stones/매 게임마다 가장

주어진 배열값을 랭킹으로 변환해서 리턴하라 (크기 작은 순)https://leetcode.com/problems/rank-transform-of-an-array/링크드 리스트 기반 해시테이블을 생성해서 풀었는데 많이 느리다. (Runtime: 249 ms, f

주어진 배열에 동일한 요소 갯수가 많은 순서대로 k개 출력.https://leetcode.com/problems/top-k-frequent-elements/해시테이블과 heap을 모두 직접 구현해 풀어서 intense 했다. Leetcode 에서 100번째로

i번 사람이 포함된 그룹 크기가 groupSizesi 라고 할때, 각각의 i사람들을 그룹으로 나눠서 리턴하라. 아래 예에서 i=0 인 사람의 그룹크기는 3이어야함.https://leetcode.com/problems/group-the-people-given-t

주어진 두 정렬된 링크드 리스트를 합치기(정렬된 상태로)

https://leetcode.com/problems/number-of-equivalent-domino-pairs우선 10x10 해시테이블을 생성하고 주어진 배열에서 각 요소갯수를 모두 더한다. 해당 테이블에서 세가지 경우의 수 별로 값을 calc() 해서 모

주어진 두 문자열이 isomorphic 하면 true 아니면 false 리턴. (문자열을 구성하는 charactor는 모든 ascii문자)https://leetcode.com/problems/isomorphic-strings/처음에 이해가 안가서 해설들을 참고

문제 주어진 문자열 집합에서 패턴과 isomorphic한 문자열만 리턴하라. 문제를 이해하기 위해 이 문제의 쉬운버전인 Leetcode-205.-Isomorphic-Strings 문제를 사전에 참고. https://leetcode.com/problems/find-an

isomorphic 패턴 문자열과 문자열집합이 isomolphic한지 체크하는 문제. 비슷한 문제로는 다음의 문제가 있고. 여기서는 'a' -> "dog" 문자가 문자열과 매핑되어야하는점이 다르다. https://leetcode.com/problems/word

Easy문제 풀이, 푸는 순서대로 상단에 업데이트피보나치 수열의 합 구하기

order로 주어지는 문자는 제시된 순서를 유지하도록 s를 sorting하기. order에 존재하지 않는 문자는 어디 위치해도 상관없음.https://leetcode.com/problems/custom-sort-string/s의 문자빈도수를 table26 에

주어진 문자열에서 거꾸로 읽어도 동일한 문자열이 되는 palindrome 이 k가 만들어질 수 있는지 확인하는 함수를 작성하라.https://leetcode.com/problems/construct-k-palindrome-strings/아래와 같은 성질을 구현

주어진 matrix의 값이 0인 요소의 동일 행과 열을 모두 0으로 만들어라hashtablehttps://leetcode.com/problems/set-matrix-zeroes/행과 열의 각각 table을 만들고 배열값이 0인 i,j를 표기. 배열을 순회 하면

Easy문제들, 푸는 대로 상단에 업데이트이 프로그래밍 언어는 한개의 변수에대한 4개의 연산자만 지원하는 언어다. 프로그램이 주어질때 결과값을 계산하라.간단한 프로그래밍 언어라는게 재미있긴한데, 좋은 문제같지는 않음.

주어진 배열에서 k번째로 큰 값을 구하기https://leetcode.com/problems/kth-largest-element-in-an-array/k번째로 크거나 작은값은 전형적인 heap문제이다. 정렬을 하면 O(nlogn)에 풀수 있는데, heap을 사

주어진 두 링크드 리스트는 각각 10진수 수를 나타낸다(역방향) 가령 2,4,3는 342를 나타냄.두 값의 합을 리스트로 리턴하라.list

edge가 주어질때, source -> destination 에대한 경로가 존재하면 true 아니면 false.https://leetcode.com/problems/find-if-path-exists-in-graph/2차원배열로 graph map을 생성하니,2

주어진 문장들에서 가장 많은 단어를 갖는 문장의 단어수는?

1 ~ n까지 값중에 isBadVersion(i) 함수를 호출해서 처음으로 bad값이 나오는 인덱스를 리턴하기.https://leetcode.com/problems/first-bad-version/left와 right가 같아질때까지 루프를 반복. while (

거꾸로 읽어도 동일한 수를 palindrome이라고 한다. 주어진 수가 palindrome인지 확인하라.

로마자 표기를 10진수 값으로 리턴하기.https://leetcode.com/problems/roman-to-integer/I can be placed before V (5) and X (10) to make 4 and 9. X can be placed bef

주어진 배열의 subarray 합중 가장 큰 합은? (subarray는 연속된 배열)아이디어가 안떠올라서 N^2으로 풀었는데, 답은 맞았으나 Time Limit Exceeded됨.첨엔 이게 왜 되나 싶었음. sum이 음수가 될바에는 음수중 가장 큰값 하나만 max에 저

다음을 만족하는 Tribonacci 수열이 존재할때 값을 계산하기.https://leetcode.com/problems/n-th-tribonacci-number/재귀를 배울때 항상나오는 피보나치 + DP 문제와 동일. dp\[] 배열에 결과를 저장하면 함수콜을

각 계단을 오르는 비용을 나타내는 배열이 주어진다. 계단은 1칸 혹은 2칸씩 오를 수 있다. 최소의 비용으로 꼭데기 까지 오른다면 얼마가 드는가?형식의 min/max 를 구하는 재귀 + DP 문제.cost 배열이 10, 15, 20 이렇게 주어졌을때 점화식이 dp\[n

계단을 한칸 혹은 두칸씩 오를 수 있다고 할때, n번째 계단을 오르는 경우의 수는?https://leetcode.com/problems/climbing-stairs/유사문제746\. Min Cost Climbing Stairs계단을 오르는 최소비용값 이라는 차

배열이 주어지고 각 링크드리스트 노드를 나타낸다. pos는 마지막 노드의 next 포인터 위치를 나타낸다. -1 이면 next 포인터는 NULL이다. 이 링크드리스트가 사이클을 갖는지 아닌지 판단하라.linked list굉장히 흥미로운 문제였다. 노드를 순회하면서 노드

주어진 배열이 10수의 각 자릿수를 나타낼때, 1을 더한 값을 배열로 리턴하라. 거의 if/else 케이스를 생각해 풀었기 때문에 좋은 문제는 아닌듯. 모든 자릿수가 9일때만 1을 더했을때 자리수가 늘어나는 성질 이용. 100%

L과 R로만 구성된 문자열이 주어진다. L와 R의 갯수가 동일한 문자열이 balanced한 문자열이라고 할때, 주어진 문자열을 쪼갰을때 모든 문자열이 Balanced되는 경우의수 중 최대 갯수는?최대로 쪼개는 갯수이니, 앞부터 가장 작은 문자열이 밸런스가 맞으면 ret

주어진 수의 각 자리수를 제곱해서 모두 더하고, 그 값을 또 계속 반복할때, 1이 나오면 true. 아니면 false 리턴하기.https://leetcode.com/problems/happy-number/1을 찾는건 쉬운데 오히려, 1이 안나올때 어떻게 반복문

트리의 left, right를 서로 바꾸는 함수를 구현하라.Invert Binary Treeroot->left 에는 계산이 끝난 recursion(root->right)를 저장. root->right에는 recursion(root->left) 저장.

배열값과 target 값이 주어질때, 배열의 서로다른 두 index의 값을 더해서 target값이 나오는 index쌍을 구하라. brute force배열값을 먼저 해시테이블에 저장하고, 배열을 다시 순회하면서 target이 되기 위한 나머지값이 해시테이블에 존재하는지

0/1로만 구성된 Tree에서 root부터 leef까지 이어지는 노드순서가 이진수값을 나타낸다고 할때, 주어진 트리에서 나타낼수 있는 모든 값의 총 합을 구하라.

다음과 같은 Pascal's Triangle 결과를 출력하기pascal trianglehttps://leetcode.com/problems/pascals-triangle/

Pascal's Triangle의 주어진 rowIndex값 번째의 행을 리턴하기https://leetcode.com/problems/pascals-triangle-ii/1번문제에서는 공간복잡도가 N^2였는데 이번에는 O(N)에 해결됨.

idx가 날짜고, 값이 가격인 배열이 주어질때, 가장 쌀때 사서 비쌀때 판다고 할때 가장큰 수익은?

첫번째 문자열이 두번째 문자열의 subsequence인지 판단하기https://leetcode.com/problems/is-subsequence/

숫자num이 주어지고 k길이가 주어질때, 숫자를 k만큼 쪼갠 수가 주어진 num의 몫이 될수 있는가? 있다면 몇개 존재하나?

동전 종류가 주어질때, 동전을 조합하여 amount 값을 만들 수 있는 동전의 최소 갯수는? (동전 갯수는 무제한 제공된다고 가정)https://leetcode.com/problems/coin-change/

mxn 크기의 맵이 주어질때 좌상단에서 우하단으로 갈수있는 모든 경우의 수를 구하기.unique pathshttps://leetcode.com/problems/unique-paths/우선 각각의 위치는 왼쪽칸 + 윗칸 값이 될것이다. 그리고 가장 코너칸의 값은

Pramp로 첫 mock 인터뷰 경험.x,y,z 좌표와 경로가 주어질때, z좌표가 고도가 높아지면 에너지를 소모하고 고도가 하강하면 에너지를 얻는다. 가령 아래 예에서는 고도가 10에서 0으로 떨어질때 총에너지가 +10이 될거고, 다시 6으로 올라갈때 총 +4(10-6

오늘 pramp mock인터뷰 해보면서 알게된 사실. (https://velog.io/@soopsaram/Pramp-Drone-Flight-Planner)나는 인터뷰같은 압박의 상황에서 코딩시 array indexing에 대해 더욱 햇갈려한다는 사실을 깨달았다

배열이 주어지고 서로다른 두 인덱스 i, j가 있을때 다음의 조건을 만족하는 i,j가 있다면 true 리턴nums\[i] == nums\[j] abs(i - j) <= k.문제를 다시 풀어보면 i, j의 간격크기가 k 이하 일때, 배열값이 서로 같은 요소가 있는지

주어진 배열에서 3번째로 큰 수를 리턴하라.

주어진 배열에서 0인요소를 가장 우측으로 옮겨라. (0을 제외한 수들의 순서가 유지되어야한다)https://leetcode.com/problems/move-zeroes/

주어진 수를 뒤집어서 리턴하라 만약 결과가 \[-2^31, 2^31 - 1] 범위를 벗어나면 0리턴https://leetcode.com/problems/reverse-integer/자릿수 계산하는 패턴 익히기

다음의 규칙으로 압축된 배열이 있다. 압축을 풀어라?\[갯수, 값, 갯수, 값 ...] 가령 아래의 예제는 2가 1개, 4가 3개 로 압축해제할 수 있다.

수조와 칸막이가 주어지고 두개를 선택한다고할때 가장 많은 물을 담을 수 있는 경우, 얼만큼의 양을 담을 수 있는가? 가령 아래의 경우, 최대인경우 높이 7 너비 7로 49만큼의 양을 담을 수 있다.between height1 ~ height7 -> 7 \* 7 = 49

문자열이 주어질때, 반복된 문자가 없는 가장 긴 substring의 길이를 구하라.sliding window 로 해결. (discussion참고) left/right 두개의 포인터를 이동하면서 window의 사이즈를 변경하여 체크.해시테이블에 빈도수를 저장. tabl

9개의 배열값이 주어짐. 그중 7개의 합이 100이 되는 요소를 정렬해서 출력하라.https://www.acmicpc.net/problem/2309입력출력2개를 선택하는 모든 경우의수 (2개를 제외하고 모두 더했을때 100이 나오는지 체크)

문자열이 주어질때 substring중 가장 긴 길이의 palindrome 문자열(좌/우에서 읽어도 동일한 문자열)을 구하라. https://leetcode.com/problems/longest-palindromic-substring/문자열을 처음부터 끝까지 순

n이 주어지면 n만큼의 정상적 괄호형태의 모든 조합을 리턴하라.괄호가 나열되는 모든 경우의 수 중에서 정상적인 괄호만 추출하기.

주어진 배열 요소의 모든 순열(순서대로 나열하는 경우의수)을 출력.정확히 std::next_permutation 사용.

훔칠수 있는 돈이 기록된 배열이 주어진다. 인접한 두 집을 한꺼번에 훔치면 경보가 작동해 잡혀간다. 잡혀가지 않고 최대로 많이 훔칠수 있는 금액은? (인접한 집은 배열의 바로 다음요소)https://leetcode.com/problems/house-robber

주어진 배열의 subsequence중에 값이 계속 증가하는것중 가장 긴 subsequence의 길이는?https://leetcode.com/problems/longest-increasing-subsequence/f(n) = max(f(n-1) ~ f(0)) (

https://www.tryexponent.com/courses/software-engineering/data-structures/arrays?ref=pramp&utm_source=pramp&utm_campaign=pramp_question_recommenda

문자열이 담긴 백터가 주어질때 모든 문자열에 공통으로 포함된 가장 긴 prefix 문자열을 찾기. (prefix: 문자열 처음부터 시작)idx를 하나씩 늘리며 모든 문자열이 같은지 체크. (이것보다 시간복잡도를 더 빠르게 할수 있나?)

정렬된 배열이 주어진다. 이것을 height balanced 이진탐색 트리로 변환하라.https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/배열이 정렬된점 때문에 재귀함수 내에서 ro

문제 해결 트리의 root->left를 invert_tree 해버리고, 그 후에 root->right 동일한지 dfs해서 비교하면 됨.

주어진 문자열이 Palindrome(좌우에서 읽어도 동일)인지 확인https://leetcode.com/problems/valid-palindrome/알파벳을 문자열을 모두 소문자로 바꾸기std::tolower() 사용. 한 char를 변환가능.string 문

brute force로 풀어봄. 배열값중 하나씩 조건을 만족하는 값으로 바꾼뒤, 배열을 순회하면서

주어진 BST에서 k 번째로 작은 값을 출력하라.BST이기 때문에 정렬이 되어있을것이고 inorder 순회를 하여 k번째 값을 출력하면 된다. 추가로 dfs내에서 어떤 리턴값을 저장해야한다면, 어렵게 dfs함수의 리턴값으로 하지말고 그냥 매개변수 하나에 배열이나 벡터를

다음동작의 stack을 구현하라. 단 getMin()함수의 시간복잡도는 상수시간이어야한다. getMin() 함수가 문제인데, 무지성으로 생각하면 모든 스택값을 리니어하게 탐색하면 된다. 그러면 O(1)을 만족할 수 없다.heap 자료구조를 추가로 사용해야하나 생각이 들

주어진 배열에서 세개의 수를 골라서 더했을때 0이 되는 모든경우의 수는?배열값을 하나씩 선택하고 선택한 값을 제외한 값으로 two sum을 구하면 됨.\-(num\[i] + num\[j]) 값이 해시테이블에 존재하면 찾는것임.해시테이블을 사용해 시간 복잡도는 O(N^2

링크드 리스트의 head노드가 주어진다. 해당 링크드리스트의 뒤에서 n번째 노드를 삭제하라.노드를 순회하면서 매노드마다 n번 이동해서 node->next가 NULL이면 해당 노드를 제거하면 된다.

주어진 singlely 링크드 리스트의 노드가 palindrome인지 확인하라.https://leetcode.com/problems/palindrome-linked-list/ 일단 리스트의 배열값을 추가 배열에 저장하고 그 배열값이 palindrome인지 확인

문제 주어진 이진트리의 Diameter(트리 내 존재하는 두 노드의 path중 가장 긴 path)를 구하라 https://leetcode.com/problems/diameter-of-binary-tree/ 해결 처음 접하는 유형의 문제였다. 단순히 루트노드에서 왼

엑셀표에 열이름을 10진수로 계산하라.결국 26개의 서로다른 문자로 수를 표현하는것과같다. (26진수)따라서 "ABC"의 경우 공식은 아래와 같다. 그리고 A~Z 문자는 1~26으로 바꿔서 계산하면 된다.(A \* 26^2) + (B \* 26^1) + (C \* 26

주어진 링크드 리스트에서 한 pair씩 swap해라. https://leetcode.com/problems/swap-nodes-in-pairs/first, second노드를 지정하고 swap. 이것을 두칸식 반복하는게 기본 아이디어. 어려웠다ㅇㅇ. 비슷하게는

주어진 이진 트리를 링크드 리스트로 변환하라. 리스트의 순서는 트리의 preorder 순회 순서이다. https://leetcode.com/problems/flatten-binary-tree-to-linked-list/구조를 보면 root->right에 gen

주어진 링크드 리스트를 k 번 rotate시켜라.한번 rotate하는건 쉽다. 링크드리스트의 맨 마지막 노드 (node), 그리고 직전노드 prev라고 할때, 아래와 같이 하면된다.이걸 k 번반복. 총 시간복잡도는 O(N^2)가 된다. 역시나 TLE 발생 (12 / 2

값이 정렬되어있는 배열이 있다. 그런데 특정 pivot 인덱스를 기준으로 회전되어있다. 이런 배열에서 target값의 index를 찾아라. 단 시간복잡도는 O(logN)을 초과할 수 없다.https://leetcode.com/problems/search-in-

중복된 값이 있는 정렬된 배열이 있을때, target값이 존재하는 범위를 리턴하라. 없다면 -1,-1을 리턴.단, 시간복잡도는 O(log N)을 초과할 수 없다.Leetcode 에서 200번째로 해결한 문제이다. 딱 두달전 5/9에 100개를 돌파했는데, 속도가 붙어서

해결 1 - O(?) 해결 2 - O(NlogN)

주어진 배열의 값을 제곱한 결과를 오름차순 정렬하라.일단 시키는 대로 푼 방법. 근데 O(n)해결이 가능하다고 함. 좀 더 고민해보기.

박스갯수, 박스에 들어가는 유닛 갯수의 배열이 주어지고, 트럭에 적재할수 있는 최대 박스갯수 (truckSize)가 주어질때, 배열에서 아무 박스나 선택이 가능할때, 유닛갯수가 최대가 되는 값은?전형적인 greedy문제, 내림차순 정렬한뒤 가장 큰값부터 저장.

미팅룸 예약 시간이 담긴 배열이 주어질때, 모든 미팅을 수용할 수 있도록 필요한 최소 미팅룸 갯수를 구하라.시작시간, 종료시간https://leetcode.com/problems/meeting-rooms-ii/먼저 시작시간 기준으로 예약을 정렬한다. 그 뒤 다

문제 해결

입력이 아래와같이 주어진다. 이동평균(moving average) 크기가 주어지고, 값이 계속 추가될때 마다 moving average 크기만큼의 평균을 구하라.

문자열이 주어질때, 최대 2개로만 구성된 가장 긴 substring 길이를 리턴하라.two pointer & sliding window (with hashtable)hashtable빈도수가 2개 이하일때 -> right 증가hashtable빈도수가 2개 초과일때 ->

오름차순 정렬된 링크드리스트와 노드의 위치 인덱스 left, right가 주어질때, left에서 right까지의 범위를 reverse해라.reverse linked list아래의 쟁점을 해결 및 구현해야한다.범위내의 리스트를 reverse 하기그뒤 범위 밖의 prev_

9x9크기의 스도쿠 보드와 값이 주어진다. 주어진 값들이 아래 스도쿠 조건을 만족하는지 확인하라.Each row must contain the digits 1-9 without repetition.Each column must contain the digits 1-9

링크드 리스트와 값이 주어진다. 주어진 값 x를 기준으로 작은 값은 리스트의 왼쪽에 큰값은 그 뒤로 배치하라. 단 기존 리스트의 상대적인 순서는 유지되어야한다. 86\. Partition Listx보다 작은값들의 리스트, x보다 같거나 큰 값들의 리스트 두개를 만들고

주어진 배열값과 k값으로 폭탄을 해체하는 코드를 생성해라. 코드를 생성하는 방법은, 각 자리수를 k개만큼 이전/이후 까지를 더한값으로 계산하면 된다. 아래 예시를 확인!주의할 사항은 순환배열이라는 사실. https://leetcode.com/problems/d

행과 열이 모두 오름차순 정렬된 MxN크기의 matrix가있다. target값이 존재하면 true 없으면 false를 리턴.binary search를 행과 열 모두 할필요가 없고, 행을 순회하면서만 함. 추가 개선 포인트로, 모든 행을 탐색할필요가 없음. target이

특정 index를 기준으로 좌/우 배열값의 합이 동일한 index를 리턴하라.brute force로 한다면 (n^2)이 되겠지만. 구간합 테그닉?을 사용하면 O(n)에 해결이 가능.처음에 l_sum/r_sum을 먼저 구해놓고. 배열을 하나씩 순회하면서 아래와같이 현재

풀어본 것중에 좋은 문제라고 생각한 것들을 분야별로 추려보았다.

링크드 리스트의 head만 주어진다. 만약 리스트에 사이클이 존재한다면 사이클이 시작되는 노드를 리턴하라. 사이클이 없다면 NULL리턴linked list cycleLeetcode - 141. Linked List Cycle해시 테이블 사용

링크드 리스트를 reverse하라.reverse linked listhttps://leetcode.com/problems/reverse-linked-list/

바이너리 트리가 아니라, 자식이 여러개인 트리를 preorder 순회하라.사실 바이너리 트리랑 순회순서가 동일하다. 루트노드를 저장한뒤, 바이너리 트리가 left/right를 재귀로 순회했다면, 여기서는 child1,child2...childN 순차적으로 재귀를 호출하

dfs 순회 하면서 2차원 벡터의 level 인덱스에 값을 push_back()한다. 문제는 level인덱스가 없을때인데, 그 조건은 ret.size()가 level과 같거나 작다면 아직 level인덱스에 값이 없다는 뜻이다. 그 조건일때만 첫 벡터를 생성해서 push

두개의 배열이 주어진다. 전체 배열값중 중간 위치의 값을 리턴하라. (배열이 홀수개면 중간 인덱스값, 짝수개면 두개의 평균값). 단 풀이의 시간복잡도는 O(log(m+n)) 이 되어야한다.말그대로 두 배열을 정렬된 순서로 합치고 중간값을 계산한 방법. 두 배열을 합치는

주어진 트리가 BST(Binary Search Tree)를 만족하는지 확인하라left 자식트리의 모든 노드 값이 루트노드 보다 작아야한다.right 자식트리의 모든 노드 값이 루트노드 보다 커야한다.left, right 의 subtree 모두 BST를 만족한다.정렬된

mxn 2차원 map이 주어진다. 전달된 (sr, sc) 좌표의 값과 동일한 값을 가진 주변 요소를 모두 color값으로 바꿔라. (주변은 상하좌우 4방향을 의미한다)2차원 좌표 dfs, 그리고 visited 체크.

mxn크기의 2차원 배열이 주어지고 '1'로 이루어진 영역은 섬을 의미하고 '0'은 바다를 의미한다. 섬의 총 갯수를 구하라.https://leetcode.com/problems/number-of-islands/

n x n크기의 matrix가 주어진다. 각각의 row와 column은 오름차순 정렬되어있다고 할때 k번째로 작은 값을 구하라. 단 공간복잡도는 O(n^2) 미만으로 해결하라.k번째라는 말이 붙으면 일단 heap으로 푸는 문제를 떠올려야함. heap_add()함수를 주

구현문제, \[start, end] 시간 예약 함수 book()이 호출될때, 이전 시간과 겹쳐서 예약이 불가능하면 false, 가능하면 true를 리턴하라. 밸런스 트리로 구성되어있는 map자료구조 사용.upper_bound(n): n보다 큰 값중에 첫번째 iterlo

대문자로 구성된 문자열이 주어지고, 아무 문자로 바꿀수 있는 횟수 k가 주어질때, 동일한 문자로 구성된 substring의 최대 갯수는?생각하기 어려웠던 문제였다. discussion을 좀 참고했음. right와 left를 O(n)동안 하나씩만 이동해도 결과를 얻을수

동일한 문자가 두개이상인 첫번째 문자를 구하라.이런 유형의 문제를 수 도없이 많이 풀어서 그런지 후딱 풀었다. 시간을 쟀을때 3분밖에 안걸려서 기뻤다.

s로 주어지는 문자열 안에서 p로 주어지는 문자열의 Anagram을 찾고 시작부분의 인덱스를 리턴하라.해시테이블과 sliding window기법을 사용하는 좋은 문제였다. p크기 만큼의 윈도우를 s내에서 하나씩 오른쪽으로 이동하면서 체크하면 됨.Runtime: 12 m

정사각형방에 좌측 하단에서 레이져가 나온다. p와 q의 길이가 주어질때 해당 레이져가 어떤 모서리에 도달하는지 계산하라. (모든 input은 최종 모서리에 도달하는게 보장됨)Discussion을 참고해 아이디어를 얻었다. 위의 도식표로 그림을 그려보면 규칙을 발견할 수

주어진 문자열 중, 동일한 문자열의 빈도수가 많은 문자 순서대로 k개를 리턴하라. (단 문자열은 사전순 정렬되어있어야 한다)unordered_map으로 빈도수를 저장하고. 저장된 값들을 priority_queue에 push한다. 그리고 heap구조에서 k개만 추출하면

값 x 주어질때 power값은 아래의 규칙을 따라 x가 1 이될때 까지의 step수를 의미한다. x가 짝수면 x = x / 2x가 홀수면 x = 3 \* x + 1예를 들어 x = 3 이면 power값은 7이다. (3 --> 10 --> 5 --> 1

주어진 2차원 배열을 오른쪽으로 90도 회전시켜라.배열인덱싱의 끝판왕(?). solution을 참고한 풀이기에 다음번에 다시 풀어보기.

주어진 값들을 더해서(중복선택 가능) target이 되는 조합을 구하라. 결과 조합이 중복될 수 없다. (2,2,3과 3,2,2는 동일)백트래킹 문제. 잘 몰랐던것.tmp임시 벡터를 어떻게 선언해야하는지 재귀 호출 직전에 현재값을 push_back()하고, 호출이 끝나

주어진 배열중 target에 해당하는 값의 index를 리턴match와 Ordering으로 구현한점이 흥미로움.

주어진 2차원배열에서 target값이 존재하는지 확인하라. 각 row/column은 오름차순 정렬되어있다.

각 인덱스에서 최대 점프거리를 나타낸 배열이 주어진다. 0인덱스에서 시작해서 마지막 인덱스에 도달할 수 있는 최소 점프횟수는?솔루션 참고. 풀이 다시 살펴볼것.

2차원 배열이 주어지고 좌상단에서 우하단으로 이동할때 가능한 경로중 최소비용은? (이동시 경로의 값을 더함)dp문제

주어진 배열은 색정보(red:0, white:1, blue:2)를 가지고 있다. 배열을 red/white/blue순으로 정렬하라.3개의 hashtable을 만들고 빈도수를 저장한뒤, nums배열을 순차적으로 변경

char타입 2차원 배열에 문자가 포함되어있다. 주어지는 word와 일치하는 연속된 문자열이 존재하는지 파악하라. 단 상하좌우 방향 관계없음. 중복된 문자를 지날 수 없음.DFS 그리고 Visited 로 가지치기(pruning)하여 풀 수 있는 문제.

배열에 주어진 숫자로 만들 수 있는 모든 조합을 리턴하라. 0 개부터 n(배열갯수)개 까지 각각의 수를 선택할수 있는 조합을 백트래킹을 통해 구한다.

딱 한개의 숫자만 중복된 배열이 주어진다. 그 값이 무엇인지 리턴하라.https://leetcode.com/problems/find-the-duplicate-number/freq 를 값으로하는 해시테이블 생성해서 O(n)에 체크

주어진 문자열이 wordDict에 포함된 문자열로만 구성되어있는지 파악하라.https://leetcode.com/problems/word-break문자열을 두부분으로 나누고 왼쪽이 hash table에 있는지 파악, 그리고 오른쪽은 recursive 함수가 결

1 ~ n 까지 값이 포함된 노드가 BST 가 되는 경우의 수를 구하라. 가령 n=3일때 총 5가지의 BST가 존재.n=4 -> 1,2,3,4 일때이를 수식으로 표현해보면 아래와 같은 규칙이 발견됨. 여기서 u4가 위의 계산결과가 됨. 어려워서 솔루션을 조금 참고했다.

주어진 링크드 리스트를 오름차순 정렬하라.각 노드를 heap에 넣고 하나씩 pop하면서 새로 링크르 리스트를 생성.기존 노드를 재조합해서 새 링크드 리스트를 생성할때는 마지막 노드부터 시작해서 head로 만들어야함. 아래 코드 참고따라서 heap은 max heap이어야

주어진 배열을 자기자신을 제외한 모든 값을 곱한 값으로 바꾸어라.0이 한개일때, 0이 두개일때의 경우를 제외하고 구간합으로 해결할수 있음.

주어진 문자열에서 모든 palindrome(회문)의 substring 갯수를 구하라. substring은 연속된 부분 문자열을 의미.중앙에서부터 시작해서 palindrome문자인지 판별하는 방법. 이 방법은 문자열이 짝수개, 홀수가 두가지 경우 모두 체크해야한다. "a

링크드 리스트에서 val값을 가진 노드를 모두 제거하라https://leetcode.com/problems/remove-linked-list-elements/노드가 헤드인경우와 아닌경우를 구분해야함.

딱 한쌍의 노드를 swap해야 정상적인 BST가 되는 트리가 주어진다. 이 트리를 BST로 고쳐라.기본적으로 tree를 inorder 순회순회하면서 두개의 노드를 선정하는 방법.잘못된 BST는 순회시 현재 노드가 이전노드보다 값이 작을 때.순회 순서상 첫번째로 만나는

같은 anagram인 문자열끼리 묶어라.정렬된 문자열을 키로 하고, original index를 value로 하는 해시테이블을 생성.

정렬되지 않은 integer배열 값중에 가장 긴 연속된 수 갯수는? (O(n)에 해결하라)hashtable에 값을 저장하고 table을 순회하면서 연속된 수들을 찾음. 아래 순회 방식을 주석과 함께 잘 살펴보기. 가지치기가 필요.

주어진 트리를 우측에서 바라볼때 노드 값을 리턴하라.Binary Tree Right Side ViewBFS로 순회. root부터 queue에 넣고, pop하면서 처음으로 height가 커질때마다 값들을 ret Vector에 저장. 아주 흥미로운 문제 였다.

문장과 스크린 사이즈가 주어진다. 해당 문장을 스크린에 몇번 담을 수 있는지 파악하라.brute force 방법. 아래 예제에서 TLE발생.

0과1로 이루어진 이진트리에서 자식트리에 1이 없는 노드를 삭제해라.https://leetcode.com/discuss/general-discussion/1152824/cracking-the-coding-interview-6th-edition-in-leetco

주어진 오렌지 상자에 썪은오렌지(2), 정상오렌지(1) 없음(0) 이 존재한다. 썪은 오렌지는 한번에 상하좌우 4방향을 오염시킨다. 몇 번만에 모든 오렌지가 썪는지 파악해라.994\. Rotting Oranges참고로 썪은 오렌지가 두개 이상일 수있음.처음에 재귀로 풀

날짜별 온도가 담긴 배열이 주어진다. 각 날짜별로 온도가 처음으로 높아지는 날이 몇일 뒤인지 파악해라.brute force(n^2) 해결외에 방법이 잘 떠오르지 않아서,해설을 보니 monotonic stack 기법을 사용하면 된다. temp배열을 하나씩 순회하면서 오늘

가격이 적혀있는 배열이 주어진다. 현재 index보다 큰 index의 값중에 첫번째 작은가격의 값으로 현재 값을 할인 받는다면 최종 할인된 가격배열은? 가령 아래 예시에서 0 index의 이후 index중에 1의 가격이 4이므로 0번의 할인된 가격은 8-4 가 된다.다

건물높이를 나타내는 배열이 주어짐. 건물 맨 오른쪽에 바다가 있다. 오션뷰인 건물의 index를 순서대로 나열하라. (오른쪽에 같거나 큰 건물이 없는경우가 오션뷰)오른쪽에 다음 큰 값이 없는경우가 오션뷰이므로, monotonic stack으로 구할수있다. decreas

n개의 주유소가 있고 주유소에 도착하면 얻는 기름 gas\[], 그리고 그 주유소를 떠날때 필요한 비용 cost\[]가 주어진다. 주유소를 순환해서 순회한다고할때, 몇번째 index에서 출발하면 모두 순회할수 있는지 찾아라.gasi - costi로 새 배열을 만들고 이

i번째 인덱스는 해당 날의 주가를 의미한다. 날이 지날수록 사고팔고를 반복할수 있을때 가장 많은 수익금액은? 그래프로 그리고 생각해보면 인접요소의 기울기가 양수인경우를 모두 더하면 가장 돈을 많이 번게 됨.

서로 겹치지 않는 시작, 종료 interval 들이 담긴 배열이 주어진다. 새로운 interval이 들어왓을때, 중첩되는 interval을 합쳐서 배열을 다시 구성해라.중첩이 발생하기 전, 그리고 발행 이후는 순서대로 push하고, 중첩부분에서 시작 값중 가장 작은 값

두번째 pramp mock 인터뷰 경험이다. 1은 섬을 0은 바다를 나타낸다. 상하좌우로 인접한 1은 하나의 섬이다. 총 섬의 갯수를 구하라.그런데 실제 pramp에서 정확한 답이 안나왓는데, segmentation fault가 난것같다.(로그상에 안나옴). 원인은 이

주어진 target값이 트리 노드중에 어떤값과 가장 가까운지 찾아라.해당 값을 binary search하여 찾음. (해설 답안은 더 간결한데 확인해볼것 https://leetcode.com/problems/closest-binary-search-tree-val

intervals\[i] = \[starti, endi] 로 interval이 주어진다. 겹치는 부분을 합쳐라. (참고로 interval\[]는 정렬되어있지 않음)greedy한 방식으로 첫번째 값과 interval을 비교하면서 겹치면 확장. 안겹치면 push하고 그 값

각각의 셀마다 가장 가까운 0의 거리는? Ideabrute-force search mat from 0 to n -> O(N^2) (N=m\*n)using Queue -> O(N) / O(N)possible O(N) / O(1)? -먼저 0인 좌표를 queue에 push

높이값이 나열된 배열이 있다. 비가와서 물이 고일때 고인물(?)의 최대양은 얼마인가?rain water trap기본적으로 descreasing monotonic stack을 사용하여 풀 수 있다. stack에 top 높이가 작은 값만 push할 수 있다. 만약 현재 높

시간이 HH:MM 형식의 string배열로 주어진다. 가장 차이가 작은 시간을 분단위로 리턴하라.먼저 HH:MM을 minute integer로 변환. 그리고 정렬. 그 뒤 인접 값을 비교해서 가장 작은것을 선택. 주의할것은 처음과 끝값(순환)도 체크해야함.

세번째 pramp mock interview 경험주어진 배열에서 0을 뒤로 밀어라.참고로 leetcode move zeros 와 동일한 문제.배열을 추가로 생성하고 기존 배열의 값이 0이아니면 새로 추가. 그런데 공간복잡도가 O(1)인 해결방법을 떠올리려나 머리가 반즘

아래와 같이 동작하는 Circular Queue를 구현하라.MyCircularQueue(k) Initializes the object with the size of the queue to be k.int Front() Gets the front item from the

4번째 Pramp mock interview경험n x n 크기의 map이 있다고 할때, 좌-하단에서 우 상단까지 갈수 있는 경로의 경우의수는 무엇인가?(단 검은색 대각선기준 건너편(그림에서 검은색)은 이동할 수 없다.)검은색의 존재를 처음부터 신경쓰면 당황할 수 밖에

패키지의 무게 배열이 주어지고, 이것들을 나눠서 실을 수 있는 일 수가 주어진다. 최소가 되는 하루 총무게는 얼마인가? 가령 아래예시의 경우 5일에 나눠 싣는다고 하면, 모든 경우의 수중에서 15가 하루 최소 무게가 된다. 이게 어떻게 bin

주어진 배열을 m개로 나눌때(연속된 sub array로), m개의 sub array합중에 가장큰값이, 모든 경우의수에서 가장 최소가 되게하는 알고리즘을 작성해라.(Write an algorithm to minimize the largest sum among these

코코라는 동물(원숭이?)이 바나나더미를 먹는다. 사육사가 오기 전까지 제한시간이 주어지고 모든 더미를 먹어야한다. 시간당 최소한으로 먹을수 있는 갯수는?(단, 만약 시간당23개를 먹을 수 있다면, 30은 두시간이 걸리고, 11은 1시간이 걸린다.)https:/

몇일 뒤에 꽃이 피는지가 적힌 bloomDay\[] 배열이 주어진다. 꽃이 피면 꽃다발을 만들수 있다. 하나의 꽃다발은 k개이어야하고, 반드시 인접한 꽃만 선택할 수 있다. 총 m개의 꽃다발을 만든다고 할때, 최소 몇일 뒤에 작업을 완수할수 있는가?이전 문제와 마찬가지

다섯번째 Pramp mock interview.배열이 주어진다. 자기자신을 제외한 나머지 배열을 모두 곱한 값으로 변환해라. (단, 나눗셈을 사용할 수 없다)arr = 2 7 3 4res = 1 2 14 42 res = 1 2 14

현재 값, 현재까지 곱중에 가장 큰값, 현재까지 곱중에 가장 작은값 이 세가지를 순서대로 계산하면서 앞으로 나아간다. (해설참고) 가장 큰 값은 절대값이 가장 큰 두 음수 값의 곱이 될 수 도 있으므로, 최소 작은값도 가지고 있어야 하는것.아래 예시에서는 답이 96이

6번째 pramp mock interview주어진 배열을 오름차순 정렬하는 pancakeSort(arr) 함수를 구현 하라, 단 flip(arr, k)만 사용할 수 있다.flip(arr, k): arr\[]에서 처음부터 k 개의 요소를 뒤집는 함수. (이것도 구현해야함

주어진 배열값 두개를 더해서 lim값이 되는 인덱스 한쌍을 찾아라. i, j 라면 i>j 이어야 한다. 모든 가능성의 조합 중에 가장 마지막 조합을 리턴해야함(문제에는 표기가 안됐음)

k개의 면을 가진 주사위 n개가 존재한다. 이 주사위 n개를 던졌을때, 그 합이 target값이 나오는 경우의 수를 구하라. 결과 값은 % 1000000007 으로 모듈러 연산해서 리턴하라(오버플로우 발생예방)각각의 주사위 값은 유니크하다. (1,6) (6,1)은 독립

\[1] \[2] \[3] ... \[n-2] \[n-1] \[n] 순서의 링크드 리스트가 주어진다.\[1] \[n] \[2] \[n-1] \[3] \[n-2] ... 순서로 재 정렬하라.stack에 넣고 pop하면 뒤에서부터 거꾸로 노드를 얻을 수 있다. 원래 리스트

\[시작,종료]로 구성된 시작시간으로 정렬된 두명의 빈 가용시간 테이블이 주어진다. 주어진 dur 시간 만큼의 미팅을 하고자할때 현재 두 타임테이블에서 그것이 가능하다면 첫번째 가능한 예약 시간을 리턴하라. slotsA = \[10, 50, 60, 120, 140, 2

배열에서 peak 지점의 인덱스를 리턴하라. 만약 peak가 여러개면 아무지점이나 리턴해도 된다. 배열의 양 끝은 -∞ 라고 가정해라. (단 arri != arri+1 항상 성립한다)peak지점은 inc-dec 지점이다. 만약에 한 지점 i를 선택했는데 왼쪽값이 더 작

2차원배열의 요소를 spiral order 순서로 리턴하라.4방향의 바운더리를 축소하면서 인덱싱 하는 방법.

다음 인덱스로 점프할수 있는 최대 거리가 기록된 배열이 주어진다. 0 부터 점프를 시작한다고 할때, 마지막 인덱스에 도달할 수 있는지 없는지 판단하라.O(n^2)맨마지막-1 부터 0 까지 앞으로 하나씩 파악한다. 그리고 현재 인덱스에서 갈수 있는 최대 거리까지 모두 탐

interval이 주어졌을때, 중첩이 발생하지 않도록 interval을 제거할때, 최소한으로 제거할 수 있는 갯수는?Gready 두 interval이 가질 수 있는 세가지 경우의 수에 따라 각각 처리. Gready하게 O(n)에 계산이 가능해짐. 현재가 cur이고 그

오름차순 정렬된 배열이 몇차례 회전한 상태로 주어진다. 가령 \[3,4,5,1,2]는 \[1,2,3,4,5] 가 3번 회전한 상태. 이때 배열에서 가장 작은 수를 찾아서 리턴하라. 단 시간복잡도는 O(logn)이하 이어야한다. 아래 네가지 모든 경우의 수를 따져보면,

숫자로 이루어진 문자열이 주어진다. 각 수들이 문자로 decode된다면 총 몇가지 경우의 수 가 존재하는가?f(n) = f(n + 1) + f(n + 2) 라는 재귀적인 구조는 쉽게 파악할수 있었는데, base case 종료조건을 자꾸 틀려서 애먹음. 추가로 memoi

주어진 트리를 각 레벨별로 출력하되, 순서를 매 레벨마다 바꿔라. 가령 아래 예에서 3(->방향) 을 출력, 그 다음레벨은 20 9(<-방향), 그 뒤는 15 7 (->방향)

완전이진트리가 주어진다. 각 노드의 next 포인터에 같은 레벨에 있는 우측 노드를 연결해라.(가장 오른쪽 노드의 next 는 NULL)

배열로 주어지는 값을 합쳤을때 가장 큰 수가 나오도록 조합하라.32 3 이 있을때 32|3 보다 3|32 더 크다. 따라서 sort의 compare함수를 이 두 경우를 비교하도록 하면 된다. (discussion 참고). 추가로 std::sort()의 custom co

주어진 문자열을 파티셔닝 한다고 할때, 나눈 sub문자열이 모두 palindrome인 경우를 모두 출력하라.백트래킹, for문을 돌며 cur 부터 i길이만큼 문자를 확인하고 그 뒤 문자열은 재귀적으로 체크. 추가로 s.substr(시작 인덱스, 길이) 두번재 인자가 길

사방이 X로 둘러쌓인 O영역만 X로 flip해라. 처음에 한번의 DFS 재귀함수에서 모든 경우를 flip 해보려고 했는데, 경계 'O' 경우를 함께 해결하기가 너무 어려웠음. -> 실패그리고 솔루션에서 힌트(경계만 미리 marking)를 받음. 사전에 경계'O' 경우는

문제 주어진 배열을 오른쪽으로 k번만큼 회전시켜라. 해결 아이디어 궁극적으로 O(1) 공간복잡도 솔루션을 요구하는 문제였다. O(n) / O(n) 배열 뒤에서 k % n 의 인덱스 값부터 배열 끝까지 새 배열에 저장. 그리고 처음부터 k % n - 1 까지 저장.

어떤 수를 1, 4, 9, 16과 같은 완전제곱수(Perfect Square)의 합으로 나타낼수 있을때, 해당 수를 표현할 수 있는 최소한의 완전제곱수의 갯수는 몇개 인가? f(n) = min(f(n - 1^2), ~ , f(n - i^2)) + 1 이라는 점화식 관계

강의, 사전수강필요 강의 의 강좌 정보가 배열로 주어질때, 주어진 강좌를 모두 수강할 수 있는지 없는지 판단하라.adjacent사전수강강의 에 해당하는 강의 리스트를 자료구조를 생성하면 , 방향성 그래프 자료구조가 된다. 만약 그래프에 사이클이 존재한다면, 모든 강좌를

문제 총 n개의 강좌 (0 ~ n-1)가 주어지고, 각각의 강좌는 사전수강 강좌가 있다. [강좌, 사전수강필요 강좌] 의 배열이 주어질때, 강좌를 수강해야할 순서대로 정렬하라. 만약 모든 강좌를 수강하는게 불가능하면 빈 vector를 리턴. 해결 아이디어 -> top

1부터 n번호를 가진 노드 n개로 이루어진 무방향 그래프가 주어진다. 모든 노드와 연결되는 하나의 center노드가 존재하는데 이 노드를 찾아라.

"a", "b" 데이터가 포함된 equations배열과, 같은 크기의 values 배열이 주어진다. values 의미는 각 index의 a / b를 계산한 값이다. 여기서 queries 로 전달되는 "x", "y" 값을 구하라. equations 으로 주어지는 데이터는

각 도시의 연결 관계가 그래프의 인접행렬 형식으로 주어진다. 연결되어있는 모든 도시를 하나의 Province라고 할때, 총 Province의 갯수는?각 노드별로 백트래킹 형태의 dfs 순회를 한다. 인접행렬의 DFS순회 코드 다시 살펴보기.

주어진 배열을 두개의 subset으로 나누었을때, 두 subset의 합이 같은 경우가 존재하는지 판단하라.가령 아래 예의 경우 1, 5, 5 와 11 두개의 subset의 합이 동일해서 true이다. 처음에 시도했던건 backtracking으로 1 ~ n개를 선택하는

두 문자열에서 공통으로 가장 긴 subsequence를 구하라. https://leetcode.com/problems/longest-common-subsequence/재귀 관계식을 해설보고 알았다. 그래도 재귀 관계식을 코드로 구현하는건 어렵지 않게 해냄. 해

두 sparse vector(대부분 값이 0인)를 dot product연산한 결과를 출력해라. 두 벡터는 1차원벡터이다.대부분의 값이 0이기 때문에 <인덱스, 값> 해시테이블에 값이 0이 아닌 요소만 넣는다. 그 뒤 테이블을 순회하며 둘다 0이 아닌 값만 곱해서

binary tree에서 두 노드의 가장 가까운 공통 부모를 찾아라. 재귀함수는 자식노드에 q, p노드가 존재하면 해당 노드를 리턴, 아니라면 NULL리턴. left, right에 노드가 NULL인지 아닌지로 현재 노드가 LCA인지 아닌지 판단 가능.재귀 호출 이후 논

주어진 Binary Search Tree 에서 두 노드의 가장 가까운 공통 부모 (LCA)를 찾아라.현재 노드의 값이 p, q보다 작다면 LCA는 우측 자식노드에 존재. 이를 재귀적으로 반복.종료조건(base case) 현재 노드 값이 p, q보다 작지도 않고, p,

기본적으로 236. Lowest Common Ancestor of a Binary Tree 와 코드는 동일. 하지만 q, p노드를 실제로 방문했는지 체크했는지 여부 추가. 따라서 모든 노드를 방문해야함. 그래서 아래 (1) 코드는 양쪽 자식노드 재귀 호출을 마친 이후

오름차순 정렬된 Linked List의 포인터가 k개 담긴 배열이 주어진다. 모든 Linked list의 노드를 오름차순 정렬이 되게 합쳐라.https://leetcode.com/problems/merge-k-sorted-lists/priority queue

Median 값은 다음을 의미한다.For example, for arr = \[2,3,4], the median is 3.For example, for arr = \[2,3], the median is (2 + 3) / 2 = 2.5.값을 추가하고(addNum(int

주어진 배열을 순회하면서 k 크기의 window size 의 모든 median값을 구하라.https://leetcode.com/problems/sliding-window-median/sliding window 문제는 매번 윈도우 크기 k를 모두 계산할 필요가

정렬이 되지 않은 integer값의 배열이 주어진다. 이 배열에 존재하지 않는 양수값 중 가장 작은 값은?(시간복잡도 O(n)에 해결 해야한다.)만약 정렬을 했다면 O(nlogn)이겠지만 hashtable을 사용하면 O(n)에 가능하다. 단 모든 hashtable을 순

배열 요소값 보다 작은 값을 가진 요소의 갯수를 구하라.brute force 방법으로는, O(n^2) 으로 배열을 두번 탐색할 수 있다. 해시테이블에 중복값의 갯수를 저장.값을 0부터 최대배열값 100 까지 증가시키며, 중복갯수를 누적해서 더해간다.

주어진 배열을 정렬하라. 단 내장 정렬함수는 사용할 수 없다.merge sort는 절반으로 계속해서 나누는 재귀함수 파트그리고 다시 merge하는 동작 두가지로 나뉘어있다.merge 동작은 합치면서 정렬( 작은값부터 배열에 넣으면) 된다. 합치기 전의 배열은 이미 정렬

어떤 이진트리의 전위순회, 중위순회한 순서가 나열된 두 배열이 주어진다. 이것으로 원래 트리를 만들어라. (단 모든 값은 유니크한 수를 갖는다.)Construct Binary Tree from Preorder and Inorder Traversal접근방법 -> 두 배열

어떤 이진트리의 중위순회, 후외순회한 순서가 나열된 두 배열이 주어진다. 이것으로 원래 트리를 만들어라. (단 모든 값은 유니크한 수를 갖는다.)Construct Binary Tree from Preorder and Inorder Traversal기본적으로 105. C

targetSum 값과 트리가 주어질때, 루트 노드부터 leaf까지 path의 합이 targetSum이 되는 path를 모두 찾아라. DFS로 순회하면서 모두 합을 더하여 pathsum값인지 확인. left/right 두개짜리 backtracking 이다. 루트부터 l

중복된 수가 포함될 수 있는 배열이 주어진다. 이 수로 만들수 있는 permutation의 모든 경우의 수를 구하라. 기존 permutation 해결방법에서 살짝 변형. 주어진 배열 값이 몇개가 존재하는지 해시테이블에 저장. 백트래킹을 배열을 전부 하는게 아니라 중복된

주어진 배열의 sub-array의 합이 k가 되는 모든 sub-array갯수는?sum\[i, j) 는 기본적으로 sum\[0, j) - sum\[0, i) 로 구할 수 있다. 배열을 순회하면서 누적합(sum\[0, j)) 을 계산하다가 sum\[0, j) - k 값이

주어진 haystack 문자열에서 needle 문자열을 탐색했을때, 발견된 첫번째 인덱스를 리턴, 없다면 -1리턴. 해시값 비교하기. O(n\*m)kmp 알고리즘

주어진 트리에서 root부터 leaf까지 path중에 합이 targetSum 과 같은 경우는 총 몇개인가 (root부터 시작될 필요 없음)https://leetcode.com/problems/path-sum-iii/기본적으로 560. Subarray Sum E

아래와 같은 동작을 구현하라. 기본적으로 trie를 구현하는 방법에 대한 문제이지만, 그 전에 hashtable만 사용하여 아주 간단한게 풀어보았다. hashtable 방법insert() 함수에서 모든 prefix를 해시테이블에 값 1로 저장한다. 그리고 전체 word

주어진 배열에서 자기 자신의 오른쪽에 있는 값들중 자신보다 작은 값의 갯수를 구하라.numsl > numsr 일 때는 그 횟수를 cnt를 누적해서 더하다가. 크기가 반대가 되는 순간 (그동안 누적해서 더한 값이 l 의 오른쪽에있는 작은값의 갯수다)cnt값은 현재까지의

liked/disliked 비율과 like갯수의 조합으로 정렬하면 좋은 문제 순서대로 파악이 가능할것같아서 Leetcode Rest API가 있는지 찾다가 누군가 이미 만들어놓은 기가막힌 스프레드 시트를 발견했다. 매일같이 업데이트 되는 시트이며 여기서 조건 정렬해서

프로페셔널 도둑에게 훔칠수 있는 돈이 기록된 집의 리스트 배열이 주어진다. 집은 원형으로 배치되어있다. 따라서 배열의 맨 처음 집과 맨 마지막 집은 인접한 집이다. 인접한 두 집을 한꺼번에 훔치면 경보가 작동해 잡혀간다. 잡혀가지 않고 최대로 많이 훔칠수 있는 금액은?

이진 트리 구조로 연결된 집이 존재한다. 인접한 두 집이 털렸을때 경보가 울린다. 경보를 울리지 않고 모든 집을 털때 가장 많이 훔칠 수 있는 금액은?인접한 두 노드를 훔치지 않아야한다. 이전 House Robber 문제들 처럼 현재 노드에서는 훔치거나, 훔치지 않는

링크드리스트가 주어진다. 노드에는 next 포인터와 random 포인터가 있는데, random은 해당 리스트내부의 무작위 노드를 가리킨다. 이 링크드리스트를 복사하여 새로운 링크드 리스트를 만들어라.노드의 값만 복사하는것은 쉽다. 문제는 random 노드. 기존리스트와

s2가 s1문자열의 permutation을 포함하고 있다면 true를 리턴하라. permutation 이라서 back tracking을 떠올릴 수 있지만 그렇게 풀면 대단히 느려진다. permutation 이라는것은 각 문자의 frequency가 항상 동일하다는 뜻.

BST와 한 노드가 주어진다. 해당 노드보다 다음 큰 값을갖는 노드 즉, Inorder Successor 노드를 찾아라.모든 노드를 순회해서 찾을수도 있을것이다. 하지만 이진트리는 탐색시간이 각 단계별로 절반씩 줄어드는 O(logn)을 고려해야한다.inorder 순회는

BST가 주어지고 트리 내의 한 노드의 포인터가 주어진다.(root노드가 주어지는게 아님주의). 그 노드의 Inorder Successor를 리턴하라. 각 노드는 parent 노드를 가지고 있다. 유사문제는 : 285. Inorder-Successor-in-BST풀이

주어진 배열에서 아래 조건을 만족하는 세개의 값이 존재하면 true리턴i < j < k and nums\[i] < nums\[j] < nums\[k]LIS 문제의 풀이방법으로 해결 (https://velog.io/@soopsaram/Lee

주어진 배열에서 가장 긴 subsequence 즉 LIS의 갯수를 구하라.우선 LIS 길이를 구한 뒤, 배열을 backtracking을 통해 순회하면서 LIS길이를 만나면 총 갯수를 카운트 한다. 답은 맞지만 TLE가 발생한다. DP로 풀이하는 방법: memoizati

다음 동작을 하는 LRUCache class 를 구현하라.주어진 capacity값까지만 저장가능. 양수값으로 초기화된다.int get(int key) key가존재하면 value를 리턴하고 없다면 -1을 리턴하라.void put(int key, int value) key

sub-array의 합이 주어진 target보다 크거나 같은 sub-array의 최소 길이는? (없다면 0 리턴)전형적인 슬라이딩 윈도우 전략if (sum >= target) -> st++ 앞부분 사이즈 줄이기if (sum < target) -> end++뒷부

0에서 n-1이름의 n개 노드로 구성된 무방향 그래프(Undirected Graph)가 주어진다. edges\[] 는 각 노드의 엣지(간선)가 리스트업 되어있다. 어떤 노드도 루트노드가 될 수 있다고 할때, 트리의 높이가 가장 낮아지는 루트노드를 모두 구하라.Brute

brute-force - O(n)sumRange가 호출될때마다 left 부터 right까지 항상 더하기O(1)초기화할때 i 까지의 부분합을 해시테이블에 저장. 그리고 left 부터 right까지의 합은 presum\[right] - presum\[left - 1] 이

ping()이 특정 시간 t 마다 호출된다.(단위 msec) 매번 ping이 호출 될때마다 최근 3000 msec 동안 호출된 ping의 갯수를 구하라. (t는 증가하기만 할수있다)슬라이딩 윈도우처음에 배열에 left right변수를 사용해서 구현하려고 했는데, 공간복

logging시스템을 구현. string 타입의 메시지와 timestamp가 입력된다. 동일한 메시지를 새로 받으려면 10초 이후에 가능하다. 가령 "foo"라는 메시지가 3초에 도착했었고. 9초에 "foo"가 도착했다면 메시지를 새로 저장할수없다(false가 retu

아래와 같은 queue의 동작을 두개의 stack만 이용해서 구현하라. stack은 push/pop/top/size/empty 메소드를 사용할 수 있다. push는 첫번째 스택에 push한다. O(1)pop/peek를 할때는 첫번째 스택에서 요소를 모두 두번째 스택으

next()가 호출될때 마다 트리의 inorder 순회한 값을 하나씩 리턴하라.initial 함수에서 vector에 inorder 순회하여 값을 미리 넣고 O(n), next가 불릴때마다 O(1)에 값을 리턴. hasNext() 도 O(1).

2D 벡터를 flat하게 만드는 iterator를 디자인해라.풀이12차원 벡터를 1차원 벡터에 복사 O(n)

다음과 같이 space로 구분된 문자열을 각각 reverse시켜라.https://leetcode.com/problems/reverse-words-in-a-string-iii/다음은 일반 문자열을 재귀적으로 reverse 하는 함수.FP스타일로 해결FP스타일로

string s에 어떤 문장이 담겨있다. 이 문장의 단어의 순서를 뒤집어서 출력하라. 그리고 불필요한 while space는 제거하라.토큰을 나눠서 stack에 저장한뒤, pop하면서 합치기.

두 문자열을 한문자씩 번갈아서 합쳐라. 더 긴 문자열의 나머지 문자열은 그대로 합치기. 다음과 같은 재귀적 구조로 작성. 풀이가 비슷했던 문제로는 Leetcode - 21. Merge Two Sorted Lists

하나씩 다시 풀기Leetcode - 1. Two SumLeetcode - 3. Longest Substring Without Repeating CharactersLeetcode - 5. Longest Palindromic Substring

문제 오름차순 정렬된 배열이 주어진다. 두 값을 더했을때 target이 되는 index 두개를 리턴하라. 공간복잡도는 O(1) 이어야한다. 아디이어 해시테이블을 사용 O(n)에 해결가능. 하지만 공간복잡도도 O(n) 이 되기 때문에 그렇게 풀수 없다. 문제에서 정

문제 root로 주어진 트리에 subRoot로 주어진 sub트리가 존재하는지 확인. 있다면 True, 없다면 false. subRoot의 서브트리와 완전히 동일해야함 아래 예시 참고. 아디이어 대부분의 트리문제는 재귀함수 형태로 푼다. 현재 주어진 r, s트리의

장애물이 1, 갈수있는도로가 0으로 주어진다. 좌상단에서 우하단으로 이동할수 있는 모든 경로의 갯수는?목적지(i, j) 로 갈수 있는 경로는 위에서(i-1, j) 좌측에서(i, j-1) 오는 방법 두가지다. 목적지부터 재귀적으로 반복하면 된다. 경계값일때 리턴값은 0인

3종류의 페인트로 집을 칠한다. 주어진 2차원 배열의 row는 각각의 집, colum은 각 3가지 페인트의 가격이 적혀있다. 인접한 집이 서로 같은색이 되지 않도록 칠하는 모든 경우중 가장 저렴한 페인트 총합은?https://leetcode.com/proble

바이너리 트리에서 각 level의 합을 구했을때, 가장 큰 값을 갖는 level을 리턴하라. (level은 1부터 시작)DFS: O(n) 각 level의 합을 저장하는 배열을 만들고 DFS순회 하면서 더하기.

주어진 문자열에서 모든 k길이의 substring 중에서 모음이 가장많은 substring의 모음 갯수는?O(n)/O(1) k 사이즈 만큼의 윈도우를 한칸씩 우측으로 이동. 윈도우의 맨 오른쪽에 들어올 다음 문자와 윈도우의 맨 왼쪽에서 제거될 문자에 모음이 있는지 확인

주어진 문자열에서 모든 k길이의 substring 중에서 모음이 가장많은 substring의 모음 갯수는?O(n)/O(1) k 사이즈 만큼의 윈도우를 한칸씩 우측으로 이동. 윈도우의 맨 오른쪽에 들어올 다음 문자와 윈도우의 맨 왼쪽에서 제거될 문자에 모음이 있는지 확인

edge가 주어질때, source -> destination 에대한 경로가 존재하면 true 아니면 false.https://leetcode.com/problems/find-if-path-exists-in-graph/Union Find두 노드가 같은 그룹에 속

주어진 그래프가 valid한 Tree인지 아닌지 판별하라A valid Tree?union-find를 사용하여 그래프에 cycle을 찾을 수 있고, 모든 노드의 대표노드가 같은지 파악하여 모든노드가 한 그룹인지 파악할 수 있다.loop detect방법0,1, 1,2, 2

주어진 그래프에서 서로 연결된 그룹의 갯수는?union find를 수행하고, 각 노드에 find()를 수행하면 대표노드를 얻을 수 있다. 같은 그룹에 있는 노드의 대표노드는 반드시 같기 때문에, 서로 다른 대표노드의 갯수를 구하면 된다.해시테이블을 사용해 O(n)으로