오블완 썸네일형 리스트형 알고리즘 10주차 09. 억지 기법과 탐욕적 전략 09-1 문제 해결 과정문제의 이해 - 설계 방향 결정 - 알고리즘 설계 - 정확성 검증 - 알고리즘 분석 - 알고리즘 구현 *설계 방향 결정- 순서적 알고리즘 / 병렬적 알고리즘- 최적해 / 근사해 *알고리즘 설계 기법- 억지 기법: 문제의 정의를 직접 사용. 원하는 답을 구할 때까지 모든 경우 테스트.- 탐욕적 기법: 단순하고 직관적인 방법. 어떤 결정을 해야할 때마다 그 순간에 최적인 것을 선택.- 분할 정복: 큰 문제를 해결 가능한 작은 문제들로 반복적으로 분할하여 해결.- 동적 계획법: 분할 정복과 유사. 작은 문제를 해결한 결과를 저장하여 큰 문제를 해결할 때 사용.- 공간으로 시간 벌기: 추가 공간을 사용하여 처리시간을 단축- 백트래킹과 분기한정 09-2 억.. 더보기 알고리즘 9주차 08. 그래프 그래프: 정점(vertex)과 간선(edge)의 집합: G = (V, E) 그래프의 종류무방향 그래프 / 방향 그래프완전 그래프 /부분 그래프가중치 그래프 (network) 그래프의 용어- 인접: 간선으로 연결된 두 정점의 관계- 정점의 차수: 정점에 연결된 간선의 수- 경로: 간선을 따라갈 수 있는 길을 나열한 것 - 경로 길이: 경로를 구성하는 간선의 수- 단순 경로: 반복되는 간선이 없는 경로- 사이클: 시작 정점과 종료 정점이 같은 단순 경로- 연결 그래프: 모든 정점 사이에 경로가 존재함- 트리: 사이클을 가지지 않은 연결 그래프. 트리는 연결 그래프에 속한다. 그래프의 표현 (1) - 인접 행렬: 2차원 배열: 행렬의 각 성분이 두 정점의 연결관계를 나타냄- 무방향 그래프에서는 .. 더보기 이전 1 다음
