Algorithm의 개념에 대한 지식들을 정리합니다.
Algorithm의 개념에 대한 지식들을 정리합니다.
그래프 용어 V : vertex E : Edge path 연결 그래프 : 어떤 두 정점 사이에도 경로가 존재하는 그래프 부분 그래프 가중치 포함 그래프 : Edge에 가중치가 달려있음 순환 경로 순환 그래프, 비순환 그래프 트리 - 비순환, 비방향그래프 신장 트리 : 연결된, 비방향성 그래프에서 순환경로를 제거하면서 연결된 부분 그래프가 되도록 하는 트리 신장 트리의 개수는 Cayley’s formula에 따른 개수를 가짐 최소비용신장트리 신장 트리가 되는 부분 그래프 중에서 가중치가 최소가되는 부분 그래프 무조건 트리로 나온다.
가지를 끊어버리는 백 트래킹에 대해 알아보자.
분기 한정법에 대해 알아보자. 분기 한정법 Branch : 이전 상태 공간 트리에서 다음 가지로 넘어가는 경우를 말함 Bound : 한계 이전의 백 트레킹과 크게 다르지 않다. 그 부분 집합의 합을 구하는 문제와 크게 다르지는 않다.
정렬에 대해 깊게 공부해보자.
탐색하는 방법에 대해 알아보자. 검색 문제 n개의 키를 가진 배열 S와 키 x가 주어졌을 때, x=S[i]가 되는 첨자 i를 찾는 것 없다면 오류로 처리한다. 결론 : 이분 검색 알고리즘보다 효율적인 알고리즘은 없다. 이진 검색 상태 공간 트리 순차 검색은 답이없다.