본문 바로가기
Algorithm

일반적으로 개발자라면 공부해볼만한 알고리즘(Problem solving)

by Ellery 2020. 11. 16.

  • 자료구조

    • 스택 stack

    • 큐queue

    • 덱deque

    • 그래프 - DFS, BFS, 위상 정렬, 크루스칼, 프림, 벨만 포드, 다익스트라, 플로이드, SCC, 단절점, 단절선, BCC

    • 트리 - LCA, 구간 쿼리 구하는 세그먼트 트리, 펜윅 트리, 트리 다이나믹, 벡터

    • 유니온 파인드

    • BST

  • 수학

    • 나머지연산
    • 최대공약수
    • 소수
    • 인접행렬, 인접리스트(그래프 저장방법)
    • 거듭제곱
  • DP

    • 조합 게임, 님 게임, Sprague-grundy 이론
    • 확률/ 기댓값 DP
    • knuth optimization
    • convex hull optimization
    • divide & conquer optimization
  • 브루트포스

    • 순열
    • 재귀
    • 비트마스크 - 상태 다이나믹
  • 일반 알고리즘

    • 그리디 알고리즘
    • 분할정복
    • 이분탐색
    • 문자열 매칭 - KMP, 라빈카프, 해싱, 트라이, 아호 코라식
    • 문자열 - 접미사 배열 문제, Z algorithm, manacher's algorithm, suffix tree
    • 네트워크 플로우 - 최대유량, 이분매칭, 최소 버텍스 커버, MCMF 최소비용 최대유량
    • Dinic 알고리즘
  • 기하

    CCW - 선분교차, 다각형의 넓이, 내부/외부, 그라함 스캔, 라인스위핑 알고리즘

이 중에서 기업에서 테스트용으로 많이 쓰이는 알고리즘은 그래프나 트리에서의 DFS,BFS, 브루트포스, DP 정도가 있고,

난이도가 아주 높지는 않은 대신 문제에 묘사된 그대로를 코드로 구현하는 시뮬레이션 능력이 필요하다. 


특히 삼성은 DFS, BFS만을 집요하게 물어보는 것으로 유명하다. 

이 이론들은 물론 알고리즘대회을 준비하는 학생들에게는 당연히 마스터해야 될 이론들이다. 당장 백준이나 코드포스 등을 가보면 문제만 1천개 푼 사람들이 수두룩하고 특히 1등은 '백준 문제만' 6000여개를 풀어서 백준 전체 문제의 50%정도를 풀었다고 한다. 10년 이상 알고리즘을 꾸준히 해온 결과라고 생각된다. 

 

나는 PS를 시작한 2주 반 동안 140여 문제를 풀었다. 아직은 브루트 포스, DP 위주의 문제로만 풀어보고 있고 오늘은 그래프 개념과 DFS와 BFS 문제들을 풀고 있다. 아직은 recursion 개념이 어려워 back-tracking 문제로 유명한 n-queens 문제를 다시 풀어보면서 base case, recursion case를 나누는 연습을 계속해서 하고 있다. 
한 3년전에 첫 언어였던 javascript 로 처음 접했던 n-queens 문제를 다시 풀어보니 감회가 새롭다.

유튜브에 부경대 권오흠 교수님의 알고리즘 강의가 있어서 문제를 풀면서 정리를 하고 있다. 

https://www.youtube.com/channel/UC-cOmaeWLm7Ii7erMQNatvA

 

권오흠

 

www.youtube.com