하루이의 개발 노트

BFS(Breadth-First Search, 너비 우선 탐색)는 그래프 또는 트리를 탐색하는 알고리즘 중 하나로, 가까운 노드부터 탐색을 진행하는 방식이다.BFS의 기본 개념탐색 순서: BFS는 시작 정점에서부터 시작하여 인접한 모든 정점을 먼저 탐색한 후, 그다음으로 가까운 정점들로 확장해 나가는 방식이다. 이 과정을 반복하며 그래프를 탐색해 나간다.큐(Queue)를 이용한 구현: BFS는 큐(Queue) 자료구조를 사용해 구현한다. 큐는 FIFO(First In, First Out) 원칙에 따라 먼저 들어온 요소가 먼저 나가는 구조다. BFS는 정점을 탐색할 때 큐에 넣고, 큐에서 꺼내면서 그 정점의 인접한 정점을 다시 큐에 넣는 과정을 반복한다.방문 여부 체크: BFS는 같은 정점을 여러 번 방문..

그래프(데이터 구조에서의 그래프)는 노드(정점)와 엣지(간선)로 이루어진 비선형 자료구조로, 다양한 문제를 해결하는 데 사용된다. 그래프는 서로 연결된 데이터 간의 관계를 표현하기에 유용하다. 이를 통해 다양한 알고리즘이 적용될 수 있으며, 특히 네트워크, 소셜 미디어 분석, 경로 탐색 등에서 자주 사용된다.1. 그래프의 기본 요소노드(Node, 정점): 데이터 포인트를 의미한다. 그래프에서는 보통 원으로 표시되며, 각 노드는 고유한 값을 가진다.엣지(Edge, 간선): 노드 간의 연결을 의미한다. 두 노드 사이의 관계를 나타내며, 방향성 여부에 따라 유향 그래프와 무향 그래프로 나뉜다.2. 그래프의 종류1. 무향 그래프(Undirected Graph)예시: 노드 A와 노드 B가 있고, 이 둘을 연결하는..

이분 탐색(Binary Search)은 정렬된 배열이나 정렬된 순서가 보장된 데이터 구조에서 특정 값을 효율적으로 찾는 알고리즘이다. 이 알고리즘은 탐색 범위를 절반으로 줄이면서 진행하므로, 시간 복잡도가 (O(\log n))으로 매우 효율적이다. 이제 이분 탐색의 핵심 개념과 주요 특징을 깊이 있게 정리해 보겠다.1. 기본 개념이분 탐색은 탐색 범위를 절반으로 계속 줄여가며 목표 값을 찾는 방식으로 동작한다. 예를 들어, 배열이 오름차순으로 정렬되어 있다고 가정했을 때, 이분 탐색은 다음과 같은 과정을 따른다:초기 설정: st (시작 인덱스)를 배열의 첫 번째 인덱스인 0으로 설정.en (끝 인덱스)를 배열의 마지막 인덱스로 설정.반복적인 비교:중간값 인덱스 mid를 계산: mid = (st + en)..

합병 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘의 대표적인 예로, 안정적인 정렬 알고리즘 중 하나이다. 합병 정렬은 데이터를 작은 단위로 분할한 후, 각 단위를 정렬하면서 합병(Merge)하여 최종적으로 정렬된 리스트를 만드는 방식으로 동작한다.합병 정렬의 기본 개념분할 정복: 합병 정렬은 주어진 리스트를 반으로 나누어 더 이상 나눌 수 없을 때까지 재귀적으로 분할한 다음, 분할된 리스트를 병합하면서 정렬한다.안정성: 합병 정렬은 안정적인 정렬 알고리즘이다. 즉, 두 개의 동등한 키를 가진 원소의 순서는 정렬 후에도 유지된다.합병 정렬의 작동 원리합병 정렬은 다음과 같은 세 단계로 구성된다:분할(Divide):주어진 리스트를 반으로 나누어 두 개의 서브 리스트로 ..

우선순위 큐(Priority Queue)는 각 요소가 우선순위를 가지며, 우선순위에 따라 요소들이 정렬되어 처리되는 자료 구조이다. 우선순위 큐는 일반적인 큐(First-In-First-Out, FIFO)와는 다르게, 먼저 들어온 요소가 아니라 우선순위가 높은 요소가 먼저 처리된다. 이러한 특성 때문에 우선순위 큐는 다양한 실세계 응용에서 중요하게 사용된다.우선순위 큐의 응용 예시응급실 환자 분류: 응급실에서는 환자가 도착한 순서가 아닌, 상태의 심각성에 따라 환자를 분류하고 치료 순서를 결정한다. 이때 우선순위 큐를 사용하여 심각한 환자를 먼저 처리할 수 있다.프로세스 스케줄링: 운영체제에서는 각 프로세스가 우선순위를 가지고 있으며, 우선순위가 높은 프로세스가 먼저 CPU를 할당받는다.네트워크 라우팅:..

