nyambu 님의 블로그

1. 동적 프로그래밍(Dynamic Programming)이란? 동적 프로그래밍(DP, Dynamic Programming)은 복잡한 문제를 작은 하위 문제로 나누어 해결한 결과를 저장하여 동일한 계산을 반복하지 않도록 최적화하는 알고리즘 기법이다. 특히, 부분 문제의 결과를 재사용할 수 있는 경우(Overlapping Subproblems)와 최적 부분 구조(Optimal Substructure)를 만족하는 경우에 효과적이다. 📌 핵심 개념:동일한 연산을 반복하지 않도록 결과를 저장(Memoization)작은 문제를 해결한 후 이를 조합하여 큰 문제를 해결하는 방식재귀(Top-Down) 방식과 반복(Bottom-Up) 방식이 존재2. 동적 프로그래밍이 필요한 이유 일반적인 완전 탐색(Brute For..

1. 그래프(Graph) 자료구조란? 그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 구성된 자료구조로, 객체들 간의 관계를 표현하는 데 사용된다. 정점(Vertex, 노드): 데이터를 저장하는 개체 (예: 도시, 사람, 컴퓨터)간선(Edge): 정점 간의 연결 관계를 나타내는 요소 (예: 도로, 네트워크 링크)그래프는 소셜 네트워크 분석, 지도 네비게이션, 네트워크 라우팅, 인공지능(AI) 경로 탐색 등 다양한 분야에서 활용된다.2. 그래프의 종류2-1. 방향 그래프 vs 무방향 그래프무방향 그래프(Undirected Graph): 간선의 방향이 없으며, 양방향으로 이동 가능예) A—B (A에서 B로 갈 수도 있고, B에서 A로도 갈 수 있음)방향 그래프(Directed Graph, DA..

1. 해시 테이블이란? 해시 테이블(Hash Table)은 키-값(Key-Value) 구조를 활용하여 데이터를 빠르게 저장하고 검색하는 자료구조이다. 해시 함수를 이용해 데이터를 특정한 위치에 저장하고, 필요한 값을 빠르게 찾을 수 있도록 한다. 해시 테이블은 **배열(Array)과 연결 리스트(Linked List)**를 조합하여 빠른 탐색, 삽입, 삭제가 가능한 자료구조이다.1-1. 해시 테이블의 기본 원리**해시 함수(Hash Function)**를 사용하여 키(Key)를 특정 인덱스(Index)로 변환한다.변환된 인덱스에 해당 데이터를 저장한다.검색할 때도 동일한 해시 함수를 사용하여 데이터를 빠르게 찾을 수 있다.2. 해시 테이블의 동작 과정2-1. 데이터 저장 과정키(Key)를 해시 함수(Ha..

1. 탐색(Search) 알고리즘이란?탐색 알고리즘은 원하는 데이터를 찾기 위한 방법론이다. 다양한 데이터 구조에서 탐색할 수 있으며, 효율적인 탐색을 위해 알고리즘을 적절히 선택하는 것이 중요하다. 대표적인 탐색 알고리즘에는 **이진 탐색(Binary Search), 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)**가 있다.2. 이진 탐색 (Binary Search)2-1. 이진 탐색 개념이진 탐색은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘이다. 일반적인 선형 탐색(순차 탐색, O(n))보다 빠르게 동작하며, **시간 복잡도는 O(log n)**이다. 2-2. 이진 탐색 동작 원리배열의 중간 값을 확인한다.찾고자 하는 값이 중간 값보다 작으면 왼쪽 부분 배열을 탐색한다.찾고자 하는 값이 ..

1. 정렬 알고리즘이란?정렬 알고리즘은 주어진 데이터 집합을 오름차순 또는 내림차순으로 정렬하는 방법을 의미한다. 정렬 방식에 따라 성능 차이가 크며, 상황에 따라 적합한 알고리즘을 선택하는 것이 중요하다. 정렬 알고리즘의 성능은 **시간 복잡도(Time Complexity)**와 **공간 복잡도(Space Complexity)**를 기준으로 평가된다. 시간 복잡도: 데이터 개수(n)에 따른 연산 횟수 (Best / Average / Worst Case 분석)공간 복잡도: 추가적으로 필요한 메모리 사용량2. 버블 정렬 (Bubble Sort) 버블 정렬은 가장 단순한 정렬 알고리즘 중 하나로, 인접한 두 개의 데이터를 비교하여 큰 값을 뒤로 보내는 방식을 반복한다. 즉, 가장 큰 값이 거품처럼 위로 올라..