원티드_언리얼RPG 2기/자료구조& 알고리즘
연결리스트 구현, 버블정렬, 병합정렬
하시무
2025. 3. 18. 00:25
리스트 개념:
연결리스트 별거없다 배열과 다르게 인덱스가 아니라 포인터로 이어져있는 자료구조다.
노드의 주소를 이용해서 동적으로 데이터를 저장하는 구조이다.
노드에는 다음노드를 가리키는 주소와 노드에 저장된 값이 들어있다.
이중연결리스트는 이전노드를 가리키는 주소값만 추가하면된다.
노드구조체에는 이전값을 가리키는 prev, 다음값을 가리키는 next, 노드가 가지는 값 value 가 들어간다.
처음노드는 보통 Head라고 하고 맨뒤 노드는 Tail이라고한다. Head는 시작노드를 가리키고 맨뒤노드는 Tail을 가리킨다.
리스트의 장점:
리스트는 삽입삭제가 뛰어난 자료구조이다.
배열과 다르게 메모리상에 연속된 자료구조는 아니지만 인덱스로 접근하기 때문에 삽입삭제가 쉽다.
구현한 리스트의 기능:
배열에서도 가능한 front, back, push_front, push_back, pop_front,pop_back도 구현
노드의 인덱스를 알아내는 at(), 인덱스의 노드를 알아내는 atNode(), 삽입삭제 insert(), erase()
리스트 내부 요소 삭제 clear() 등을 구현했다.
인덱스로 접근한다 했지만 포인터로 접근하는걸 의미한다.
stl::list랑 비슷하게 구현하려했는데 nullptr 때문에 고생했다. 이젠 그냥 맘편하게 stl 쓰고싶다 완벽히 이해했어
버블정렬 개념:
2 1 9 3 5 라는 숫자가 있다고 할때
첫번째 요소부터 5까지 비교연산을 하면서 크거나 작은값으로 원소들의 자리(값)을 바꾼다.
그다음 두번째 요소부터 반복
``` size() - 1 까지 반복하면 된다.
버블정렬은 쓰레기 정렬이다. N^2 의 시간복잡도를 가지고 순차적으로 다음 노드의 값과 비교하면서 위치를 바꾸는 정렬이다. 앞으로는 쓸일이 없을듯하다.
병합정렬 개념:
병합정렬은 분할과 정복, 쉽게 말해서 하나의 리스트를 반으로 쪼개서 정렬한다음 두 개의 리스트(혹은 구간)을 비교하면서 순차적으로 정렬된 값을 집어넣는 것이다.
구현:
병합정렬을 구현하기위해 리스트를 반으로 쪼갤 split() 과 병합할 merge()를 먼저 구현했다.
split()을 구현할때 slow, fast노드를 만들어서
시작노드부터 1칸씩 움직이는 slow , 2칸씩 움직이는 fast를 이용해서 fast가 리스트의 맨끝을 가리킬때까지 반복했다.
예를 들어 리스트에 {1, 2, 3, 4, 5} 라는 값이 들어있을때
한번 움직이면
slow-> 2 3 4 5
fast -> 3 4 5
두번 움직이면
slow->3 4 5
fast ->nullptr
이렇게되면 fast가 nullptr이므로 slow는 리스트의 중간을 가리킨다.
slow가[3]을 가리키므로 리스트를[1, 2] | [3, 4, 5] 로 나눌 수 있음
이렇게 쪼개면 두개의 리스트가 되는데
여기서 첫번째리스트의 시작주소와 두번째리스트의 시작주소를 이용해서 병합정렬을 할수있다.
분할을 했으니 정복의 시간이다.
다시 이 리스트들을 비교하면서 정렬하면된다.
쉽게 생각하면 10명이 탈수있는 엘레베이터가 두개있는 건물이 있다. 건물의 각층마다 한개의 입구와 출구가 있다.
이런 건물 6층에 가야하는 인원이 20명이 엘레베이터에 타고 내리는것과 비슷하다.
엘레베이터에 탑승할때는 무작위지만 나올때는 각 엘레베이터에서 정렬되서 나온다.
또 엘레베이터에서 나온사람들은 입구로 들어갈때 한번더 정렬된다.
이게 바로 병합정렬이 아닐까 생각한다.
Mylist.h
pragma once
#include <assert.h>
#include <iostream>
class MyNode
{
public:
MyNode* prev;
int val;
MyNode* next;
size_t count;
MyNode(int val);
MyNode(MyNode* prev, int val, MyNode* next);
};
/*
만들어 놓은 연결리스트는. 추후 정렬 구현에도 사용 할 예정.
*/
class MyList
{
private:
MyNode* frontNode; //head
MyNode* backNode; //tail
int count; //리스트에 저장된 노드 개수
MyNode* atNode(int at);
MyNode* mergeSortRecursive(MyNode* head);
MyNode* merge(MyNode* left, MyNode* right);
MyNode* getMiddle(MyNode* head);
public:
MyList();
~MyList();
void push_front(int val);
void push_back(int val);
void pop_back();
void pop_front();
int& front(); // 맨 앞의 값 반환.
int& back(); // 맨 뒤의 값 반환.
int at(int index);
void insert(int index, int value);
void erase(int index, int value);
void clear(); // 리스트 내부의 모든 노드 삭제
void print(); // 리스트 값들을 cout으로 출력(연습용 함수)
size_t size(); // 리스트에 들어있는 데이터의 수 반환.
void Swap(int& a, int& b);
int Max(int x, int y);
void BubbleSort();
void mergeSort();
};
Mylist.cpp
#include "Mylist.h"
MyNode::MyNode(int val) //prev,next가 nullptr이고 데이터만 포함하는 노드 생성
{
prev = nullptr;
next = nullptr;
this->val = val;
}
MyNode::MyNode(MyNode* prev, int val, MyNode* next) //prev,next ,데이터를 포함하는 노드 생성
{
this->prev = prev;
this->val = val;
this->next = next;
}
MyNode* MyList::atNode(int at)
{
if (at < 0 or at >= count)
{
return nullptr;
}
MyNode* current = frontNode; //현재노드를 head에서 시작
for (int i = 0; i < at; i++)
{
current = current->next;
}
return current;
}
MyList::MyList()
{
frontNode = nullptr;
backNode = nullptr;
count = 0;
}
MyList::~MyList()
{
clear();
}
void MyList::push_front(int val)
{
MyNode* newNode = new MyNode(val);
if (frontNode == nullptr) //노드가 비어있으면
{
frontNode = backNode = newNode;
}
else
{
frontNode->prev = newNode;
newNode->next = frontNode;
frontNode = newNode;
}
frontNode->prev = nullptr;
count++; //노드요소의 개수를 1만큼 늘린다.
}
void MyList::push_back(int val)
{
MyNode* newNode = new MyNode(val);
if (backNode == nullptr) //리스트가 비어있으면
{
frontNode = backNode = newNode;
}
else
{
backNode->next = newNode;
newNode->prev = backNode;
backNode = newNode;
}
backNode->next = nullptr;
count++;
}
void MyList::pop_back()
{
if (backNode == nullptr)
{
return;
}
if (frontNode == backNode)
{
delete backNode;
frontNode = backNode = nullptr;
}
else
{
MyNode* temp = backNode; //현재 마지막노드 저장
backNode = backNode->prev; //tail한칸뒤로 이동
backNode->next = nullptr; //tail이 nullptr를 가리키게함
delete temp;
}
count--;
}
void MyList::pop_front()
{
if (frontNode == nullptr)
{
return;
}
if (frontNode == backNode)
{
delete frontNode;
frontNode = backNode = nullptr;
}
else
{
MyNode* temp = frontNode; //현재 첫노드 저장
frontNode = frontNode->next; //head한칸앞으로 이동
frontNode->prev = nullptr; //head가 nullptr를 가리키게함
delete temp;
}
count--;
}
int& MyList::front()// 맨 앞의 값 반환.
{ // TODO: 여기에 return 문을 삽입합니다.
if (frontNode != nullptr)
{
return frontNode->val;
}
}
int& MyList::back()// 맨 뒤의 값 반환.
{
// TODO: 여기에 return 문을 삽입합니다.
if (backNode != nullptr)
{
return backNode->val;
}
}
int MyList::at(int index)
{
MyNode* node = atNode(index);
if (node == nullptr)
{
return -1; //잘못된 index면 -1 반환
}
return node->val;
}
void MyList::insert(int index, int value)
{
if (index < 0 || index > count)
return;
if (index == 0) //맨앞
{
push_front(value);
return;
}
if (index == count) //맨뒤
{
push_back(value);
return;
}
MyNode* prevNode = atNode(index - 1); // 삽입위치 찾기
MyNode* nextNode = prevNode->next;
MyNode* newNode = new MyNode(prevNode, value, nextNode);
prevNode->next = newNode;
nextNode->prev = newNode;
count++;
}
void MyList::erase(int index, int value)
{
MyNode* deleteNode = atNode(index);
if (deleteNode == nullptr)
return;
if (deleteNode == frontNode)
{
pop_front();
return;
}
if (deleteNode == backNode) //마지막 노드 삭제
{
pop_back();
return;
}
deleteNode->prev->next = deleteNode->next; //이전 노드의 next 수정
deleteNode->next->prev = deleteNode->prev; //다음 노드의 prev 수정
delete deleteNode;
count--;
}
void MyList::clear() // 리스트 내부의 모든 노드 삭제
{
MyNode* current = frontNode;
while (current) //포인터가 nullptr이 아니면
{
MyNode* nextNode = current->next;
delete current;
current = nextNode;
}
frontNode = nullptr;
backNode = nullptr;
count = 0;
}
void MyList::print() // 리스트 값들을 cout으로 출력(연습용 함수)
{
MyNode* current = frontNode;
while (current != nullptr)
{
std::cout << current->val << " ";
current = current->next;
}
std::cout << std::endl;
}
size_t MyList::size() // 리스트에 들어있는 데이터의 수 반환.
{
return count;
}
void MyList::BubbleSort()
{
for (int i = 0; i < size(); i++)
{
for (int j = 0; j < size() - 1 - i; j++)
{
MyNode* node1 = atNode(j);
MyNode* node2 = atNode(j + 1);
if (at(j) > at(j + 1))
{
Swap(node1->val, node2->val);
}
}
}
}
void MyList::mergeSort()
{
if (frontNode == nullptr || frontNode->next == nullptr) {
return;
}
frontNode = mergeSortRecursive(frontNode);
MyNode* current = frontNode;
while (current && current->next) {
current = current->next;
}
backNode = current;
}
MyNode* MyList::mergeSortRecursive(MyNode* head)
{
if (head == nullptr || head->next == nullptr) {
return head;
}
MyNode* middle = getMiddle(head);
MyNode* secondHalf = middle->next;
middle->next = nullptr;
if (secondHalf) {
secondHalf->prev = nullptr;
}
MyNode* left = mergeSortRecursive(head);
MyNode* right = mergeSortRecursive(secondHalf);
return merge(left, right);
}
MyNode* MyList::getMiddle(MyNode* head)
{
if (head == nullptr) {
return nullptr;
}
MyNode* slow = head;
MyNode* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
MyNode* MyList::merge(MyNode* left, MyNode* right)
{
if (left == nullptr) {
return right;
}
if (right == nullptr) {
return left;
}
MyNode* result = nullptr;
if (left->val <= right->val) {
result = left;
result->next = merge(left->next, right);
if (result->next) {
result->next->prev = result;
}
}
else {
result = right;
result->next = merge(left, right->next);
if (result->next) {
result->next->prev = result;
}
}
return result;
}
void MyList::Swap(int& a, int& b)
{
int temp{ 0 };
temp = a;
a = b;
b = temp;
}
int MyList::Max(int x, int y)
{
int x1{ x }, y1{ y };
if (x1 > y1) { return x1; }
else { return y1; }
}
출력
작성했다가 실패한 코드
MyNode* MyList::Split(MyNode* head)
{
if (!frontNode || !frontNode->next) { return nullptr; }
MyNode* slow = head; //중간지점을 찾는 노드
MyNode* fast = head; //맨끝을 찾는 노드
//포인터 두개로 리스트 한개를 리스트 두개로 나눈것처럼 조작
//노드가 비어있지않거나 맨끝을 가리키지 않으면 반복
while (fast->next != nullptr && fast->next->next != nullptr)
{
slow = slow->next; //1칸씩 이동
fast = fast->next->next; // 2칸씩 이동
}
if (slow->next == nullptr) { return nullptr; }
MyNode* secondHead = slow->next; //두번째 리스트의 시작 노드 = 첫번째리스트의 마지막 노드
slow->next = nullptr; //첫번째 리스트와 두번째 리스트 연결끊기
if (secondHead)
{
secondHead->prev = nullptr;
}
return secondHead; //두번째 리스트의 시작주소 반환
}
MyNode* MyList::MergeSort(MyNode* head)
{
if (head != nullptr || head->next != nullptr) //리스트가 비어있거나 노드가 하나면 정렬할 필요 없음
return head;
MyNode* secondHead = Split(head); // 리스트를 반으로 나눔
head = MergeSort(head); //첫 번째 반을 재귀적으로 정렬
secondHead = MergeSort(secondHead); //두 번째 반을 재귀적으로 정렬
return Merge(head, secondHead); //정렬된 두 개의 리스트 병합
}
MyNode* MyList::Merge(MyNode* head, MyNode* secondHead)
{
if (!head) return secondHead;
if (!secondHead) return head;
MyNode* mergedHead;
if (head->val < secondHead->val)
{
mergedHead = head;
head = head->next;
}
else
{
mergedHead = secondHead;
secondHead = secondHead->next;
}
MyNode* mergedTail = mergedHead; //mergedTail부터 시작해서 두 리스트의 값을 비교하며 병합
while (head != nullptr && secondHead != nullptr)
{
if (head->val < secondHead->val)//두번째 값이 더 크면
{
mergedTail->next = head;
head->prev = mergedTail;
head = head->next;
}
else //첫번째 값이 더 크면
{
mergedTail->next = secondHead;
secondHead->prev = mergedTail;
secondHead = secondHead->next;
}
mergedTail = mergedTail->next;
}
// 남은 노드 연결
if (head != nullptr)
mergedTail->next = head;
else
mergedTail->next = secondHead;
return mergedHead;
}
MyNode* MyList::getFrontNode()
{
return frontNode;
}내가 처음에 짠 코드대로하면 분할만 하고 정복을 못했다.
//MergeSort 함수의 조건문 오류: 논리 연산자가 잘못 사용됨
if (head != nullptr || head->next != nullptr)
//수정
if (head == nullptr || head->next == nullptr)
//Merge 함수의 마지막 부분 오류:
if (head != nullptr) mergedTail->next = head; else mergedTail->next = secondHead;
//이 부분에서 남은 노드를 연결할 때 prev 포인터를 설정하지 않음
//이중 연결 리스트에서는 prev 포인터도 올바르게 설정해야함
if (head != nullptr) { mergedTail->next = head; head->prev = mergedTail; } else if (secondHead != nullptr) { mergedTail->next = secondHead; secondHead->prev = mergedTail; }
//Split 함수의 초기 조건 검사 오류:
if (!frontNode || !frontNode->next) { return nullptr; }
//이 함수는 인자로 받은 head를 사용해야 하는데, frontNode를 사용하
//수정
if (!head || !head->next) { return nullptr; }
//Split 함수의 종료 조건 검사 추가:
if (slow->next == nullptr) { return nullptr; }
//mergeSort 전체 알고리즘이 완료된 후 backNode를 업데이트하는 코드가 없다.
//정렬 후에 backNode를 올바르게 설정해야함
//Merge 함수에서 병합 후 마지막 노드의 next를 nullptr로 설정하는 코드가 빠져있음