힙 트리(Heap Tree)는 이진 트리의 일종으로, 최댓값 또는 최솟값을 효율적으로 관리하기 위해 설계된 자료 구조다. 힙 트리는 완전 이진 트리(Complete Binary Tree)의 형태를 가지며, 노드 간의 특정 순서 관계를 유지한다. 힙 트리는 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용된다.힙 트리의 종류힙 트리는 크게 두 가지 유형으로 나뉜다:최대 힙(Max Heap): 부모 노드가 자식 노드보다 크거나 같은 값을 가진다. 따라서 루트 노드는 트리에서 가장 큰 값을 가진다.최소 힙(Min Heap): 부모 노드가 자식 노드보다 작거나 같은 값을 가진다. 따라서 루트 노드는 트리에서 가장 작은 값을 가진다.힙 트리의 특성완전 이진 트리(Complete Binary Tre..

시간 복잡도(Time Complexity)는 알고리즘의 효율성을 측정하는 중요한 지표로, 입력 크기(input size)에 따라 알고리즘이 실행되는 시간의 증가율을 나타낸다. 시간 복잡도는 알고리즘이 처리해야 하는 작업량이 어떻게 증가하는지를 수학적으로 분석하여 표현하며, 주로 "빅 오 표기법(Big-O notation)"으로 나타낸다.1. 빅 오 표기법(Big-O Notation)빅 오 표기법은 입력 크기 ( n )에 대해 알고리즘의 실행 시간이 최악의 경우 어떻게 증가하는지를 설명한다. 이 표기법은 다음과 같은 형태로 사용된다:( O(1) ): 상수 시간 복잡도( O(log n) ): 로그 시간 복잡도( O(n) ): 선형 시간 복잡도( O(n log n) ): 로그 선형 시간 복잡도( O(n^2) ..

스택(Stack)과 큐(Queue)는 데이터 구조의 기본적인 개념으로, 데이터의 순서와 접근 방식에 중점을 둔 자료구조이다. 이 두 자료구조는 많은 알고리즘과 소프트웨어 시스템에서 중요한 역할을 한다.스택 (Stack)스택은 LIFO (Last In, First Out) 구조를 따르는 자료구조다. 즉, 마지막에 삽입된 데이터가 가장 먼저 제거된다. 스택은 물리적으로 한 쪽 끝에서만 데이터의 삽입과 삭제가 일어나는 구조를 가진다.주요 연산:push(data): 스택의 꼭대기에 데이터를 삽입한다.pop(): 스택의 꼭대기에서 데이터를 제거하고 반환한다.peek(): 스택의 꼭대기에 있는 데이터를 제거하지 않고 반환한다.isEmpty(): 스택이 비어 있는지 확인한다.size(): 스택에 있는 요소의 수를 반..

파이썬에서 리스트와 문자열의 메모리 사용을 설명하면서, 파이썬의 동적 타이핑(dynamic typing)과 객체의 동등성 판단에서 메모리 주소를 객체의 식별자로 사용하는 방식에 대해서도 추가 설명해보겠다. 1. 파이썬의 메모리 관리파이썬은 객체 지향 언어로, 모든 데이터가 객체로 표현된다. 각 객체는 메모리에 저장되며, 파이썬의 메모리 관리 시스템이 이를 관리한다. 파이썬은 가비지 컬렉션(garbage collection)을 통해 더 이상 참조되지 않는 객체를 자동으로 메모리에서 해제한다.레퍼런스 카운팅(Reference Counting): 파이썬은 기본적으로 레퍼런스 카운팅을 사용해 객체의 메모리를 관리한다. 객체가 생성될 때마다 그 객체를 참조하는 변수가 몇 개인지를 세고, 더 이상 참조되지 않으면 ..

트리(Tree)의 기본 개념과 예시트리(Tree)는 계층적인 관계를 표현하는 데이터 구조이다. 트리는 노드(Node)와 간선(Edge)으로 이루어지며, 데이터 구조나 알고리즘에서 중요한 역할을 한다.노드(Node):트리의 기본 구성 요소이다. 각 노드는 데이터를 포함하고, 다른 노드들과 연결될 수 있다. 노드의 개수는 트리의 크기를 나타낸다.루트 노드(Root Node):트리의 최상단에 위치한 노드이다. 부모 노드가 없는 유일한 노드로, 모든 노드는 루트 노드로부터 시작되는 경로를 가진다.부모 노드(Parent Node):자식 노드를 직접 연결하는 상위 노드이다. 부모 노드는 자식 노드의 상위에 위치하며, 두 노드를 연결하는 간선으로 표시된다.자식 노드(Child Node):특정 노드에 의해 연결된 하위..