억지기법
문제의 정의를 바탕으로 한 가장 직접적인 방법
예) 최대공약수 방법, a^n구하는 알고리즘 등...
억지기법의 중요성 : 쉬운문제 어렵게 풀필요없다, 광범위하게 문제적용가능, 실제로 더 빠를수도, 이론적인 기반이 된다
정렬, 탐색, 기하학적문제, 완전탐색, 그래프탐색
선택정렬
- 정렬문제에 대한 가장 직접적인 해결방법
- 입력리스트에서 가장 작은 항목을 찾고 이것을 꺼내 정렬된 리스트에 순서대로 저장한다(입력된 리스트와 같은 크기의 리스트 1개를 추가 필요로함)
* 제자리 정렬을 위한 알고리즘 개선
-> 정렬이 안된 리스트에서 최솟값이 선택되면 이 값을 새로운 리스트가 아닌 첫 번째 요소와 교환한다.
-> n-1번 반복(n번쨰는 자동으로 큰 값이니까!)
def selection_sort(A):
n = len(A)
for i in range(n-1):
least = i
for j in range(i+1, n):
if A[j] < A[least]:
least = j
A[i], A[least] = A[least], A[i]
printStep(A, i+1)
복잡도 : O(n^)
기본연산 추가되어도 복잡도 같다 = 반복문에서는 그래서 거의 1개로 본다
순차탐색
- 리스트에 n개의 항목이 들어있다. 이 리스트에서 "탐색키"를 가진 항목을 찾아라, 만약 찾는 항목이 있으면 그 항목의 인덱스를 반환, 없으면 -1을 반환. 단 리스트의 항목들은 정렬되어있지않음
* 억지 기법 탐색 전략
: 순차탐색(순서대로) 또는 선형 탐색
#순차탐색
def sequential_search(A,key):
for i in range(len(A)):
if A[i] == key:
return i
return -1
복잡도 : 입력의 구성에 따라 다름
최선 : T(n) = 1 , O(1)
최악 : T(n) = n, O(n)
평균 : T(n) = (n+1) / 2 , O(n)
-> 리스트의 모든 숫자가 골고루 한 번씩 key로 사용되는 경우를 가정
문자열 매칭
- 길이가 n인 입력 문자열 T와 길이가 m인 패턴 문자열 P가 있다. T에서 가장 먼저 나타나는 P의 위치를 찾아라. 패턴 없으면 -1반환해라
* 억지기법 문자열 매칭 전략 : 텍스트의 첫 번째 문자위치에 패턴을 놓고 비교한다. 이 과정을 패턴을 오른쪽으로 한 칸씩 옮기면서 성공한 매칭이 나타날 때까지 반복한다.
def string_matching(T,P):
n = len(T)
m = len(P)
for i in range(n-m+1):
j = 0
while j < m and P[j]==T[i+j]: #j가 m보다 작고 패턴문자열의 문자가 텍스트랑 같을때
j = j + 1
if j == m:
return i
return -1
복잡도 분석
최선 : 첫번째 위치에서 매칭 성공 => O(m)
최악 : 매 위치에서 m번 비교
최근접 쌍의거리
def closet(p):
n = len(p)
mindist = float("inf")
for i in range(n-1):
for j in range(i+1, n):
dist = distance(p[i], p[j])
if dist < mindist:
mindist = dist
return mindist
유클리드 거리 사용
복잡도 : O(n^2)
완전탐색
순열이나 조합 또는 모든 부분 집합을 찾는 과정을 포함하는 문제들이 많음
예) 틱택토 게임, 외판원 문제(해밀토니안 사이클)
*
TSP완전 탐색
(해밀토니안 사이클이란 그래프가 주어졌을 때 임의의 한 정점에서 출발하여 다른 모든 정점을 한번씩만 방문하고 다시 시작 정점으로 돌아오는 경로를 뜻한다.)
- 그래프가 N개의 정점을 갖는 완전 그래프라면 모든 해밀토니안 사이클은 (N-1)!개가 된다.
- 완전 탐색은 상태공간 트리의 모든 단말노드를 검사하여 길이가 최소인것을 선택하는 전략
복잡도 = O(n!)
배낭채우기 문제
복잡도 O(2^n)
일 배정 문제
복잡도 O(n!)
그래프의 순회
-보다 직관적으로 그래프를 표현하자! : 인접리스트(집합) or 딕셔너리 사용
-깊이우선탐색DFS
1. 정점을 순회할 때 stack에 정점을 넣어준다.
2. 스택의 맨 위에 있는 정점의 인근 정점 중 방문하지 않은 (아무) 하나를 순회한다.
def dfs(graph, start, visited):
if start not in visited: #만약 visited에 start가 없으면 = 초기
visited.add(start) #visited에 start넣어주기
print(start, end = ' ')
nbr = graph[start]-visited
for v in nbr:
dfs(graph,v,visited)
복잡도
-인접리스트 표현: O(n+e)
-행렬표현: O(n^2)
ex) mygraph = { "A": ["B", "C"],
"B": ["D", "C","E"],
"C": ["E", "D"],
"D": ["B", "E"],
"E": ["B", "C"] }
-너비우선탐색BFS
1. Queue에서 정점을 뽑아서 정점을 순회한다
2. 해당 정점을 순회 후에 해당 정점의 인접 정점 중 방문하지 않은 정점을 모두 큐에 넣어준다(순서무관)
import queue
def bfs(graph, start):
visited = {start} #start들어가있는 방문한 정점 딕셔너리
que = queue.Queue() #큐 만든다
que.put(start) #큐에 시작정점 넣기
whlie not que.empty(): #큐가 빈 것이 아닐동안 반복
v = que.get() # 큐에서 가져오기(먼저들어간것 먼저빼내기)
print(v,end=' ')
nbr = graph[v] - visited #nbr은 그래프에 있는 정점과 인접한 정점리스트에서 방문한 정점뺀 나머지
for u in nbr: #나머지 v의 정점들 순회할동안
visited.add(u) #방문딕셔너리에 넣기
que.put(u) # 큐에 넣기
정점의 수 = 리스트의 갯수
간선의 수 = 리스트의 길이
ex) mygraph = { "A": ["B", "C"],
"B": ["D", "C","E"],
"C": ["E", "D"],
"D": ["B", "E"],
"E": ["B", "C"] }
복잡도
-인접리스트 표현 : O(n+e)
- 인접행렬표현 : O(n^2)
'개발일기 > Python' 카테고리의 다른 글
[Python] - 이진검색트리 (0) | 2023.04.24 |
---|---|
[Python] - 축소정복 (0) | 2023.04.24 |
[Python] 기본적인 자료구조 - 그래프(Graph) (0) | 2023.04.24 |
[Python] 알고리즘 효율성 분석 (0) | 2023.04.24 |
[Python] 알고리즘 - 최대 공약수 구하기(유클리드 알고리즘) (0) | 2023.03.14 |