[코드없는 프로그래밍 - Coding Test]

코업프Computational Thiking을 할 수 있는지를 보는 것이다.이는 Time, Space Complexity를 이해하고 있는지를 확인할 수 있고, 이러한 것이 가능한 개발자만이 Scalable한 개발을 할 수 있다고 판단하고 있다.random access가

O(logn)의 Search를 기대하는 알고리즘이다.Pivot을 간단히 설정하여 해당 Target value를 찾아내면된다.구현은 간단하지만 반드시 알고 있어야한다.L은 left, R은 right 라고 가정하면 초기값은 vector 및 Array의 begin, end

ReferenceSliding Window 알고리즘을 익히기 좋은 문제다.부르트 포스로 풀면 Pivot 이동 O(n) 연산과 해당 Pivot 시 발생하는 왼쪽, 오른쪽의 누적합 알고리즘이 합쳐진다면 O(n^2)이 예상된다.하지만 Sliding Window 알고리즘을 적

Sort Colors

보통 두 Array를 합칠 때, 사용하는 알고리즘으로 각각의 Array에 Pointer를 두고 비교하여 새로운 Array에 써주는 식으로 Return 하는 방식이 있다. 하지만, 그렇지 않고 원래의 Array에 쓰도록 하는 문제가 이 문제다.이 문제에서는 애초에 하나의

move zeros Reference 배열을 바라보는 관점을 높여주는 문제다. Algorithm 제목만 보면 0을 움직여야만 할 것 같지만, 이렇게 생각하면 Bubble swap을 해줘야하므로 굉장히 많은 Operation이 수행된다. 다르게 생각해보면 숫자를 왼쪽으

Interval List들을 받아서, Merge 후 결과 Interval을 Return 한다.Interval Start 지점의 값을 기준으로 Sorting 후 merge를 해나가면 O(n)으로 해결할 수 있다.물론 Sorting이 필요한 경우에는 O(nlogn)이 소요

Reference배열 문제를 해결할 때, 그래프를 고려해볼만한 문제다.해당 배열에서 어떤 Sub 배열을 Sorting해야 전체 배열이 Sorting 되는지, 그 Sub 배열에 포함되는 원소는 몇개인지 구하는 문제였다.처음으로 생각해볼만한 알고리즘으로는 sorting 후

String Mtaching 은 O(n)의 Time Complexity로 진행할 수 있다는 점을 숙지하고 있어야한다.기본적으로는 O(NxM)이다. N번 M 개의 문자열을 비교하기 때문이다.KMP, Rabin Karp가 유명하다.이는 미스매칭이된 부분에서 앞에서 이미 매

Add String addString(num1, num2)와 같은 문제다. 특이한 점은 num1, num2가 string type이라는 것이다. num1, num2가 type이 int이거나 float이면 풀기 쉽지만, 32/64bit를 넘어서는 수를 준다면, 풀기어려울

이는 앞으로 읽어도, 뒤로 읽어도 똑같다는 것을 의미한다.위 문자열은 Palindrome인 것이다.Palindrome을 판별하는 알고리즘은 간단하며 O(n)의 Time Complexity를 갖는다.p1과 p2를 두고 서로 같은지를 판별하면서 줄여나가면 된다.p1과 p2

똑같은 알파벳으로 이루어진 String을 의미한다.LISTEN <-> SILENT\[abc, cde, bca, ...] 와 같은 list input이 주어졌다고 해보자.첫 번째 Solution으로 생각해보면 각 단어들을 Sorting 후 해당 결과를 Key로 갖는

말그대로 반복되는 문자가 없는 Substring중 가장 긴 것을 찾는 문제다.브루트포스는 당연히 안된다.. 너무 큰 Time & Space Complexity다.위와 같은 문자 리스트를 주었다고 해보자.이 또한 Pointer를 지정함으로써 Substring의 조합을 만

Stack의 기능 top, push_back, pop_back 뿐만 아니라 max 값을 찾아서 주는 기능도 추가하는 문제다.위와 같은 Input이 Stack에 들어간다고 해보자.이는 max기능의 Time Complexity를 O(1)로 만들기 위해 Space Compl

중복되는 문자를 지워주는 문제다.Stack Approach가 얼마나 중요한지 알려주는 문제였다.기초적으로는 중복되는 2문자가 있으면 지워주는 문제를 생각해본다.위와 같은 식으로 top과 현재 push 하고자하는 변수를 통해 stack에 push 할지, pop을 할지를

ReferenceInsert/Find 기능이 O(1)의 Tiem Complexity를 가진다.Data Constructor가 Key-Value 관계를 가진다.Hash Map의 핵심은 hash function 이며 해당 Output을 조작하여 Bucket으로 설정해서 L

Reference가장 중요한 3가지가 있다. 이를 만족하면 DP 문제다.Problem을 Sub Problem으로 나눌 수 있는가Sub Problem으로 Problem을 구할 수 있는가SUb Problem이 겹치는게 있는가 (Memorization으로 해결)Memoriz

2차원에서 최소 비용으로 가는 해당 위치의 최소 cost를 구하는 문제다.왼쪽에 있던 문제에서 0,0에서 (m-1, n-1)으로 가는 최소 비용을 구하는 것인데, 이는 2차원으로만 표현되었지 계단 문제와 동일하다.오른쪽과 아래쪽 방향으로만 움직인다는 제한이 있으므로 해

주어진 동전들로 주어진 합을 만들기위한 최소 동전 개수를 구하는 문제다.합이 11로 만들기 위한 동전이 2, 3, 5 원을 구성해서 만들 수 있는 최소 동전 수를 구해야된다.F(11) = 1 + Min(F(9), F(8), F(6)) 이런식으로 점화식을 바로 떠올려야된

Tree, Graph의 근간이 되는 자료구조remove, merge, 교차점 찾기, 루프 찾기 등이 핵심위와 같이 Val, 다른 노드 Addr을 갖고있는 녀석이 노드다.o -> o -> oval, addr을 갖고있는 노드를 o 라고하면, 서로 연결한 모습이 위와 같다.

Reference총 3가지 방법으로 마지막 방법에 유의해보고자한다.1 3 5 7 9 면, 5가 중간 지점이다.1 3 5 7 이면 5가 중간 지점이다.n 번 순회 후 counting 하여 length를 알아내고 n/2 만큼 원소로 이동한다.TimeComplexity :