자료구조 스터디 3주차

 

3-1)깊이 우선 탐색  DFS

가장 많이 사용되는 탐색 방법.

깊이우선 탐색: 그래프 완전 탐색 기법중 하나. 시작 노드에서 출발하여 한 쪽 분기를 정해 최대 깊이까지 탐색을 마친 후 다음 분기로 너머가 탐색을 수행.

재귀 함수, 스택 자료구조를 이용한다.

 

시간 복잡도: O(노드 수+엣지 수)

깊이 우선 탐색에서 재귀함수를 이용하므로 스택 오버플로우에 유의해야 함.

 

한번 방문한 노드를 다시 방문하지 않으므로 노드 방문 여부를 페크할 배열이 필요하다. 대부분 인접리스트로 표현.

후입선출의 특성을 가진다. 실제로는 스택 자료구조보다 스택의 성질을 갖는 재귀함수로 구현하는 경우가 더 많다.

 

 

[수행과정]

 

1. dfs를 시작할 노드를 정한 후 사용할 자료구조(인접리스트)를 초기화한다.

 

2와 3의 순서는 상관 없음

 

2. 스택에서 노드를 꺼내고 꺼낸 노드의 인접 노드를 스택에 삽입한다.

 

3.스택 자료구조에 값이 없을때 까지 반복한다.

 

이미 사용한 노드를 재삽입하지 않는 것이 핵심임.

pop한 노드의 인접노드가 없을 경우 스택속 다른 노드를 pop.

스택에 노드를 push할 때 방문 배열을 체크하고, 스택에서 노드를 pop할 경우 탐색 순서에 기록하며 방문 배열과 대조해본다.

 

3-2)너비 우선 탐색 BFS

시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하며 탐색하는 알고리즘.

경로가 여러개일 경우 최단 거리를 보장한다.

선입선출 방식 : 큐를 이용함.

방문한 노드를 테크할 방문 배열이 필요함.

시간 복잡도: O(노드 수+엣지 수)

그래프를 인접 리스트로 표현한다.

 

[수행과정]

 

1.시작 노드를 정한 후 자료구조(인접 리스트)를 초기화.

 

 

2. 큐에서 노드를 꺼낸 후 그 노드의 인접 노드를 큐에 삽입.

 

3. 큐 자료구조에 값이 없을 때까지 반복 

 

 

3-3)이진 탐색

데이터가 정렬되어있는 상태에서 원하는 값을 찾아내는 알고리즘.

대상 데이터의 중앙값과 찾고자하는 값을 비교해 데이터 크기를 반씩 줄이며 탐색.

시간복잡도 : O(log n)

 

[수행과정]

1.현재 데이터의 중앙값을 선택

2. 중앙값이 타깃보다 크다면 왼쪽 데이터를 선택

3,중앙값이 타깃값보다 작다면 오른쪽 데이터를 선택 

 

 

4-1) 탐욕 알고리즘

그리디 알고리즘

 

현재 상태에서 보는 선택지중 최선의 선택지가 전체 선택지의 최선의 선택지라 가정하는 알고리즘.

전체에서 항상 최적의 해를 보장하지는 못함.

 

[수행과정]

1. 현재 상태에서 최선이라 생각되는 해를 선택

2. 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지를 확인한다

3. 현재까지 선택한 해 집합이 전체 문제를 해결할 수있는지 검사하고, 전체문제를 해결하지 못한다면 1로 돌아가 재수행한다.

 

 

 

 

 

 

 

 

[지금 무료] Do it! 알고리즘 코딩테스트 with Python | 하루코딩 - 인프런

3강/4강 수강