프로그래머는 어떤 알고리즘을 마스터해야 합니까?

열거하다. (poj 1753, poj2965)

탐욕 (POJ 1328, POJ 2 109, POJ 2586)

재귀와 분치법.

재귀적.

시공 방법. (poj3295)

모의법. (POJ 1068, POJ 2632, POJ 1573, POJ 2993, POJ 2996)

2. 그래픽 알고리즘:

그림의 깊이는 먼저 순회하고 폭은 먼저 순회한다.

최단 경로 알고리즘 (Dijkstra, Bellman-Ford, Floyd, Heap+Dijkstra)

(poj 1860, poj3259, poj 1062, poj2240, poj1/kloc-0)

최소 스패닝 트리 알고리즘 (prim, kruskal)

(poj 1789, poj2485, poj 1258, poj3026)

토폴로지 정렬 (poj 1094)

두 부분 그래프의 최대 일치 (헝가리 알고리즘) (poj304 1, poj3020)

최대 흐름 확장 경로 알고리즘 (KM 알고리즘). (poj 1459, poj3436)

셋. 데이터 구조.

문자열 (POJ 1035, POJ 3080, POJ 1936)

정렬 (빠른 정렬, 병렬 정렬 (역방향 순번과 관련), 힙 정렬) (poj2388, poj2299)

간단하고 합집합적인 응용 프로그램.

해시 테이블 및 이진 검색 방법 (디지털 해시, 문자열 해시) 과 같은 효율적인 검색 방법

(poj3349, poj3274, POJ2 15 1, poj 1840, poj2002, poj2503

호프만 나무 (poj3253)

다량

트리 나무 (정적 트리, 동적 트리) (poj25 13)

넷. 단순 검색

깊이 우선 검색 (POJ 2488, POJ 3083, POJ 3009, POJ 132 1, POJ 225 1)

폭 우선 검색 (POJ 3278, POJ 1426, POJ 3 126, POJ 3087). POJ 34 14)

간단한 검색 기술 및 가지 치기 (POJ 253 1, POJ 14 16, POJ 2676,1/kloc

동사 (verb 의 약어) 동적 프로그래밍

배낭 문제. (poj 1837, poj 1276)

다음과 같은 유형의 간단한 DP 가 있습니다 (lrj 의 책 149 페이지 참조).

E[j]=opt{D+w(i, j)} (poj3267, poj 1836, poj 1260,)

E [i, j] = opt {d [i- 1, j]+xi, d [i, j- 1]+yj, yj

C [i, j] = w [i, j]+opt {c [i, k- 1]+c [k, j]}. (최적 이진 조회 트리 문제)

자동동사 수학

조합 수학:

1. 덧셈 원리와 곱셈 원리.

2. 조합을 정렬합니다.

3. 재귀 관계.

(POJ3252, poj 1850, poj 10 19, poj 1942)

수론.

1. 소수 및 나눗셈 문제

2. 이진 숫자.

합동 모드 연산.

(poj2635, poj3292, poj 1845, poj2 1 15)

계산 방법.

1. 단조로운 함수의 이분법을 풀다. (POJ 3273, POJ 3258, POJ 1905, POJ 3 122)

일곱. 형상을 계산하다.

기하학적 공식.

교차 곱과 점 곱의 적용 (예: 선 세그먼트의 교차점 판단, 점 대 선 세그먼트의 거리 등). ). (poj203 1, poj 1039)

폴리곤의 간단한 알고리즘 (면적 찾기) 및 관련 판단 (점이 폴리곤 내에 있는지 여부)

(poj 1408, poj 1584)

볼록 가방. (POJ 2 187, POJ 1 1 13)

중급 (학교 경기 피날레, 지방 경기 중간 난이도):

첫째, 기본 알고리즘:

C++ 표준 템플릿 라이브러리 응용 프로그램. (poj3096, poj3007)

더 복잡한 시뮬레이션 문제 교육 (POJ 3393, POJ 1472, POJ 337 1, POJ 1027, POJ 2706)

2. 그래픽 알고리즘:

미분 구속 시스템의 확립과 해법. (poj 120 1, poj2983)

최소 비용 및 최대 트래픽 (POJ 25 16, POJ 25 16, POJ 2 195)

이중 연결 구성 요소 (poj2942)

강하게 연결된 분기와 그 수축 점. (poj2 186)

그림의 절단 모서리 및 절단 점 (poj3352)

최소 컷 모델, 네트워크 흐름 프로토콜 (poj3308)

셋. 데이터 구조.

나무를 세분화하다. (POJ 2528, POJ 2828, POJ 2777, POJ 2886, POJ 2750)

정적 이진 조회 트리. (poj2482, poj2352)

나무 그룹 (POJ 1 195, POJ332 1)

RMQ. (poj3264, poj3368)

합집합의 고급 응용 프로그램. (poj1703,2492)

KMP 알고리즘. (poj 196 1, poj2406)

넷. 검색

최적 및 실행 가능한 자르기

검색 기술 및 최적화 (POJ34 1 1, POJ 1724)

스토리지 검색 (poj3373, poj 169 1)

동사 (verb 의 약어) 동적 프로그래밍

복잡한 동적 계획 (예: 특수 여행자 문제 해결을 위한 동적 계획 등) ) 을 참조하십시오

