Loading
2017.04.27 16:20 - 쿠나

알고리즘 관련 학습 사항 정리



두서없이 공부하다 보니 이대로 안 될 거 같아서 적어놓으면서 정리하기로 함.

갱신의 가능성은 ... 글쎄...

  • 기본기 (자료구조)
    • 링크드리스트, 더블링크드리스트 (std::list)
      다양한 링크드리스트 구현 방법에 대해 공부해야 둘 것.
    • dictionary (std::map)
    • Queue (일반적으로 std::priority_queue 사용)
    • Tree 
      • Disjoint Set, Union-Find 개념
      • Heap
      • Indexed Tree
        (Binary / Red-black과 같은..? 일반적으로 std::map 같은 방식으로 내장 되어 있으니 구현할 필요는 없을 것)
      • Prim / Kruskal 최소비용신장트리
    • Sorting
      • quicksort, Merge sort (분할정복의 기본 이해)
      • Radix sort (O(n) 소팅의 이해 및 응용)
    • Graph
      • DFS, BFS (recursively or using for; )
        예시: Minimum Vertex Cover, Edge cover, ...
  • 응용
    • Dynamic Programming; DP
      계산했던 값을 재사용하여 계산 시간을 줄인다는 의의가 있음을 깨달아야 함.
      (대체로 부분정복이 가능한 문제들에 대해 적용)
      • Graph
        • TSP
          저장되는 값: 현재 위치/방문한 지점에 따른 최적의 moving distance
          최적의 경로를 역추적할 수 있음, 방법도 숙지할 것.
        • Dijkstra, Bellman-Ford
        • Floyd-Warshall
          다익스트라/플로이드 둘다 경로 역추적 가능.
          다익스트라는 음수간선 사용 불가능.
      • 문자열 매칭
    • 백트래킹: 색칠 문제, N Queen 문제
      일종의 그리디? 유형으로 시간복잡도가 크기 때문에 이 점을 유념해서 사용해야 됨...
      필요시 DP나 여타 다른 알고리즘이랑 보조하여 사용
    • 기하 / 그래프 문제
    • 기본적인 수학적 성질 / 정수론
      • 페르마의 소정리
        (a가 소수 p로 나누어 떨어지지 않을때, a^(p-1) mod p = 1)

참조할 만한 문제들: Baekjoon Online Judge

이것 말고 다른 비슷한 것

저작자 표시 비영리 동일 조건 변경 허락
신고

'CSE > 알고리즘' 카테고리의 다른 글

알고리즘 관련 학습 사항 정리  (0) 2017.04.27
리듬게임 파일(BMS)의 처리 방법에 대하여  (9) 2013.08.29
BOF Attack on gdb  (0) 2013.08.04

댓글을 입력하세요