Algorithm

링크 n 개의 모든 노드를 탐색하는 가장 짧은 경로를 반환하는 문제각 노드를 2진수의 자리로 표현n = 5 일때, final state = 11111(2)bfs 를 활용하여 (다음상태, 다음노드) 가 seen 에 없으면 queue 에 추가

링크배열요소의 합이 최대가 되도록 최대 길이k 로 배열을 분할하는 문제분할된 각 부분 배열들은 모두 최대값으로 대치됨ex. 1, 15, 7, 9, 2, 5, 10 => 15, 15, 15, 9, 10,10, 10최대 길이가 k 이므로 현재 요소(i) 에서 i-1 ~ i

링크문자열이 정규식에 부합하는지 찾는 문제pattern 의 첫글자가 text의 첫글자와 같거나 '.' 이면 통과pattern 에 '\*' 문자가 있다면 ('\*' 문자는 0번이상이므로)\*앞의 문자가 나타나지 않는 경우\*앞의 문자가 1이상 나타나는 경우 나머지 t

링크Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two en

링크합해서 0이 되는 3개의 수 배열을 모두 찾는 문제3sum 은 2sum 으로 분리 가능함 \- -1, 0, 0, 1 일 때, -1 과 0, 0, 1 에서 target 이 1 인 twoSum 으로 접근 가능연산한 값을 저장중복된 값을 제거하기 위해 answer 는

링크휴대폰 키패드에서 숫자들의 조합으로 만들어낼 수 있는 문자열들을 구하는 문제itertools 의 product 사용digits 를 순회하며 해당하는 문자 배열들을 더해주는 방식

링크뒤에서 n번째 노드 제거하기길이(len) 을 구하여 len - n 번째와 len - n + 2 번째 이어주기slow 와 fast 이용fast를 n 만큼 이동시켜놓은 이후 slow, fast 한칸씩 이동 > fast와 slow 간격 n 유지fast 가 맨 끝 노드에

링크n개 쌍의 () 를 활용하여 모든 가능한 parentheses 를 구하는 문제backtracking 이용( -> ( : ( 의 개수 < n, ) : 항상 가능 ) -> ( : ( 의 개수 < n, ) : ) 의 개수 <= )의 개수

링크k 개의 정렬된 연결리스트를 하나로 정렬하기연결리스트들을 순회하며 최소값을 찾고이를 head 에 연결시간이 오래 소요됨 (O(kn))divide and conquer 이용시간 통과!

링크다음 사전 순서 배열 찾기끝에서 부터 탐색하며 내림차순이 어긋나는 부분 찾기 (ex. 12453 에서 4와 5에서 오름차순이 됨 4 = k)k 와 k 값 다음으로 큰 수를 swap, 뒤 부분배열 오름차순 정렬 역순으로 정렬되어있을 때는 별도의 코드 필요constan

링크정렬된 배열이 k 번째 인덱스에서 회전되었을 때, 특정 원소의 위치를 O(log(n)) 만에 구하는 문제회전이 시작된 인덱스 (오름차순이 위배되는 곳) 을 찾아서 l, r 정하기인덱스를 찾느라 O(n) 의 시간이 소요될 수 있음mid 값이 l 보다 크다면 > 왼쪽이

링크배열에서 해당 원소의 첫번째 위치와 마지막 위치를 구하는 문제python 의 bisect 모듈 이용 96% 빠르게 통과함!! 최고다!! 왼쪽 한번 오른쪽 한번O(2logn) = O(logn)

링크정렬되어있지 않은 배열에서, 존재하지 않는 가장 작은 양수를 O(n), constant memory 사용으로 구하는 문제res 을 1로 초기화 하고 배열을 돌며 res 와 같은 값이 나오면 1 을 증가시켜준다res 값에 변화가 없을 때 까지 반복

링크물이 고일 수 있는 양 구하기유사문제Container with most water문제와 유사하게 l, r pointer 2개를 두고, 양을 더하고 빼는 방식minHeight 를 계산해두고, 포인터 이동 이후 이동된 위치의 높이만큼 빼주기이동된 위치에서 minHeig

링크순열 구하는 코드itertools.permutations재귀함수를 통해 직접 순열 코드 구현check 배열을 통해 중복 방지시간은 1번과 같게 나옴nums 배열 자체를 조작

링크2차원 배열 90도 회전하기tmp 변수에 기존 배열 저장해놓고 in place rotation

링크Input: strs = "eat","tea","tan","ate","nat","bat"Output: \["bat","nat","tan","ate","eat","tea"]sort된 문자열을 키로 사용하는 딕셔너리 사용딕셔너리의 values return

링크You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.Return t

