삼성 DX 동계 알고리즘 강의를 듣다보니 처음듣는 알고리즘이 정말 많다. KMP, 라빈카프 등등.. 이런 알고리즘들을 잘 정리해둔 블로그들이 있어 블로그의 내용에 따라 공부해볼만한 알고리즘과 빈도를 정리해본다.

공부해야하는 알고리즘

❓ : 내가 모르는 알고리즘
📝 : 암기가 필요한 알고리즘

• array, list
• two pointer, sliding window
• 누적합
• 이분탐색
• stack, queue, heap, deque, hash
• 📝 DFS/BFS
• back tracking/branch and bound
• 구현 및 시뮬레이션 : 요구사항 구현 / 문자열 처리
• 📝 유클리드 호제법: GCD/LCM 구하기
• 📝 에라토스테네스의 체 : 소수 판정
• 📝 조합, 순열

가끔 나옴

• 📝 다익스트라
• 📝❓ 플로이드 와샬
• 📝 크루스칼
• 📝❓ 프림
• 📝 유니온 파인드
• 📝❓ LCS
• 📝❓ LIS
• 진법 변환
• DP
• greedy

빈도 낮음

• 비트마스킹
• ❓ 위상정렬
• 📝 Trie
• 📝 누적합 -> 제곱근 분할법 -> 세그먼트 트리
• 📝❓ 라빈카프, KMP, 보이어-무어

시간복잡도의 유용성과 한계

시간복잡도는 유용한 도구이지만 말 그대로 가늠해보는 도구이다. 예를 들어 해시나 자바에서 객체 생성과 같은 경우 생각보다 O(1)도 시간이 매우 크다. 시간복잡도는 그대로더라도 최적화 테크닉을 통해 유의미한 차이를 만들기도한다.

충분히 접근법을 고민해서 나온 결과라면 1억번의 연산보다 조금 많더라도 그걸 구현 후 최적화하는 방식의 시도를 추천한다.

문제 풀이 절차

1. 문제 분석

결국 수학이나 컴퓨터는 필요한 부분을 살리고 불필요한 부분은 최대한 줄이는 추상화가 중요하다. 요구사항을 최대한 단순하게 정리해야한다.

EX)

• 좌표평면 위에 점들이 존재한다.

• 이들은 추가되거나 삭제 될 수 있다.

• 특정 거리 내의 집들은 하나의 그룹으로 합쳐진다.

  이렇게 정리를 하고나면 필요한 자료구조, 알고리즘들이 떠올릴 수 있다. 여기서 놓치지 말 것은 제약사항을 정확히 파악하는 것이다.

EX)

• ~한 경우는 주어지지 않는다.

이런 제약사항은 구현시에도 주의해야하지만, 설계단계에서 문제를 단순하게 처리할 수 있도록 도와주는 경우가 많다. 이를 최대한 활용해서 가장 효율적인 알고리즘과 자료구조를 파악한다. 또한 아이디어도 세워본다.

이 단계에서 시간복잡도를 활용해 풀이가 가능할만한 방법을 생각한다.
간단히 예제에 대해 직접 손으로 시뮬레이션 해보는 것도 좋다.

2. 구현

입사 수준의 코딩테스트에서 오히려 굉장히 중요한 것이 구현이다. 구현을 간단히 하기 위해서는 설계 단계에서 어느정도 필요한 공통 메서드들을 분리하고 중간 중간 입출력을 통해 점검해주는 것이 좋다.

제한사항과 엣지 케이스를 놓치지 않고 정확하게 구현하는 것도 중요하다. 항상 엣지 케이스를 생각하고 깔끔하게 구현하는 노력을 해보자.

3. 최적화 & 점검

테스트 케이스를 보완하여 좀 더 오류가 없는지 검증하여 정확도에 문제가 없는지 점검할 수 있다.

그 외에 큰 틀의 알고리즘은 설계단계대로 적용했더라도 여러가지 최적화를 시도해볼 수 있다.

EX)

• 정적배열을 활용한 L1, L2, L3 캐쉬 히트 늘리기
• 해쉬함수 직접구현(EX 롤링해쉬)을 통한 성능 최적화
• 레드블랙트리 사용 줄이기
• 객체 생성이나 메모리 할당 줄이기

이런 최적화는 실제 시간복잡도를 못 줄일지는 몰라도, 꽤나 유효한 차이를 보인다. 최초 구현은 가장 가독성이 좋고 구현하기 간결한 코드를 선택하되 시간이 남을땐 속도를 개선하려는 노력을 해보자.

4. 다른 좋은 풀이 참고

내가 혼자 코드를 발전시키는 것은 바퀴를 재발명하는 것이다. 주변 자료나 사람으로부터 좋은 풀이(코드나 접근법)를 참고하자.