지수의 블로그

3 분 소요

TIL

코드스테이츠

알고리즘

1. 코딩테스트 난이도에 대해

일반적으로 프로그래머스 기준 레벨 3 / 해커랭크 기준 medium 정도의 문제를 풀 수 있다면 웬만한 코딩 테스트는 통과할 수 있을 것입니다.
코딩 테스트를 어렵게 내는 기업은 4문제 중 1문제 꼴로 프로그래머스 3.5~4 레벨 / 해커랭크 Hard 정도의 문제가 나오기도 합니다.

2. 알고리즘 문제를 풀 때

주입식 교육을 통해 알고리즘을 학습하는 것이 효과적인 경우가 있습니다. 단기간이라면 더욱 효과가 큽니다.
많은 문제를 풀고, 유형에 대응할 수 있어야 합니다.
일부 코딩 테스트는 잘 알려진 유형들만 출제되고, 이 유형들을 접근하는 템플릿이 존재합니다.
알고리즘 문제가 어렵다고 해서 좌절할 필요는 없습니다. 문제 유형을 빠르게 익히면 됩니다.

시간이 많다면:
우리의 뇌는 해결되지 않은 문제를 싫어합니다. 그래서 의식적으로 노력하지 않아도 문제가 풀릴 때까지 뇌는 계속해서 일을 합니다. 따라서, 레퍼런스 코드를 보지 않고 많은 문제들을 차근차근 풀며 유형을 익히는 게 가장 좋습니다. 막히는 문제가 있다고 하더라도 꾸준히 고민하여 하나씩 해결해야 합니다.

만약 시간이 없는데, 코딩 테스트가 있다면:
GeeksforGeeks에서 레퍼런스 코드를 보고 빠르게 이해합시다. GeeksforGeeks 기준, 여러분들이 많이 봐야할 유형은 다음과 같습니다.
Backtracking, Dvide and Conquer, Graph Algorithm: 대부분의 문제는 이 세가지 유형에서 거의 다 나오기 때문에, 해당 알고리즘 위주로 학습하시면 됩니다.
Greedy, Dynamic Programming: 약간 난이도가 높은 문제이기 때문에, 위의 세 가지 유형을 공부한 후 학습하시면 좋습니다.
Searching, Sorting: 주어진 함수를 쓰는 것이 좋습니다. (자바스크립트에서는 Array.prototype.sort)
[Advanced] Randomized Algorithms: 휴리스틱한 유형이기 때문에 입사 코딩테스트 문제로는 거의 나오지 않습니다.

3. 시간 복잡도

대부분의 문제는 실행 시간: 1초에 가깝게 디자인됩니다.
1초가 걸리는 입력의 크기 (외워 버리는 게 훨씬 좋습니다)

O(N): 100,000,000
O(NlgN): 5,000,000
O(N^2): 10,000
O(N^3): 500
O(2^N): 26
O(N!): 11

보통 1억 번의 연산당 1초가 걸린다고 생각하면 됩니다. 만약 문제에서 시간의 상한을 두었다면, 그것도 고려 범위에 포함해야 합니다.

1 ≤ N ≤ 10만일 때 걸리는 시간
O(1) 1 → 1e-8초
O(N) 10만 → 0.01초
O(N^2) 100억 → 100초 (불가능, O(N) 또는 O(NlogN)으로 풀어야 함)

이렇듯 문제의 시간 혹은 입력 범위 제한을 보고, 어떤 방법까지 생각하면 좋을지 미리 결정이 가능합니다.

예로, 1≤N≤500이 주어졌다면, O(N), O(N^2), O(N^3), O(NlogN) 등등으로 풀 수 있고, O(N^4)를 가진 로직은 사용할 수 없습니다.

💡 O(N^3) 알고리즘, 풀어야 할까?

