Data structure & Algorithms study (32) 썸네일형 리스트형 너비 우선 탐색 (BFS, Breadth-First Search) 너비 우선 탐색 (BFS, Breadth-First Search) 개요너비 우선 탐색(BFS)은 그래프나 트리를 탐색하는 대표적인 알고리즘 중 하나로, 탐색의 너비(Breadth)를 우선으로 진행하는 방식이다. BFS는 시작 노드에서 출발해 인접한 노드들을 먼저 탐색한 후, 그 다음으로 인접한 노드들의 이웃들을 탐색하는 방식으로 진행된다. 즉, 같은 레벨에 있는 노드들을 먼저 방문하고, 한 레벨의 모든 노드를 방문한 후 다음 레벨로 넘어가는 방식이다.BFS는 큐(Queue) 자료구조를 사용해 구현되며, 최단 경로를 찾는 문제나, 그래프의 각 노드를 너비 우선으로 방문할 때 매우 유용하다. BFS의 동작 원리시작 노드에서 탐색을 시작한다.해당 노드를 방문 처리하고, 그 노드를 큐에 넣는다.큐에서 노드를 꺼.. 깊이 우선 탐색 (DFS, Depth-First Search) 깊이 우선 탐색 (DFS, Depth-First Search) 개요깊이 우선 탐색(DFS)은 그래프 탐색 알고리즘 중 하나로, 그래프의 모든 노드를 깊이(depth)를 우선으로 탐색하는 방법이다. DFS는 재귀(Recursion)나 스택(Stack)을 사용하여 구현할 수 있으며, 그래프 또는 트리에서 특정 경로를 찾거나, 모든 노드를 방문하는 데 유용하게 사용된다.DFS는 다음과 같은 방식으로 동작한다:시작 노드에서 출발하여 한 노드를 선택하고, 그 노드에서 갈 수 있는 경로 중 하나를 선택해 탐색을 계속 진행한다.더 이상 갈 수 있는 노드가 없을 때, 다시 이전 경로로 돌아와 다른 경로를 탐색한다.방문한 노드를 다시 방문하지 않도록 하기 위해 방문 여부를 기록한다.DFS는 깊이 우선이기 때문에 가능한 .. 그래프(Graphs)- 인접 리스트(Adjacency List) 인접 리스트는 그래프를 표현하는 또 다른 방법으로, 각 노드에 연결된 이웃 노드들을 리스트나 다른 자료구조로 저장하는 방식이다. 이 방법은 간선의 수가 적은 희소 그래프(Sparse Graph)를 표현할 때 공간 효율적이다. 인접 리스트의 구조각 노드는 자신과 연결된 노드들의 리스트를 갖고 있다. 이를 위해 파이썬에서는 딕셔너리나 리스트를 활용할 수 있다.키(Key): 노드를 나타낸다.값(Value): 해당 노드와 연결된 노드들의 리스트이다. 리스트의 각 항목은 이웃 노드를 나타낸다.인접 리스트 예시다음은 4개의 노드를 가진 무방향 그래프의 예시이다. 0 -- 1 \\ / \\ 2 -- 3이 그래프의 인접 리스트 표현은 다음과 같다:{ 0: [1, 2], 1: [0, 2.. 그래프(Graphs) - 인접행렬(Adjacency Matrix) 그래프(Graphs) 개요그래프는 노드(Node)와 그 노드들을 연결하는 간선(Edge)으로 이루어진 자료구조이다. 그래프는 여러 문제를 모델링하는 데 유용하며, 특히 네트워크, 지도, 소셜 네트워크 등의 문제를 해결할 때 자주 사용된다.그래프는 방향성(Directed)이 있을 수도 있고 없을 수도 있으며, 가중치(Weighted)가 있을 수도 있고 없을 수도 있다. 이 특징에 따라 그래프의 형태가 달라진다.그래프를 표현하는 두 가지 주요 방법은 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)입니다. 이 중에서 인접 행렬에 대해 자세히 살펴보겠다. 인접 행렬 (Adjacency Matrix)인접 행렬은 그래프를 표현하는 방법 중 하나로, 2차원 배열을 사용하여 노드 .. 해시 테이블(Hash Tables) 해시 테이블(Hash Tables) 개요해시 테이블은 키(key)-값(value) 쌍을 저장하는 자료구조이다. 키를 해시 함수(hash function)를 통해 특정한 인덱스로 변환하여, 배열과 같은 자료구조에 값을 저장한다. 해시 테이블의 주요 장점은 빠른 데이터 검색, 삽입, 삭제이다. 평균적으로 O(1) 시간 복잡도를 가지기 때문에 효율적이다.하지만 해시 테이블에서 중요한 문제는 충돌(collision)이다. 충돌은 두 개 이상의 서로 다른 키가 동일한 해시 값을 갖게 되어 동일한 인덱스에 저장하려고 할 때 발생한다. 이 문제를 해결하기 위해 여러 가지 기법이 사용된다. 충돌 처리 기법충돌을 처리하기 위한 대표적인 방법으로 체이닝(Chaining)과 오픈 어드레싱(Open Addressing)이 있.. 이진 탐색 (Binary Search) 이진 탐색(Binary Search)은 효율적인 탐색 알고리즘으로, 정렬된 리스트에서 특정 값을 찾기 위해 사용된다. 이진 탐색은 리스트를 반으로 나누어 탐색 범위를 좁혀가는 방식으로 동작하며, 시간 복잡도가 O(log n)으로 매우 효율적이다.설명 및 개념이진 탐색은 다음과 같은 단계를 따른다:초기화: 리스트의 시작 인덱스와 끝 인덱스를 설정한다.중간 요소 계산: 시작 인덱스와 끝 인덱스의 중간 요소를 계산한다.비교:중간 요소가 찾고자 하는 값과 일치하면, 해당 요소의 인덱스를 반환한다.중간 요소가 찾고자 하는 값보다 크면, 끝 인덱스를 중간 인덱스의 왼쪽으로 이동시켜 리스트의 왼쪽 절반을 탐색한다.중간 요소가 찾고자 하는 값보다 작으면, 시작 인덱스를 중간 인덱스의 오른쪽으로 이동시켜 리스트의 오른쪽.. 선형 탐색 (Linear Search) 선형 탐색(Linear Search)은 가장 기본적인 탐색 알고리즘 중 하나로, 리스트나 배열에서 특정 값을 찾기 위해 처음부터 끝까지 순차적으로 비교하는 방식으로 동작한다. 이 알고리즘은 정렬되지 않은 리스트에서도 동작하며, 매우 간단한 구현이 가능하지만 효율성은 떨어질 수 있다.설명 및 개념선형 탐색은 다음과 같은 단계를 따른다:초기화: 리스트의 첫 번째 요소부터 시작한다.비교: 현재 요소와 찾고자 하는 값을 비교한다.일치 여부 확인:현재 요소가 찾고자 하는 값과 일치하면, 해당 요소의 인덱스를 반환한다.일치하지 않으면, 다음 요소로 이동한다.리스트 끝까지 반복: 리스트의 끝까지 이 과정을 반복한다.결과 반환: 리스트의 모든 요소를 검사한 후에도 찾고자 하는 값이 없으면, -1을 반환하여 값을 찾을 .. 힙 정렬 (Heap Sort) 힙 정렬(Heap Sort)은 완전 이진 트리(Complete Binary Tree) 기반의 정렬 알고리즘으로, 힙(heap) 자료 구조를 이용하여 정렬을 수행한다. 힙 정렬은 최악의 경우에도 O(n log n)의 시간 복잡도를 가지며, 안정 정렬은 아니지만 제자리 정렬(In-place Sorting)이다.알고리즘 개념힙 정렬은 다음 두 가지 단계로 이루어진다:최대 힙 구성 (Build Max Heap):주어진 배열을 최대 힙(Max Heap)으로 변환한다. 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 완전 이진 트리이다.힙에서 요소 추출 및 정렬 (Extract Elements from Heap):최대 힙에서 루트 노드(가장 큰 값)를 추출하여 배열의 끝으로 이동시키고, 힙의 크기를 줄인 후 다시.. 이전 1 2 3 4 다음