(poj 1 19 1, poj 1054, poj3280, poj2948, poj

상태의 동적 구성을 기록합니다. (POJ3254, POJ24 1 1, POJ 1 185)

트리 동적 계획 (POJ 2057, POJ 1947, POJ 2486, POJ 3 140)

자동동사 수학

조합 수학:

1 .. 배제 원칙.

비둘기장 원칙.

3. 변위군과 폴야 정리 (POJ 1286, POJ 2409, POJ 3270, POJ 1026).

4. 재귀 관계 및 생성 함수.

수학.

가우스 제거법 (POJ 2947, POJ 1487, POJ 2065, POJ 1 166, poj/kloc-

2. 확률문제. (poj307 1, poj3440)

3.GCD, 확장된 유클리드 (중국 잉여 정리) (poj3 10 1)

계산 방법.

1.0/ 1 십진 프로그래밍. (poj2976)

삼각법은 단일 피크 (단일 밸리) 극값을 해결하는 데 사용됩니다.

3. 행렬법 (poj3 150, poj3422, poj3070)

4. 반복 근사 (poj330 1)

무작위 알고리즘 (poj33 18, poj2454)

기타 문제 (POJ 1870, POJ 3296, POJ 3286, POJ 1095)

일곱. 형상을 계산하다.

좌표 이산화.

스캔라인 알고리즘 (예: 직사각형의 면적 및 둘레 찾기, 일반적으로 선 세그먼트 트리 또는 파일과 함께 사용됨)

(poj 1765, poj 1 177, poj115/

다각형의 코어 (반평면 교차) (poj3 130, poj3335)

기하학 도구의 종합 응용. (POJ 18 19, POJ 1066, POJ 2043, POJ 3227, poj2/kloc-;

고급 (지역 중간 난이도):

1. 기본 알고리즘 요구 사항:

코드는 빠르고 간결하지만 스타일을 잃지 않는다.

(poj2050, poj 1684, poj 142 1, poj 1048, poj

정확성과 효율성을 확보하다. Poj3434

2. 그래픽 알고리즘:

도 제약 최소 스패닝 트리 및 k 번째 최단 경로입니다. (poj 1639)

최단 경로, 최소 스패닝 트리, 이분도, 최대 흐름 문제에 대한 관련 이론 (주로 모형 설정 및 해결)

(poj3 155, poj2 1 12, poj 1966, poj2289/kll

최적 비율 스패닝 트리. (poj2728)

최소 트리 차트 (poj3 164)

두 번째 작은 스패닝 트리.

무향 그래프와 직접 그래프의 최소 원

셋. 데이터 구조.

트리 그래프의 수립 및 적용 (poj2778)

LCA 와 RMQ 문제 (LCA (최근 공통 조상 문제) 는 오프라인 알고리즘 (결합 +dfs) 과 온라인 알고리즘 (RMQ+dfs) 이 있습니다. (poj 1330)

Deque 및 해당 응용 프로그램 (유지 관리 단조로운 대기열은 동적 계획에서 상태 전환을 최적화하는 경우가 많습니다.) (poj2823)

왼쪽 틸팅 트리 (결합 가능한 힙)

접미사 트리 (매우 유용한 데이터 구조, 또한 경주 문제 핫스팟). (poj34 15, poj3294)

넷. 검색

비교적 번거로운 검색 제목 훈련 (POJ 1069, POJ 3322, POJ 1475, POJ 1924, POJ 2049, poj2049

넓은 검색의 상태 최적화: M 진수로 상태를 저장하고, 해시 테이블로 전환하여 중복을 판단하고, 스토리지 상태를 비트 단위로 압축하고, 양방향 와이드 검색과 A* 알고리즘을 사용합니다. (POJ 1768, POJ 1 184, POJ 1872, poj/kloc.

깊이 검색의 최적화: 가능한 비트 연산을 사용하고, 반드시 가지를 잘라야 하며, 함수 인수는 가능한 적고, 층은 너무 적다. 양방향 검색이나 회전 검색과 IDA* 알고리즘을 고려해 볼 수 있습니다. (POJ3 13 1, POJ2870, POJ2286)

동사 (verb 의 약어) 동적 프로그래밍

데이터 구조 최적화가 필요한 동적 프로그래밍 (poj2754, poj3378, poj30 17)

사변형 부등식 이론.

어려운 상태 DP(poj3 133)

자동동사 수학

조합수학.

1. 뫼비우스 반전 (poj2888, poj2 154)

2. 부분 순서 관계 이론.

게임 이론.

1. 최대 최소 프로세스 (poj33 17, poj 1085)

님 문제.

일곱. 형상을 계산하다.

반평면의 교차점 (poj3384, poj2540)

가시성 작성 (poj2966)

점 세트의 최소 원 커버리지입니다.

뒤꿈치 점 (poj2079)