링크겹치는 범위를 하나로 합치기Input: intervals = \[1,3,2,6,8,10,15,18]Output: \[1,6,8,10,15,18]배열을 정렬해서 차례로 겹치는 간격들을 찾기

링크(https://leetcode.com/problems/unique-paths/)오른쪽 또는 아래로 이동 가능한 좌표들로 queue 에 넣어서 finish 지점에 도착하면 경우 ++시간초과최단거리 경우의 수 문제와 같게 접근boardi = boardi-1

링크insert / delete/ replace 를 통해 문자열1을 문자열2로 만드는 가장 간단한 방법의 단계 수 구하기dp\[i]\[j] = word1:i+1 과 word:j+1dp\[0]\[j] = j 빈문자열을 j 로 만드는 방법 = j 번 추가dp\[i]\[0

링크정렬0, 1, 2, 의 개수 세기대입l, r two pointersl 은 0의 위치 r 은 2의 위치1 보다 느림

링크board 에서 중복 없이 해당 단어를 만들 수 있는지 반환하는 문제시간 초과최적이 아닌 true false 반환이기 때문에 dfs 가 더 적합할 것으로 생각check 를 2차원 배열이 아닌 in 으로 판단했을 때는 시간초과가 났음무조건 모든 노드를 탐색하는 것이

링크히스토그램에서 가장 큰 사각형의 넓이를 찾는 문제 index 를 stack 에 넣음 for 문을 돌면서 현재 높이가 stack 의 끝보다 작으면 pop 시작 넓이를 갱신

링크1과 0으로 이루어진 보드에서 1로 만들 수 있는 가장 큰 사각형의 넓이를 구하는 문제각 위치에서 세로 확인넓이 업데이트 시간이 많이 소요됨\-참고 문제 , velog각 행에서 1 들을 높이로 생각\[1, 0, 0, 1, 0, 1, 0, 0, 1, 0]

링크n 개의 노드를 가지는 BST 개수 구하는 문제n == 4 일때, 루트를 제외하고 left, right sub trees 의 개수는 0 3 1 2 2 1 3 0for 문을 돌면서 left \* right 를 하면 됨중복을 줄이기 위해 n

링크올바른 bst 인지 판단하는 문제 (left.val < root.val < right.val)left > root > right 순으로 탐색하면서 배열을 만듬leftarr-1 >= root.val 이면 falserightarr0 <= root.val

링크preorder, inorder 로 쓰여진 배열을 보고 bst 를 만드는 문제 preorder0 은 rootinorder 에서 root 를 기준으로 왼쪽은 left child, 오른쪽은 right child 로 나뉨을 이용재귀로 트리 만듬매번 root 값의 inde

링크연결리스트를 k 길이의 그룹들로 나눠 reverse 하는 문제, 단 O(1) 메모리리스트의 길이 구하기n // k 만큼 반복문k 길이 만큼 reverse 시킨 후이 그룹들을 이어주기

링크정렬된 배열을 balanced binary search tree 로 변환하는 문제리스트의 길이 구하기n // 2 -> rootleft, right 재귀적으로 구하기

링크이진트리를 pre-order 순으로 linked list 로 만드는 문제 O(1) 메모리 root.left 의 가장 끝 right node 의 오른쪽에 root.right 붙이기root = root.right 로 이동시키며 해당 과정 반복

링크이진트리의 경로들 중 path 의 합이 최대가 되는 경우를 구하는 문제diameter of binary tree 문제와 비슷하게 접근left, right, left + root, root, right + root, left + right + root 판별

링크O(n) 의 시간복잡도로 정렬되어있지 않은 배열에서 연속된 숫자들의 최대 길이를 찾는 문제파이썬의 setadd O(1)pop O(1)remove O(1)in O(1)배열을 set으로 변환 후, in 키워드를 통해 찾기리트코드 solution변형

링크next 와 random 포인터를 가진 linked list 를 deepcopy 하는 문제dictoriginalNode = copiedNode딕셔너리를 만들면서 next 연결딕셔너리를 이용해 random 연결딕셔너리 다 만들고 next 와 random 동시에 연결깔

링크문자열s와 단어들의 배열 wordDict 가 주어졌을 때, wordDict 내의 단어들로 문자열을 만들 수 있는지 여부를 구하는 문제dpi = dpj && sj+1:i+1 in wordDict

링크LRU 캐시 구현dictkey = nodehead, tailhead : 가장 최근 사용 tail : lru

링크곱했을 때 가장 큰 값이 되는 연속적인 부분 배열 구하는 문제왼쪽 -> 오른쪽오른쪽 -> 왼쪽 0을 만나면 1로 초기화음수 \* 음수 = 양수!더했을때 가장 큰수가 나오는 연속된 부분을 찾기 위함max 와 min 동시에 갱신 -> min 이 max 가 될수도있기 때