서론자료구조를 공부하다 보면 단방향 연결 리스트 다음으로 마주치게 되는 것이 바로 양방향 연결 리스트다. 단방향 연결 리스트가 한 방향으로만 이동할 수 있다면, 양방향 연결 리스트는 앞뒤로 자유롭게 이동할 수 있다는 점에서 더 유연한 구조를 가지고 있다. 양방향 연결 리스트란?양방향 연결 리스트(Doubly Linked List)는 각 노드가 데이터와 함께 이전 노드(prev)와 다음 노드(next)를 가리키는 두 개의 포인터를 가진 자료구조다. 이러한 구조 덕분에 리스트를 양방향으로 순회할 수 있으며, 특정 위치에서의 삽입과 삭제 연산이 단방향 연결 리스트보다 효율적이다.시간 복잡도삽입(Insertion): O(1)삭제(Removal): O(1)탐색(Searching): O(N) (정확히는 O(N/2..
서론자료 구조를 공부하다 보면 배열(Array)만으로는 충분하지 않은 순간이 온다. 특히 데이터의 삽입과 삭제가 빈번하게 일어나는 상황에서 배열의 성능은 급격히 떨어진다. 이럴 때 등장하는 것이 바로 연결 리스트(Linked List)다.이 글에서는 단방향 연결 리스트의 개념부터 구현, 시간 복잡도 분석, 그리고 배열 및 양방향 연결 리스트와의 비교까지 모든 것을 다뤄본다.단방향 연결 리스트란?단방향 연결 리스트는 노드(Node)들이 하나의 체인처럼 연결된 자료 구조다. 각 노드는 두 가지 정보를 담고 있다:val: 노드에 저장된 실제 데이터next: 다음 노드를 가리키는 참조(포인터)배열과의 가장 큰 차이점은 인덱스가 없다는 것이다. 연결 리스트에서는 첫 번째 노드(head)에서 시작해서 next 포인..
[알고리즘] 합병 정렬, 퀵 정렬, 기수 정렬
이번 글에서는 합병 정렬(Merge Sort), 퀵 정렬(Quick Sort), 기수 정렬(Radix Sort) 세 가지를 다뤄본다.앞에서 배운 버블, 선택, 삽입 정렬보다 훨씬 빠르고, 큰 데이터셋에서도 성능이 안정적인 알고리즘들이다. 1. 합병 정렬 (Merge Sort)합병 정렬은 분할 정복(Divide and Conquer) 방식으로 동작한다.배열을 계속 반으로 나누다가 길이가 1 이하인 배열이 되면, 다시 합치면서 정렬을 완성한다.핵심 아이디어는 정렬된 두 배열을 합치는 과정이다.예를 들어 [8, 3, 5, 4, 7, 6, 1, 2]가 있다면:반으로 쪼갠다 → [8,3,5,4]``[7,6,1,2]또 쪼갠다 → [8,3] [5,4] [7,6] [1,2]끝까지 쪼개면 [8] [3] [5] [4] [..
프로그래밍에서 정렬 알고리즘은 가장 기초적이면서도 중요한 개념이다. 정렬 알고리즘은 컬렉션(collection)의 항목을 재배열하는 과정이다. 최신순, 인기순, 제목순으로 글을 재배열하는 모든 서비스들에서 우리는 정렬을 만나왔다. 버블 정렬, 선택 정렬, 삽입 정렬 세 가지를 한 번에 비교하고, 각 알고리즘의 특징과 장단점을 살펴보자.버블 정렬(Bubble Sort)버블 정렬은 인접한 두 원소를 비교하고 필요 시 교환(swap)하며 큰 값이 뒤로 이동하는 방식으로 배열을 정렬한다.말 그대로 큰 값이 거품처럼 위로 떠오른다는 느낌에서 이름이 유래했다.동작 방식배열의 첫 원소부터 인접한 두 값을 비교.앞의 값이 뒤보다 크면 교환.배열 끝까지 반복하면 가장 큰 값이 맨 뒤로 이동.다음 패스에서는 마지막 원소는..
1. 개념삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어 진행하는 알고리즘이다.하나의 원소를 꺼내 이미 정렬된 부분에서 적절한 위치를 찾아 삽입하면서 전체 배열을 점차 정렬해 나간다.버블 정렬이나 선택 정렬과 비슷한 기초 정렬 알고리즘이지만, 특정 상황에서는 더 효율적으로 작동한다.2. 동작 방식동작 예시정렬할 배열: [5, 3, 4, 1, 2]첫 번째 원소는 이미 정렬된 부분으로 간주한다[5] | [3, 4, 1, 2] (정렬된 부분 | 정렬되지 않은 부분)두 번째 원소(3) → 정렬된 부분과 비교5보다 작으므로 앞으로 이동한다.[3, 5] | [4, 1, 2]세 번째 원소(4) → 정렬된 부분과 비교5보다 작고, 3보다는 크므로 3과 5 사이에 삽입한다.[3, 4, 5] | [1, ..
1. 개요나이브 문자열 검색(Naive String Search)은 가장 기본적인 문자열 탐색 기법이다. 이 알고리즘은 긴 문자열 내에서 특정한 짧은 문자열(패턴)이 몇 번 등장하는지를 확인하는 데 사용된다. 2. 알고리즘 개념나이브 문자열 검색은 다음과 같은 방식으로 동작한다.긴 문자열의 각 문자부터 시작하여,짧은 문자열의 길이만큼 잘라서 비교하며,모든 문자가 일치하면 해당 위치를 일치로 간주하고 카운트를 증가시킨다.3. 동작 절차 count를 0으로 초기화한다.긴 문자열의 0번째 문자부터 (긴 문자열 길이 - 짧은 문자열 길이) 위치까지 반복한다.매 반복마다:짧은 문자열의 문자를 하나씩 반복하며,긴 문자열의 i + j 번째 문자와 짧은 문자열의 j 번째 문자를 비교한다.둘 중 하나라도 다르면 비교를 ..