컴퓨터 - ACM ICPC
17/02/24 06:10(년/월/일 시:분)
43개 체크리스트 중 당신은 몇 개나 가능합니까?
[알고리듬 기본]
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 양성과정