//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 깊이 우선 탐색(DFS: Depth-First-Search) 그래프 완전 탐색 재귀함수로 구현 스택 자료구조 이용 깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색 수행 ⇒ 자식 노드부터 탐색 재귀 함수로 구현, 스택 자료구조를 이용 처음 탐색 노드의 어떤 인접 노드부터 탐색할지에 대한 순서는 상관없음 [깊이 우선 탐색의 원리] 한 번 방문한 노드를 다시 방문하면 안 된다. 노드 방문 여부를 체크할 배열이 필요하다. 그래프를 인접 리스트로 표현 DFS는 후입 선출의 특성을 가짐 → 스택 o..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 에지 리스트(edge list) 에지를 중심으로 그래프를 표현 특정 노드와 관련되어 있는 에지를 탐색하기 쉽지 않기 때문에 노드 중심 알고리즘에서 잘 사용하지 않고 벨만 포드나 크루스칼 알고리즘에서 사용 [에지 리스트로 가중치 없는 그래프 표현하기] 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현 배열의 행은 2개면 충분 노드는 여러 자료형을 사용할 수 있다. [에지 리스트로 가중치 있는 그래프 표현하기] 가중치가 있는 그래프는 행을 3개로 늘려 3번째 행에 가중치를 저장하면 된다. 2. 인접 행렬(adjacency matrix) 2차원 배열을 자료구조로 이용하여 그래프를 표현 노드 중심으로 그래프를 표현 ..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 대부분 O(n²)과 O(nlogn) 사이의 시간 복잡도 정렬 알고리즘 정의 시간복잡도 버블(bubble) 데이터의 인접 요소기리 비교하고, swap 연산을 수행하며 정렬하는 방식 O(n²) 선택(selection) 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 O(n²) 삽입(insertion) 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 O(n²) 퀵(quick) pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 O(nlogn) 병합(merge) 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 O(nlogn) 힙(hea..