상황에 따라 다릅니다. O(N^3)이 가장 빠를 때도 있기 때문입니다.
Big-O는 입력이 커질 때, 값이 커지는 속도입니다. 입력이 작을 때는 값이 커지는 속도에 큰 차이가 없기 때문에 어떻게 풀어도 상관없습니다. 0.01초나 0.05초나 (적어도 코딩 테스트에서는) 코드가 시간 내로 작동하기 때문입니다. 하지만 입력이 충분한 경우 시간 복잡도에 따라 수행 시간의 차이가 극명해집니다.
이때 입력은 대부분의 경우 문제에 직접적으로 주어지는 N 또는 M의 가장 큰 값입니다. 그래서 Big-O가 중요합니다.
보통 문제에서는 입력값의 상한이 정해집니다.
입력의 상한이 500일 때 O(N^3)으로 풀어도 괜찮습니다.
그러나 입력이 이 이상인 경우,
루프를 하나 없애서 O(N^2)로 만들거나,
루프를 한 번 돌 때마다 탐색 공간을 줄이는 logN (대표적으로 Binary Search, Divide and Conquer)을 사용해 O(N^2 * logN)으로 만들어야 합니다.
결론적으로, 입력을 보고 O(N^3)으로 해결할 수 있는 알고리즘인지 판단할 수 있어야 합니다.

4. 공간 복잡도

자바스크립트에서 보통 변수 하나는 8Byte 입니다.

KB = 1000 byte
MB = 1000K = 100만 byte
GB = 1000M = 10억 byte

알고리즘 문제에 메모리 조건이 나오는 경우가 많습니다.
일반적으로는 128MB, 256MB, 512MB가 자주 등장합니다.

가령 길이가 1000인 배열 arr이 있다고 가정합시다. 배열 arr의 각 변수 하나당 8byte이기 때문에, 이 배열 arr의 크기는 8KB가 돕니다.

만약 행과 열이 1000인 이차원 배열이라면, 810001000이므로 8MB가 됩니다.

그렇다면, 배열의 요소의 갯수가 천만개인 경우 80MB가 됩니다. 이 경우에는 주의해야 합니다. 만약 메모리 조건이 128MB인 경우, 그 중 80MB를 변수에 사용하는 것이기 때문입니다.

5. 문제를 처음 봤을 때

입력과 공간 상한을 확인합니다.
먼저, 완전 탐색으로 문제를 풀어봅니다. (만약, 알고리즘이 바로 떠올랐다면 그렇게 풀면 됩니다.)

완전 탐색으로 풀어야 하는 이유는: 그렇게 해도 시간이 오래 걸리지 않는 경우가 많고, 완전탐색으로 풀어보면서 문제를 이해해야 합니다.

문제에 순서를 부여해야 합니다.
입력의 순서나, 입력의 크기를 가장 작은 것부터(또는 가장 큰 것부터) 차례대로 하면 됩니다.
순서가 없는 경우에는 직접 순서를 부여해야 합니다. 모든 문제는 순서를 부여해야 하고, 순서대로 풀어야 합니다.

반복문을 쓰셔도 됩니다. 배열 메서드는 권장하지 않습니다. 왜냐하면, 시험 상황에서는 함수 스코프 때문에 변수가 헷갈릴 수 있습니다.
알고리즘 문제에서는 다른 것에 신경쓰지 않고, 문제 풀이에만 신경쓸 수 있어야 합니다.

문제 푸는 시간의 30~50%는 문제를 분석하는 데만 사용합니다.

절대 코드부터 치지 마세요. 문제를 보자마자 코드를 쓰는 경우가 많습니다만, 대부분은 처음 생각대로 되지 않습니다. 그런데 열심히 쓴 코드가 아깝거나, 거의 다 된 것처럼 느껴져 쉽게 수정하기도 어렵습니다.
코드는 도구일 뿐입니다. 문제를 확실하게 파악하고, 예외 케이스를 모두 분석했다면 코드는 자연스럽게 작성됩니다.

6. 기본적으로 알아둬야 할 유형

외워야 하고, 코딩테스트 직전에 보고가야 합니다.

GCD
순열/조합
(정렬은 Array.prototype.sort 사용)
우리가 직접 quick sort, merge sort 구현한 것보다, 자바스크립트 개발자들이 C언어로 짠 정렬이 더 효율이 좋습니다.
DFS(재귀), BFS(큐): 템플릿
분할정복(재귀), 다이나믹 프로그래밍 ⇒ 감을 잡기 어렵기 때문에 케이스 스터디가 필요합니다.

회고 (TIL)

2022.03.31 Daily 회고

✏오늘 한 일

  • 알고리즘 공부방법 정리

⁉느낀 점

이제 알고리즘 공부 시작해야한다. 떨린다!

🎃현재 나의 상태

내일이면 내 운명이 결정나겠지. 심호흡!

댓글남기기

참고