📂 자료구조

배열(Array) VS 배열 리스트(ArrayList) VS 연결 리스트(LinkedList)

📙 1. 배열 📌 1. 개념 및 특징 배열(Array)이란 같은 타입의 여러 변수를 하나의 묶음으로 다루는 것을 말한다. 배열을 구성하는 각각의 값을 배열 요소(Element), 배열에서의 위치를 가리키는 숫자를 인덱스(Index)라고 한다. 배열은 참조 객체이므로 배열을 가리키는 참조 변수는 스택 영영에 할당되며, 이 참조 변수가 가리키고 있는 주소값은 실제 힙 영역에 생성되는 배열의 주소값이다. 배열의 크기는 고정적이다. 메모리 공간이 연속적으로 구성된다. 📌 2. 장점 인덱스를 활용할 수 있기 때문에, 특정 위치에 있는 원소에 대한 접근의 시간복잡도가 O(1)이다. 인덱스를 활용할 수 있기 때문에, 특정 위치에 있는 원소에 대한 수정의 시간복잡도가 O(1)이다. 📌 3. 단점 크기가 고정적이기 때문..

배열(Array)

📙 1. 배열이란? 배열(Array)이란 같은 타입의 여러 변수를 하나의 묶음으로 다루는 것을 말한다. 배열을 구성하는 각각의 값을 배열 요소(Element)라고 하며, 배열에서의 위치를 가리키는 숫자를 인덱스(Index)라고 한다. 📙 2. 배열 선언 & 생성 & 초기화 📌 1. 배열 선언 배열을 선언하는 방법은 원하는 타입의 변수를 선언하고 변수 또는 타입에 배열임을 의미하는 대괄호를 붙이면 된다. public static void main(String[] args) { int[] numbers; String[] names; } 📌 2. 배열 생성 배열을 선언한 다음에는 배열을 생성해야 한다. 배열을 선언하는 것은 단지 생성된 배열을 다루기 위한 참조변수를 위한 공간이 만들어질 뿐이고, 배열을 생성해..

세그먼트 트리(Segment Tree)

1. 개념 🛫 세그먼트 트리(Segment Tree)란 여러 개의 데이터가 존재할 때 특정 구간의 합을 구하는 데 사용하는 자료구조이다. 트리 종류 중 하나로 이진트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다는 장점이 있다. O(log N) 2. 동작방식 🚁 세그먼트 트리를 이용하기 위해서는 우선 '구간 합 트리'를 생성해야 한다. 그리고 '구간 합을 구하는 함수'와 '원소를 수정하는 함수'를 이용하여 구간 합을 구하고 특정 원소를 수정할 수 있다. '1 9 3 8 4 5 5 9 10 3 4 5'라는 12개의 원소를 가진 배열이 주어졌을 때 세그먼트 트리를 이용하여 구간 합을 구해보자. 1. 구간 합 트리 생성하기 '구간'은 원래 데이터 범위를 반씩 분할하는 것으로 설정한다. 최상단 노드..

카운팅 정렬 (Counting Sort)

1. 개념 👑 '계수 정렬'이라고도 불리는 '카운팅 정렬(Counting Sort)'은 각 원소들이 몇 개씩 있는지 나타내는 count배열을 활용하는 정렬 알고리즘이다. 각 원소의 값이 count 배열의 인덱스가 되므로 '정수나 정수로 표현할 수 있는 자료'에 대해서만 적용 가능하다. 2. 동작방식 🎓 동작 방식은 다음과 같다. 원소의 최댓값을 포함할 수 있는 배열 설정 각각의 원소가 몇 번 등장하는지 카운팅 count 배열의 인덱스 = 원소 값 count 배열의 값 = 등장 횟수 count 배열을 누적합으로 만들어주기 정렬되지 않은 배열(초기값)의 뒤에서부터 돌면서, 원소의 값과 동일한 인덱스가 가리키는 곳에 원소 배치해 주기 '0 2 1 1 4 4 4 3 5'가 주어졌을 때 동작방식을 아래의 그림을 ..

