이동통신사 결합요금제 불편완화 프로젝트

목차

1.배경

2.해결방안

3.자료구조 선택

4.알고리즘 선택

5.기대효과

본문내용

그래프 특징
Greedy 알고리즘 사용
Node 수가 많지 않은 편
Node에 연결된 간선의 수는 적다
입력은 1번, 조회는 여러 번
모든 간선의 수를 알 필요는 없다.
가중치 합이 2이하까지만 진행

그래프 알고리즘 선택 1
깊이우선탐색(DFS, Depth First Search)
해가 존재할 가능성 있으면 계속 전진 탐색
스택 구조, 재귀 호출 이용
재귀 호출이 이루어질 때마다 위치가 점점 깊게 들어감
너무 깊게 들어가면 overflow 발생하므로, 막히면 나아갈 곳이 있는 곳으로 돌아가서 과정 반복, 모든 곳을 방문했을 때 탐색 종료
단점 : 목표 노드가 없는 경로에 깊이 빠질 수 있음 <- 깊이 제한
너비우선탐색(BFS, Breadth First Search)
생성된 순서에 따라 노드 확장
큐 구조, 큐의 첫 정점을 보고 그 정점에 인접한 정점들 탐색
새롭게 발견되는 정점 enqueue, 모든 인접 정점 탐색 끝나면 첫 정점 dequeue
단점 : 많은 기억 공간 필요

키워드

이동통신사,   통신요금,   알고리즘 구현