코딩테스트

문제 바로가기주어진 array에서 합이 target이 되는 요소의 인덱스를 찾아야한다. 👉 hash table

문제 바로가기처음에는 BFS로 순회하면서 이진탐색을 수행하자고 생각했다.Time complexity : O(nlogn). 모든 노드를 순회하며 이진탐색Space complexity : O(n). queue문제를 풀고 솔루션을 확인했는데... 세상에, 이진탐색트리는 중복

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes conta

문제 바로가기처음에 maxLen 업데이트 코드를 잘못 배치했는데 샘플 데이터에서는 잘 돌아가서 그대로 제출했었다.그래서 2번 실패 끝에 통과할 수 있었다. 만약 실제 테스트였으면 0점이었을 것이다.코드 작성 전에 귀찮더라도 알고리즘을 다시 생각해보고, 샘플 데이터를 몇

문제 바로가기list 등의 자료구조를 사용할 때는 비어있거나 존재하지 않는 키를 찾고 있지는 않은지 확인해야한다!!

문제 바로가기binary search처럼 반절씩 줄여나가며 탐색

Given a string s, return the longest palindromic substring in s.

문제 바로가기반복문으로 푼다고 온갖 경우들을 다 생각하면서 짜다가 너무 시간이 오래 걸려서 포기했다.같은 상황이 반복되면 recursion으로 푸는 것을 고려하자!Kleene stars를 만나는 경우와 아닌 경우를 기점으로 나눠가면서 회귀함수로 해결할 수 있다.

문제 바로가기

문제 바로가기Time Complexity: O(n)Space Complexity: O(1)각각의 최대 부분합은 이전 최대 부분합이 반영된 결과값임을 활용하자.배열의 각 인덱스에서 가질 수 있는 최대 부분 값은 자신의 값과 이전의 최대 부분합에 자신의 값의 합 중 더 큰

