Python algorithm 개념 및 실습 - 그래프(친구찾기, 친밀도)

Python

Python algorithm 개념 및 실습 - 그래프(친구찾기, 친밀도)

developers developing 2022. 9. 19. 19:00

알고리즘이란 ?

어떤 일을 하기 위한 명령의 집합
문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 것
어떤 문제를 해결하기 위한 절차나 방법

알고리즘 복잡도

Complexity
- 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한가?
알고리즘의 성능을 객관적으로 평가하는 기준
- 시간복잡도(time complexity) : 실행 횟수로 판단
- 공간복잡도(space complexity) : 기억공간과 파일 공간의 사용량
빅오 표기법 ( Big O Notation)
- 알고리즘이 얼마나 빠른지 표시하는 방법
- 입력 데이터 크기 증가할 때 알고리즘 연산 시간(횟수)의 증가 방식
- 연산의 횟수를 비교함
- O(n) : 계산 복잡도
  - O : 빅 O
  - n : 연산 횟수
  - O(1) : 입력 크기 n과 계산 복잡도가 무관 할때 ex) n(n+1)/2
  - O(logn) : 입력 크기 n의 로그 값에 비례하여 증가 ex) 이분탐색
  - O(n) : 입력 크기 n에 비례하여 복잡도 증가 ex) 최댓값, 순차탐색
  - O(nlogn) : 입력 크기 n과 로그 n 값의 곱에 비례하여 복잡도 증가 ex) 병합정렬, 퀵정렬
  - O(n²) : 입력 크기 n의 제곱에 비례하여 복잡도 증가 ex) 선택정렬, 삽입정렬
  - O(n₂) : 입력 크기가 n 일 때, 2의 n 제곱 값에 비례하여 복잡도 증가 ex)하노이의 탑

그래프

각 꼭짓점(vertex)들의 관계를 연결한 형태
파이썬에서는 리스트와 딕셔너리를 이용해서 표현 가능

친구찾기 : 여덟 명의 사람들이 친구 관계를 맺고 있을 때 리스트와 딕셔너리를 이용하여 그래프 표현

frend_info = {

"Summer": ["John", "Justin", "Mike"],

"John": ["Summer", "Justin"],

"Justin": ["John", "Summer", "Mike", "May"],

"Mike": ["Summer", "Justin"],

"May": ["Justin", "Kim"],

"Kim": ["May"],

"Tom": ["Jerry"],

"Jerry": ["Tom"],

}

# g = 그래프, name = 이름

def all_friends(g, name):

# 앞으로 처리 해야 할 사람들을 큐(리스트)에 저장

queue = []

# 큐에 추가한 사람들 기록(set) - 중복 안하려고

end = set()

# name 을 queue, end 추가

queue.append(name)

end.add(name)

# 반복문 : 큐에 사람이 있을 때까지

while queue:

# 큐에서 한 사람씩 꺼내서

person = queue.pop(0)

# 꺼낸 이름 출력

print(person)

# 반복문 - 꺼낸 이름을 키 값으로 해서 아직 큐에 추가된 적이 없는 사람을

for p in g[person]:

# 조건 존재하지 않으면

# 큐에 추가하고 집합에도 추가

if p not in end:

queue.append(p)

end.add(p)

if __name__ == "__main__":

all_friends(frend_info, "Summer")

친밀도 : A와 B가 친구, B와 C가 친구일 때, A를 기준으로 B의 친밀도는 1, B와 C의 친밀도는 1 이므로, A와 C의 친밀도는 2가됨.