dukongmon

[그래프 용어]노드(Node) = 정점 : 그래프에서 동그라미에 해당되는 부분간선(Edge) = 거리(가중치) : 그래프에서 선에 해당되는 부분오른쪽 예시에서는 4개의 노드와 5개의 엣지로 구성됨 1) Union-Find 알고리즘 (합집합 찾기)대표적인 그래프 알고리즘'합집합 찾기' 또는 '서로소 집합(Disjoint-Set) 알고리즘'이라고 불림여러개의 노드가 존재할 때, 2개의 노드를 선택해서 이 두 노드가 현재 서로 같은 그래프에 속하는지 판별하는 알고리즘 위와 같이 아직 연결되지 않은 8개의 노드가 있다고 하자현재는 각 노드가 자기 자신만을 원소로 갖기 때문에 8개의 집합이 생김이를 테이블로 만들면 아래와 같이 만들 수 있음 (= 모든 값이 자기 자신을 가리키도록 테이블 생성)테이블 첫 행은 각 ..

그래프 탐색 대표 알고리즘 DFS / BFS탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정코테에서 매우 자주 등장하는 유형Queue입구와 출구가 모두 뚫려있는 터널과 같은 형태FIFO(First In First Out) 구조 : 먼저 들어온 데이터가 먼저 나가는 선입선출 형식의 자료구조컨베이어 벨트처럼 들어온대로 나가는 구조!EX ) 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()⇒ 5 2 3 7 1 4 List 자료형을 이용해 기능적으로는 큐를 구현할 수 있음But, List는 시간 복잡도가 더 높아서 비효율적으로 동작할 수 있음만약 pop()으로 원소를 꺼내면 그 후에 나머지 원소들의 위치를 조정해줘야 하기 때문에 O..

그래프 탐색 대표 알고리즘 DFS / BFS탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정코테에서 매우 자주 등장하는 유형Stack리스트의 한쪽 끝에서 수행되는 선형 리스트의 한가지 형태입구와 출구가 동일한 형태LIFO(Last In First Out) 구조 : 선입후출 형태로 스택에 마지막으로 입력된 자료가 제일 먼저 삭제되는 구조깊은 상자라고 생각했을 때 차곡차곡 넣는데, 마지막에 넣은걸 먼저 꺼낼 수 있는 구조!EX ) 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()⇒ 5 2 3 7 1 4 stack = []# 삽입(5)-삽입(2)-삽입(3)-삽입(7)-삭제()-삽입(1)-삽입(4)-삭제()stack.append(5..

자기 자신을 다시 호출하는 함수를 의미DFS, BFS에서 많이 사용함무한히 재귀 함수를 반복하면 어느정도 출력하다 최대 재귀 깊이 초과 메시지 출력됨RecursionError: maximum recursion depth exceeded while calling a Python object더보기추가 설명실제로 컴퓨터 시스템 상에서 함수가 재귀적으로 호출되면 컴퓨터 시스템의 스택 프레임에 함수가 반복적으로 쌓여서 가장 마지막에 호출된 함수가 처리가 된 이후에 그 함수를 불렀던 함수까지 처리되는 방식임 실제로는 스택과 같은 형태로 동작한다고 이해할 수 있음즉, 일종의 스택 자료 구조 안에 함수에 대한 정보가 차례대로 담겨서 컴퓨터 메모리에 올라가게 된다고 이해할 수 있음당연히 컴퓨터의 메모리는 한정된 크기만큼..