죠셉의 세상이야기

-알고리듬 체크리스트

알고리즘? 알고리듬?

영어로는 algorism보다는 algorithm(알고리듬)으로 훨씬 더 자주 쓰지만 한국에서는 알고리듬보다는 알고리즘의 사용 빈도가 높다고 합니다.

이 포스팅에서는 알고리듬으로 이야기하겠습니다.

인터넷에서 검색해서 알고리듬 얼마나 공부했는지 알고 있는지 체크 리스트가 있네요.

이중에서 몇 개를 할 수 있을까요...

사실 학부생 때 배운 게 전부다 보니..기억이 안 납니다.

출처는 사내 SW검정 Professional 양성과정 라고 적혀있는데, 본 글은 작도닷넷에서 퍼왔습니다.

[알고리듬 기본]

1. 재귀함수 설계, 구현

2. 정수, 실수형 변수의 메모리 크기와 구조를 이해, 활용

3. 비트연산자(&, |, ^, <<, >>, ~) 이해, 활용

4. 10^19 이상의 매우 큰 정수를 더하고, 빼고, 곱하는 프로그램을 API 활용하지 않고 구현

[탐색 및 정렬]

5. 깊이 우선 탐색과 너비 우선 탐색 이해, 활용

6. 자신이 설계한 탐색 알고리듬의 시간복잡도 계산

7. 이분 탐색 이해, 활용

8. Bubble sort 구조와 원리 이해, 활용

9. Quick sort와 Merge sort의 장단점 이해, 활용

10. Counting sort와 Radix sort 이해, 활용

11. 히스토그램에서 최대 면적을 가지는 부분 직사각형을 선형 시간내에 구하기

[자료구조]

12. Stack, Queue, Double-ended-queue 이해, 활용

13. Vector(ArrayList)와 List(LinkedList) 장단점 이해, 활용

14. Heap(Priority Queue) 이해, push, pop 등의 연산 활용

15. DSU(Disjoint Set Union, 서로소집합) 개념 이해, Union Find 경로압축기법 구현

16. Indexed Tree 및 Sparse Table 이해하고, 값이 변하는 배열에서 구간 합, 구간 최소/최대값 구하기

[확률 이론]

17. 순열 이론(중복 순열, 원 순열, 염주 순열, 완전 순열) 이해, 활용

18. 조합 이론(중복 조합, 이항 정리, 파스칼 삼각형, 카탈란 수) 이해, 활용

19. 조건부 확률(베이스 정리) 이해, 활용

20. 이항분포(Binomial Distribution), 정규분포(Gaussian Distribution) 이해, 활용

[이산 수학]

21. 에러토스테네스의 체를 이용하여 오일러 피 함수 값 구하기

22. 페르마의 소정리를 이해하고, 이를 이용하여 모듈러에서 곱셈의 역원 구하기

23. 확장 유클리드 호제법 이해, 활용

24. 중국인의 나머지 정리 이해, 활용

25. 포함 배제의 원리를 이용하여 여러 문제에서 경우의 수를 계산

[그래프]

26. 인접 행렬 및 인접 리스트의 장단점 이해, 활용

27. Dijkstra, Floyd-Warshall, Bellman-Ford algorithm 이해, 활용

28. Prim's algorithm, Kruskal's algorithm 이해하고 이를 이용하여 MST(Minimum Spanning Tree, 최소 비용 신장 트리) 구하기

29. DAG(Directed Acyclic Graph)를 이해하고, 위상 정렬 구현

30. LCA(Lowest Common Ancestor, 최저 공통 조상) 이해하고 이를 시간복잡도 log n 시간에 구현

31. 양방향 그래프에서 절단점과 절선 구하기

32. Network Flow 이론 이해, 활용

[문자열]

33. 문자열 매칭을 KMP 알고리듬, Rabin-Karp fingerprinting, Suffix Array & LCP 이용 구현

34. 여러 문자열을 하나의 Trie로 나타나기

35. Aho-Corasick algorithm 구현

[계산 기하학]

36. CCW(Counter ClockWise)와 벡터 외적의 원리 이해, 구현

37. 단순 다각형 면적 구하는 사선식 원리

38. 두 선분의 교차 여부, 다각형 상의 점의 위치를 CCW 이용 구현

39. Convex hull을 CCW 이용하여 시간복잡도 n log n 이내에 구현

40. Plane Sweeping 이용하여 직사각형 합집합의 면적 구하기

[동적 계획법]

41. 동적 계획법에서 상향식 접근법과 재귀식 접근법의 차이 및 장단점 이해, 활용

42. 동적 계획법의 요소(기억공간, 점화식, 기저 조건) 이해 및 상황에 맞게 적용

43. 널리 알려진 동적 계획법 문제(Knapsack, LIS, Bit Mask DP) 해결

출처: 사내 SW검정 Professional 양성과정