퀵 정렬 (Quick Sort)

1. 정의 👨‍🚀 퀵 정렬(Quick Sort)은 분할 정복 방법을 이용하는 정렬 알고리즘이다. 퀵 정렬은 피벗(Pivot)을 기준으로 분할과 정복이 이루어지게 된다. 퀵 정렬은 '피벗을 선택하는 방식'과 '재귀 또는 비재귀 방식'의 선택에 따라 다양한 구현 방법이 존재한다. 이번 글에서는 '왼쪽 피벗을 선택하는 방식'과 '재귀 방식'을 통한 퀵 정렬을 알아보도록 하자. 2. 동작 방식 🦸‍♂️ 기본적인 동작 방식은 아래와 같다. 배열에서 임의의 원소인 pivot을 선택한다. (해당 글에서는 배열에서 제일 왼쪽 원소를 pivot으로 선택한다.) pivot을 기준으로 pivot보다 작은 원소는 왼쪽으로, pivot보다 큰 원소는 오른쪽에 오도록 배열을 배치한다. pivot을 기준으로 나누어진 왼쪽 배열과 ..

힙 정렬 (Heap Sort)

1. 정의 🏄‍♂️ 힙정렬이란 자료구조 힙(Heap)을 기반으로 하는 정렬 방식이다. 오름차순 정렬일 경우 최대힙을 이용하고 내림차순 정렬일 경우 최소힙을 이용한다. 간단하게 설명하자면 힙 정렬은 루트노드를 제거하고 제거된 루트 노드를 배열의 뒷부분부터 채워 넣으면서 정렬이 이루어지는 것이다. 2. 동작 방식 🚣‍♂️ 최대힙을 이용하여 오름차순으로 정렬하는 경우를 생각해 보자. 가장 쉽게 생각할 수 있는 동작방식은 아래와 같다. 정렬해야 하는 원소들을 하나씩 힙에 넣어준다. 삭제를 하면서 루트 노드를 가져오고 그것을 배열의 뒷부분부터 채운다. 이렇게 한다면 기존 배열로부터 힙을 구성하는 배열 하나를 추가적으로 만들고(1번 과정), 뒷부분부터 정렬된 원소들을 넣을 배열을 하나 더 만들어야 한다.(2번 과정..

[자료구조] 힙(Heap)

1. 정의 🐳 힙(Heap)이란 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다. 힙의 특징 완전 이진트리의 일종이다. 반정렬 상태이다. 최대힙(Max Heap) 또는 최소힙(Min Heap)에 따라서 루트 노드가 항상 가장 큰 값이거나 가장 작은 값을 유지하기 때문이다. 중복된 값을 허용한다. 힙의 종류 최대 힙 (Max Heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 형식 최소 힙 (Min Heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리 형식 2. 동작 방식 🐟 인덱스 0 1 2 3 4 5 6 7 8 값 - 9 7 6 4 5 1 3 8 Heap은 배열을 통해 쉽게 구현이 가능하다. 그 이유는 힙이 완전 이진트리이..

위상 정렬(Topology Sort)

1. 정의 🧊 위상 정렬(Topology Sort)이란 순서가 정해져 있는 작업을 차례대로 수행할 때 그 순서를 결정해 주는 알고리즘이다. 교육과정의 선수과목이 위상 정렬을 설명하는 가장 적절한 예시이다. 컴퓨터 공학을 전공하고 있는 학생은 다음 전공과목(ex. 알고리즘)을 듣기 위해서는 선수 과목(ex. 자료구조)을 필수적으로 들어야 한다. 기초컴퓨터프로그래밍 → 자료구조 → 알고리즘 자료구조 → 논리회로및설계 → 논리회로실험 알고리즘 → 논리회로및설계 → 논리회로실험 또한, 위상정렬은 위와 같이 여러 개의 경로가 존재할 수 있다. 마지막 특징으로는 위상 정렬은 비순환 유향 그래프(DAG - Directed Acyclic Graph)에만 적용이 가능하다. 즉, 사이클이 발생하지 않는 방향 그래프여야 한..

병합 정렬(Merge Sort)

합병정렬이라고도 불리는 병합정렬에 대해서 알아보자. 1. 정의 🎃 병합정렬이란 정렬해야 하는 배열을 가장 작을 때까지 나누고, 그 시점부터 인접한 부분배열끼리 비교하며 정렬하는 알고리즘이다. 해당 알고리즘은 분할 정복(Divide and Conquer) 알고리즘을 기반으로 한다. (분할 정복(Divide and Conquer)이란 문제를 분할하고, 분할한 문제를 정복하여 합치는 것이다.) 2. 동작 방식 🎪 주어진 배열을 절반으로 분할하여 부분배열로 나눈다. - 분할(Divide) 해당 부분배열의 길이가 1이 될 때까지 계속해서 1번 과정을 반복한다. 인접한 부분 배열끼리 합친다. - 정복(Conquer) 위의 그림을 통해 알 수 있듯이 크기가 1이 될 때까지 분할이 진행된다. 그리고 인접한 배열끼리 합..

삽입 정렬(Insertion Sort)

1. 정의 🧵 삽입 정렬은 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 카드 예시를 살펴보면 쉽게 이해할 수 있을 것이다. '4, 2, 3, 1, 5'라는 숫자 적힌 5장의 카드가 순서대로 있다고 하자. 앞에서부터 순서대로 카드를 뽑으면서 손에 쥔다고 생각하자. 뽑힌 카드는 이미 손에 쥐어진 카드들 사이에 위치를 찾아들어간다. 이미 손에 쥐어져 있는 카드들 뽑은 카드 자신의 위치를 찾아들어간 모습 4 4 4 2 2 4 2 4 3 2 3 4 2 3 4 1 1 2 3 4 1 2 3 4 5 1 2 3 4 5 1번 숫자가 적힌 카드가 자신의 위치를 찾아가는 것을 다시 한번 살펴보자. 1번 카드는 4번과 비교하고, 3번과 비교하고, 2번과 ..

선택 정렬(Selection Sort)

선택 정렬은 여러 가지 면에서 앞에서 살펴본 버블 정렬과 상당히 비슷하다. 두 가지 정렬 방법을 구분하는 게 어렵지는 않으니, 선택 정렬을 공부하는 김에 버블 정렬도 같이 공부하는 것을 추천한다. 1. 정의 🎿 선택 정렬은 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 2. 동작 방식 🧦 N개의 원소가 있다고 하자. 우선, 배열에서 최솟값을 찾는다. 그리고 첫 번째 원소와 배열에서 찾은 최솟값의 원소를 바꿔준다. 이것이 1회전 수행한 것이다. 이렇게 되면 배열의 첫 번째에 위치한 원소가 가장 작은 값을 가지게 된다. 2회전을 수행할 때는 첫 번째 원소를 제외한 나머지 배열들 중에서 최솟값을 찾는다. 그리고 해당 원소와 배열의 두 번째 원소를 바꿔준다. 이와 같은 방식으..

버블 정렬(Bubble Sort)

거품 정렬이라고도 불리는 버블 정렬에 대해서 알아보자. 1. 정의 👟 버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 2. 동작 방식 👞 N개의 원소가 있다고 하자. 첫 번째 원소와 두 번째 원소를 비교하여 만약 첫 번째 원소가 더 크다면 둘의 자리를 바꿔준다. 그리고 두 번째 원소와 세 번째 원소를 비교하여 만약 두 번째 원소가 더 크다면 둘의 자리를 바꿔준다. 이러한 동작을 (마지막 - 1) 번째의 원소와 마지막 원소를 비교할 때까지 수행한다. 이것이 1회전 수행한 것이다. 이렇게 되면 마지막에 위치한 원소가 가장 큰 원소가 된다. 2회전을 수행할 때 마지막 원소를 제외한 나머지들을 정렬해 준다. (N - 1) 회전까지 수행하면 정렬이 마무리된다. 위의 방식은 오름차순으로 정렬을 ..