본문 바로가기

공부 키워드/알고리즘 및 데이터 구조

그래프(Graph) 그래프(Graph) 그래프는 데이터 구조 의 한 형태로, 여러 개의 정점(node)과 이 정점들을 연결하는 간선(edge)으로 구성된다. 그래프는 데이터 간의 관계를 모델링하는데 사용될 수 있으며, 컴퓨터 과학, 네트워크 시스템, 사회학 등 다양한 분야에서 응용된다. 그래프의 유형 무방향 그래프(Undirected Graph) 무방향 그래프는 정점들이 방향없 없는 간선으로 연결된 그래프이다. 즉, 두 정점은 서로 연결되어 있고, 어느 쪽에서 출발해도 다른 쪽에 도달할 수 있다. 양방향이기 때문에 A와 B를 연결하는 간선이 있다면, A->B, B->A 둘 다 가능하다. 특징 대칭성 : 무방향 그래프의 간선은 대칭적이라 어느쪽에서든 이동할 수 있다. 루프 : 무방향 그래프에서는 한 정점에서 출발해 다른 정점.. 더보기
깊이 우선 탐색(DFS, depth-first search), 너비 우선 탐색(BFS, Breadth-first search) 깊이 우선 탐색(DFS, depth-first search) 깊이 우선 탐색(DFS)은 그래프의 모든 노드를 탐색하는데 사용되는 알고리즘 중 하나이다. 루트 노드에서 시작해 한 방향으로(주로 왼쪽부터) 들어갈 수 있는한 끝까지 탐색하여 더 이상 들어갈 수 없는 경우, 가장 최근의 분기점으로 돌아가 다른 방향의 노드를 탐색하는 방식으로 진행된다. DFS의 구현 // 그래프를 인접 리스트 형태로 표현 const graph = { A: ['B', 'C'], B: ['A', 'D', 'E'], C: ['A', 'F'], D: ['B'], E: ['B', 'F'], F: ['C', 'E'] }; // DFS 함수 정의 function dfs(graph, startNode) { let visited = []; //.. 더보기
해시 테이블(Hash Table) 해시 테이블(Hash Table) 해시 테이블은 키(Key)와 값(Value)을 매핑하여 데이터를 저장하는 데이터 구조 중 하나이며, 이 방식은 빠른 데이터 검색이 가능하다. 하지만, 해시 테이블은 해시 함수를 사용해 저장 위치를 결정하는데, 이 과정에서 충돌(Collision)이 발생할 수 있다. 충돌(Collision)은 두 개의 키가 동일한 해시 값을 가지게 되어, 같은 위치에 저장되려고 할 때 발생하는 상황을 의미하는데 이를 해결하기 위한 몇 가지 방법이 있다. 체이닝(Chaning) 충돌을 해결하는 가장 일반적인 방법 중 하나로, 각 해시 테이블의 항목을 연결 리스트로 구성하여 충돌이 발생했을 때, 리스트에 노드를 추가하는 방식이다. 이렇게 하면 동일한 해시 값에 대해 여러 키를 저장할 수 있게.. 더보기
Deep Copy vs Shallow Copy Deep Copy vs Shallow Copy Deep Copy(깊은 복사)와 Shallow Copy(얕은 복사)는 객체를 복사할 때 사용되는 두 가지 방식이며, 객체 내의 데이터를 어떻게 처리하는지에 따라 구분된다. Deep Copy(깊은 복사) 깊은 복사는 객체의 모든 레벨을 재귀적으로 복사한다. 객체 내부의 다른 객체나 배열 등도 새롭게 복사되어, 복사된 객체는 원본 객체와 완전히 독립적인 복제본이 된다. 이 방식을 사용하면 복사된 객체를 수정해도 원본 객체에는 영향을 주지 않고, 반대의 경우도 마찬가지이다. 깊은 복사는 복사 과정이 상대적으로 느리고, 메모리 사용량이 더 많다는 단점이 있지만, 복사된 객체가 원본 객체와 완전히 독립적이 되므로, 두 객체 간의 상호 작용을 걱정하지 않아도 된다. 예.. 더보기
스택(Stack), 큐(Queue) 스택(Stack) 스택은 프로그래밍에서 사용되는 기본적이면서도 중요한 자료구조 중 하나이며, 선형 자료구조이다. 데이터를 임시 저장하고 관리하는데 사용되며, 특히 데이터의 입력과 출력순서가 후입선출(LIFO, Last In First Out) 방식으로 이루어진다. 스택의 특징 스택은 한쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형 자료 구조이다. 데이터의 추가(push)와 삭제(pop)가 같은 쪽에서 이루어지며, 가장 마지막에 들어온 데이터가 가장 먼저 나가는 구조를 가진다. 스택은 웹 브라우저의 뒤로 가기 기능, 함수 호출 시의 콜 스택 관리, 괄호 검사 , DFS(깊이 우선 탐색)등 다양한 애플리케이션에서 활용된다. 스택의 기본 연산 push() : 스택에 데이터를 추가하는 작업. 스택의 가장 위에 .. 더보기
연결 리스트(Linked List) 연결 리스트 (Linked List) 연결 리스트는 노드의 집합으로, 각 노드가 다음 노드를 가리키는 포인터를 통해 순차적으로 연결된 구조이다. 연결 리스트는 동적 메모리 할당을 사용해 구현되며, 배열과 달리 런타임에 크기가 변경될 수 있다. 연결 리스트의 각 요소는 데이터 필드와 하나 혹은 그 이상의 다음(next) 링크 필드로 구성된다. 즉, 비엔나 소세지 마냥 줄줄이 이어져 있는 느낌이다. 연결 리스트의 종류 단일 연결 리스트(Singly Linked List) 각 노드가 다음 노드만을 가리키는 포인터를 가지며 리스트의 첫 번째 노드는 헤드(Head)라고 한다. 리스트의 마지막 노드는 꼬리(Tail)이며 다음 노드가 없음을 나타내는 NULL 값을 가진다. 작동 원리 삽입(Insertion) 새로운 .. 더보기
시간 복잡도(Big-oh Notaion) 시간 복잡도(Time Complexity) 알고리즘을 실행하는데 필요한 시간이 입력의 크기에 따라 어떻게 변화하는지를 나타내는 척도이다. 이는 알고리즘의 효율성을 평가하는 중요한 기준 중 하나로, 알고리즘의 실행 시간이 입력 크기에 따라 얼마나 증가하는지를 분석함으로써, 알고리즘을 이해하고 최적화하는데 도움이 된다. 시간 복잡도의 표현 시간 복잡도는 주로 빅오 표기법(Big O notation)을 사용하여 표현된다. 빅오 표기법은 최악의 경우 시간 복잡도를 나타내는데 사용되며, 알고리즘의 상한을 설명해준다. 예를 들어 O(n)은 알고리즘의 실행 시간이 입력 크기 n에 선형적으로 비례한다는 것을 의미한다. 주요 시간 복잡도 시간 복잡도 설명 예시 O(1) 상수 시간 입력 크기와 상관없이 실행 시간이 일정하.. 더보기
정렬 알고리즘 정렬 알고리즘 정렬 알고리즘은 데이터를 특정한 기준에 따라 순서대로 배열하는 방법이다. 이러한 알고리즘은 데이터 처리의 효율성을 높이고, 정보를 쉽게 찾거나 이해할 수 있도록 도와준다. 정렬 알고리즘 종류 버블 정렬(Bubble Sort) 버블 정렬은 정렬과정에서 데이터의 원소들이 거품이 물 위로 올라오는 것처럼, 각 원소들이 서로의 위치를 바꾸며 최종적인 위치를 찾아가는 과정을 거친다. 버블 정렬의 기본 원리 인접한 두 원소를 비교하여 크기 순서대로 정렬하는 알고리즘이며, 인접한 원소의 순서가 바뀌어야 한다면 두 원소의 위치를 교환한다. 첫 번째 원소부터 시작하여 바로 다음 원소와 비교하고, 조건에 맞다면 위치를 교환하여 배열의 끝까지 반복한다. 각 단계마다 가장 큰 원소가 배열의 끝으로 이동하며, 이.. 더보기

티스토리툴바