전체 글
-
알고리즘, Dynamic ProgrammingData Structure & Algorithm 2024. 7. 8. 15:30
동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 이 기법은 하위 문제의 해를 재사용하여 전체 문제의 해를 구하는 데 사용됩니다. 동적 프로그래밍은 주로 최적화 문제를 해결하는 데 사용되며, 두 가지 중요한 속성을 가집니다: 최적 부분 구조(Optimal Substructure)와 중복 부분 문제(Overlapping Subproblems).동적 프로그래밍의 개념최적 부분 구조(Optimal Substructure):큰 문제의 최적 해가 그 부분 문제의 최적 해로부터 유도될 수 있는 속성을 의미합니다.예를 들어, 최단 경로 문제에서 전체 경로의 최적 해는 그 경로를 구성하는 부분 경로들의 최적 해로 구성될 수 있습..
-
알고리즘, graph, DijkstraData Structure & Algorithm 2024. 7. 3. 18:18
다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 데 사용되는 알고리즘입니다. 이 알고리즘은 가중치가 있는 그래프에서 사용되며, 가중치가 음수가 아닌 경우에만 적용할 수 있습니다.다익스트라 알고리즘의 개념시작 정점 선택: 알고리즘은 시작 정점에서 시작합니다.최단 경로 집합: 최단 경로를 확정한 정점들의 집합을 유지합니다.미확정 집합: 아직 최단 경로가 확정되지 않은 정점들의 집합을 유지합니다.거리 배열: 시작 정점에서 각 정점까지의 현재까지 발견된 최단 거리를 저장합니다. 초기에는 시작 정점의 거리를 0으로 설정하고 나머지 정점의 거리를 무한대로 설정합니다.이웃 정점 업데이트: 현재 정점에서 인접한 정점들로의 거리를 계산하고, 더 ..
-
자료구조와 알고리즘, graph, dfs, bfsData Structure & Algorithm 2024. 7. 1. 17:07
그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조로, 정점 간의 관계를 나타내는 데 사용됩니다. 그래프는 다양한 형태로 존재하며, 여러 가지 문제를 해결하는 데 유용합니다.그래프의 기본 용어정점(Vertex): 그래프의 노드를 의미합니다. 정점은 데이터를 저장할 수 있습니다.간선(Edge): 정점 간의 연결을 나타냅니다. 간선은 방향이 있을 수도(유향 그래프) 없을 수도(무향 그래프) 있습니다.인접 정점(Adjacent Vertex): 간선으로 직접 연결된 정점들입니다.경로(Path): 한 정점에서 시작하여 다른 정점으로 가는 일련의 간선들입니다.가중치(Weight): 간선에 부여된 값으로, 두 정점 간의 비용이나 거리를 나타냅니다. 가중치가 있는 그래프를 가중치 그래프(..
-
자료구조와 알고리즘, Hash TableData Structure & Algorithm 2024. 6. 30. 16:20
해시 테이블(Hash Table)은 키(Key)와 값(Value)의 쌍을 저장하고, 빠르게 데이터를 검색, 삽입, 삭제할 수 있는 자료 구조입니다. 해시 테이블은 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이를 인덱스로 사용해 배열에 값을 저장합니다.해시 테이블의 특징빠른 검색, 삽입, 삭제: 평균적으로 O(1)의 시간 복잡도로 검색, 삽입, 삭제 작업을 수행할 수 있습니다.해시 함수(Hash Function): 키를 입력받아 고정된 크기의 해시 값(주로 정수)을 반환하는 함수입니다. 좋은 해시 함수는 키를 고르게 분포시키고 충돌을 최소화합니다.충돌(Collision): 서로 다른 키가 동일한 해시 값을 갖는 상황을 충돌이라고 합니다. 충돌을 해결하는 방법으로 체이닝(Chaining)과 개방 주소..
-
리액트 디자인 패턴 - Controlled Pattern과 UnControlled PatternReact.js & Next.js 2024. 6. 30. 13:39
목차Controlled PatternUnControlled PatternControlled PatternReact의 Controlled 패턴은 폼 요소의 상태를 React 컴포넌트의 state로 관리하는 방식입니다. 이 패턴을 사용하면 React가 폼의 데이터를 완전히 제어할 수 있게 됩니다. Controlled 패턴의 주요 특징:상태 관리:폼 요소의 값을 React의 state로 관리합니다.사용자 입력에 따라 state를 업데이트합니다.값 설정:폼 요소의 value 속성을 state 값으로 설정합니다.이벤트 핸들링:onChange 이벤트를 통해 사용자 입력을 감지하고 state를 업데이트합니다.예시 코드:import React, { useState } from 'react';function Contro..
-
자료구조와 알고리즘, Tree, Priority QueueData Structure & Algorithm 2024. 6. 28. 18:21
우선순위 큐(Priority Queue)는 각 요소가 우선순위를 가지는 데이터 구조로, 일반적인 큐와 달리 요소들이 우선순위에 따라 제거됩니다. 우선순위 큐는 큐의 일종이지만, 요소를 삽입할 때 그 우선순위에 따라 적절한 위치에 배치하고, 제거할 때는 가장 높은(또는 낮은) 우선순위를 가진 요소를 먼저 제거합니다.우선순위 큐의 특징우선순위에 따른 요소 관리: 각 요소는 우선순위를 가지고 있으며, 큐의 요소는 우선순위에 따라 정렬됩니다.삽입 및 제거: 삽입 연산과 제거 연산은 모두 우선순위를 고려하여 수행됩니다.응용 분야: 작업 스케줄링, 네트워크 트래픽 관리, 시뮬레이션 시스템 등에서 자주 사용됩니다.구현 방법우선순위 큐는 다양한 방법으로 구현할 수 있지만, 가장 효율적인 방법은 힙(heap) 자료구조를..
-
자료구조와 알고리즘, Tree, Binary HeapData Structure & Algorithm 2024. 6. 28. 18:20
이진 힙(Binary Heap)은 완전 이진 트리(Complete Binary Tree)의 일종으로, 힙 속성을 만족하는 자료 구조입니다. 힙 속성은 다음과 같은 두 가지 형태로 구분됩니다:최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은 구조.최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 구조.이진 힙의 특징완전 이진 트리: 이진 힙은 항상 완전 이진 트리입니다. 즉, 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 경우 왼쪽부터 차례대로 노드가 채워져 있습니다.힙 속성: 최대 힙에서는 부모 노드의 값이 자식 노드의 값보다 크거나 같고, 최소 힙에서는 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.이진 힙의 구현이진 힙은 주로 배열을 ..
-
알고리즘, Tree, DFSData Structure & Algorithm 2024. 6. 27. 16:31
깊이 우선 탐색(Depth-First Search, DFS)은 그래프 또는 트리의 노드를 탐색하는 방법 중 하나로, 가능한 한 깊이 있는 노드를 우선으로 탐색합니다. DFS는 스택(stack) 자료 구조를 사용하여 구현할 수 있으며, 재귀적으로도 쉽게 구현할 수 있습니다.DFS의 특징깊이 우선 탐색: 가능한 한 깊이 있는 노드를 먼저 탐색하고, 더 이상 깊이 갈 수 없을 때 다음 인접한 노드로 이동합니다.스택 사용: DFS는 LIFO(Last In, First Out) 특성을 가진 스택을 사용하여 다음에 탐색할 노드를 관리합니다. 재귀적 구현에서는 함수 호출 스택을 사용합니다.경로 탐색: 그래프나 트리에서 경로를 탐색할 때 유용하며, 모든 경로를 탐색하는 문제에 적합합니다.DFS의 구현 (자바스크립트 예..