문제 바로가기처음 생각정렬가장 긴 두 위치에서 시작해서 점점 작은 위치를 탐색2.1 만약 높이를 줄이는게 더 이득이면 수정그런데 처음에는 손해여서 넘겼던 위치가 나중에 더 이득인데도 이미 지나가서 선택하지 못하는 경우가 생겼다.testcase: \[76,155,15,1

문제 바로가기Time Complexity: O(n^2)Space Complexity: O(n)Using collection.Counter get all unique numbers with count of occurrences.

문제 바로가기

문제 바로가기Time Complexity: O(n)Space Complexity: O(n)Time Complexity: O(n)Space Complexity: O(1)

문제 바로가기

문제 바로가기Time Complexity: O(logn)Space Complexity: O(1)Time Complexity: O(logn)Space Complexity: O(1)그런데 사실 pivot을 찾지 않고도 한번의 binary search로 해결할 수도 있다.

문제 바로가기Time Complexity: O(logn)Space Complexity: O(1)Time Complexity: O(logn)Space Complexity: O(1)처음에 target이 있는지 찾을 필요도 없이 바로 처음 마지막 위치를 binary sear

문제 바로가기최적화는 신경쓰지 않고 어떻게 풀지 생각하고 작성한 코드이다.풀리긴했으나 매우 낮은 시간 점수를 보여줬다. Time Complexity는.... 거의 O(n^n)이 되지 않을까 싶다.candidates를 정렬하고 for문으로 candidates를 순회하면서

LeetCode - 바로가기\[Leetcode] 39. Combination Sum - 바로가기

문제 바로가기nums 리스트의 모든 원소를 순회하면서 해당 원소에 도달하기 위한 최소 jump 수를 기록하는 jumpNums 리스트를 업데이트한다.Time Complexity: O(n^2)Space Complexity: O(n)nums 리스트의 모든 원소를 순회하면서

문제 바로가기Time Complexity: O(n^2)Space Complexity: O(n^2) - DFS에서 제일 깊은 단계에서 길이 n의 buf가 stack에 n개 올라가므로 visited를 기록하는 대신 각 단계에서 사용한 숫자를 제외한 새 list를 전달한다.

문제 바로가기행렬을 시계방향 90도 회전시키는 문제.회전을 할때 어떤 원소의 행과 열은 다음과 같이 바뀐다row' = colcol' = (n - 1) - row따라서 행렬을 순회하며 회전 결과 위치로 값을 옮겨주면 된다.이 때 다음과 같은 최적화를 통해 계산 수를 줄일

문제 바로가기n: strs.lengthk: average str.lengthTime Complexity: O(nklogk)Space Complexity: O(nk)

문제 바로가기Time Complexity: O(n)Space Complexity: O(1)

문제 바로가기Time Complexity: O(nlogn) - sortSpace Complexity: O(n)

문제 바로가기Time Complexity: O(n)Space Complexity: O(1)

문제 바로가기Time Complexity: O(mn)Space Complexity: O(mn)Time Complexity: O(mn)Space Complexity: O(mn)

문제 바로가기

문제 바로가기pivot을 기준으로 작은 쪽, 큰 쪽으로 나눠 정렬하는 quick sort의 특징을 활용한다.Time Complexity: O(kn) - k: 색의 종류Space Complexity: O(1)

문제 바로가기Time Complexity: O(2^n)Space Complexity: O(2^n)

문제 바로가기k: word의 길이Time Complexity: $O(mn\*4^k)$Space Complexity: $O(mn)$DFS가 recursion으로 구현되어 있으므로 visited를 운용할 필요없이 board에 바로 반영해 Space Complexity를 줄

문제 바로가기Time Complexity: $O(n)$Space Complexity: $O(n)$

문제 바로가기처음에 생각했던 풀이 방식이다.DFS로 접근하며 각 subtree의 최대/최소 값과 parent node의 비교를 통해 True/False를 반환한다.Time Complexity: $$O(n)$$Space Complexity: $$O(n)$$말단 노드에서부

문제 바로가기기본 풀이 방식은 동일하나 Recursion이 Loop보다 거의 두배 빨랐다. 이는 list의 잦은 추가와 삭제에서 오는 차이때문으로 생각된다.Time Complexity: $$O(n)$$Space Complexity: $$O(\\log n)$$Time C

문제 바로가기Time Complexity: $$O(n)$$Space Complexity: $$O(n)$$preorder 방식으로 DFS로 탐색하는 방식이다. queue를 사용하지 않으므로 더 적은 시간이 소모된다.Time Complexity: $$O(n)$$Space

문제 바로가기leaf node에서 backtracking으로 root까지의 길이 중 최대 값을 계산한다.Time Complexity: $$O(n)$$Space Complexity: $$O(\\log n)$$ - worse case: $$O(n)$$

문제 바로가기preorder와 inorder의 탐색 순서 차이를 이용해 해결한다.preorder\[0]는 root 노드 값이므로 해당 값으로 inorder에서 root의 위치를 탐색할 수 있다.inorder에서 root의 위치를 특정하면 해당 index를 기준으로 le

문제 바로가기

문제 바로가기

문제 바로가기Time Complexity: $$O(n)$$Space Complexity: $$O(n)$$$2\*(a+b+c)-(a+a+b+b+c) = c$Time Complexity: $$O(n)$$Space Complexity: $$O(n)$$a ⊕ 0 = aa ⊕

문제 바로가기Time Complexity: $$O()$$Space Complexity: $$O()$$

문제 바로가기tree를 생성해 DFS를 진행했다. 그 과정에서 중복되는 계산을 줄이기 위해 DP를 적용했다.

문제 바로가기Time Complexity: $$O(n)$$Space Complexity: $$O(n)$$fast가 slow의 2배 만큼 이동한다는 점을 이용하면 cycle이 시작되는 node를 찾을 수 있다.1 ~ 9의 값을 가지고 4 ~ 9에 cycle이 존재하는 n

문제 바로가기linked list로 각 key-value 쌍의 사용 순서 구조를 유지하고, 각 node의 탐색을 위해 hash map을 사용한다.각 get, put 작업에 대해Time Complexity: $$O(1)$$Space Complexity: $$O(c)$$

문제 바로가기Time Complexity: $$O(n\\log n)$$Space Complexity: $$O(n)$$Time Complexity: $$O(n\\log n)$$Space Complexity: $$O(\\log n)$$ - 함수 호출에 의한 stack이론상

문제 바로가기Time Complexity: $$O(n)$$Space Complexity: $$O(1)$$

문제 바로가기Time Complexity:push: $$O(\\log n)$$pop: $$O(n)$$top, getMin: $$O(1)$$Space Complexity: $$O(n)$$매 push마다 이전 min값과 현재 값을 비교한 새로운 min값을 같이 저장한다.

문제 바로가기방문 여부 체크1.1. set에 object id가 있으면 방문했던 노드1.2. 아니면 처음 방문한 노드방문했던 노드면 그 노드가 intersect이다.2.1 아니면 set에 object id를 저장 후 재개Time Complexity: $$O(n_A +

문제 바로가기Time Complexity: $$O(n)$$Spcae Complexity: $$O(n)$$Time Complexity: $$O(nlog n)$$Spcae Complexity: $$O(1)$$ or $$O(n)$$ <- if In-Place not a

문제 바로가기Time Complexity: $$O(n)$$Space Complexity: $$O(n)$$Time Complexity: $$O(n)$$Space Complexity: $$O(n)$$

문제 바로가기Time Complexity: $$O(n_r n_c)$$Space Complexity: $$O(n_r n_c)$$Time Complexity: $$O(n_r n_c)$$Space Complexity: $$O(n_r n_c)$$

문제 바로가기Time Complexity: $$O(n)$$Space Complexity: $$O(1)$$Time Complexity: $$O(n)$$Space Complexity: $$O(n)$$

문제 바로가기위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다.

문제 바로가기In computer science, a trie, also called digital tree or prefix tree, is a type of search tree, a tree data structure used for locating specifi

문제 바로가기

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Given the root of a binary tree, invert the tree, and return its root.

Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.

스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

2048 게임을 기반으로 하는 문제. 한 번에 상하좌우 중 한 방향으로 이동할 수 있으며, 최대 5번의 이동에서 얻을 수 있는 가장 큰 블록 값을 반환한다.

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

You are given two binary trees root1 and root2. 중략...Return the merged tree.

문제 바로가기가중치가 없는 그래프에서 다중 시작점에서부터 모든 칸까지의 최단 거리를 구하는 문제출처 - https://solved.ac/contribute/7576알고리즘익은 토마토의 위치를 queue에 삽입queue의 익은 토마토들을 dfs로 순회하며 주변의

문제 바로가기가중치가 없는 그래프에서 다중 시작점에서부터 모든 칸까지의 최단 거리를 구하는 문제출처 - https://solved.ac/contribute/7569알고리즘 - \[백준 7576] 토마토와 동일익은 토마토의 위치를 queue에 삽입queue의 익

문제 바로가기해설 바로가기냥캣이번 하반기 Dev-Matching 프론트엔드 과제를 대비하기 위해 지난 상반기 문제인 고양이 사진첩 애플리케이션문제를 풀어보고 해설과 함께 복기해봤다.필수 구현사항과 옵션 구현사항은 다음과 같았다.app이라는 class를 가진 main에