DP3 코딩테스트 빈출 유형 정리 [코딩테스트 주요 알고리즘]- 구현 및 시뮬레이션 - 문자열 처리(해시테이블 or 스택)- 완전 탐색(브루트 포스)- 이진 탐색(매개변수 탐색)- 그래프 탐색(DFS, BFS)- 백트래킹- DP- 그리디- 투포인터 [가끔 나오는 알고리즘]- 정렬- MST(크루스칼)- 최단경로(다익스트라, 벨만-포드, 플로이드-와샬)- 위상정렬- 모든 쌍 최단경로 문제- 분리집합- 트리의 지름 구하기- 트라이 2024. 8. 4. [알고리즘] ep5-3++) 분할통치법 vs DP 문제) 여행의 최소비용을 구하는 알고리즘을 작성하라.airtelDC(분할통치 버전)와 airtelDP(동적프로그래밍 버전)를 구현하고 실행시간을 비교 프로그램 요구사항: 1) 각 해결버전의 정방향, 역방향 버전 가운데 자유롭게 하나를 선택하여 구현하라. 2) 출력예시: 최종적으로 다음과 같이 인쇄되어야 한다. ※ 참고1) 아래는 MAX = 30인 경우의 인쇄결과임.2) X.XXXXXXXX는 cputime in milliseconds. 주의:반드시 아래 가이드라인의 main 함수 내용과 동일하게 실행하고 출력을 구하라.n = 6로 한 테스트실행 결과가 수작업실행 결과와 일치하는지 확인한 후 n = MAX로 한 본실행을 시도할 것.경로가 아닌 최소비용만을 요구하는 문제이므로, 만약 최소비용 경로가 두 .. 2024. 7. 24. [알고리즘] ep5-3) 방향그래프 ㅁ방향그래프(directed graph): 모든 간선이 방향간선인 그래프 응용: 일방통행 도로, 항공노선, 작업 스케줄링 방향 DFS 알고리즘에서, 네 종류의 간선이 발생한다1. 트리간선(tree edges): 새로운 정점 방문 시 사용되는 간선2. 후향간선(back edges): 현재 정점에서 이미 방문한 정점으로 돌아가는 간선3. 전향간선(forward edges): 조상의 정점에서 자손의 정점으로 향하는 간선4. 교차간선(cross edges): 같은 레벨 또는 다른 서브트리의 정점으로 향하는 간선 방향그래프 G의 두 정점 u와 v에 대해 만약 u에서 v로의 방향경로가 존재한다면, "u는 v에 도달한다(reach)" 또는 "v는 u로부터 도달 가능(reachable)하다"라고 말한다 방향그래프 G.. 2024. 7. 23. 이전 1 다음
