Data Structure

개강을 약 2주 앞두고 자료구조를 빠르게 복습하여 정리하고자 시리즈를 추가하게 되었다.

기존의 정적으로 할당 받는 방식의 배열은 정해진 인덱스를 초과하면 더 이상 값을 저장할 수 없지만 동적으로 할당 받는 Dynamic Array는 할당 받은 메모리를 초과하면 추가로 데이터를 저장할 수 있다.

스택은 나중에 들어온 데이터가 가장 먼저 나가는 후입선출(LIFO: Last-In First-Out) 형태의 자료 구조이다. 스택은 시스템의 활성 레코드, 웹 브라우저의 뒤로 가기, 그림판 등의 프로그램에서 작업 취소 (Ctrl+Z) 등에 활용된다.

사용자로부터 식을 입력 받아 유효하게 입력되었는지 검사하는 프로그램이다.

이번 문제는 미로 찾기이다.쥐 한 마리가 미로에 갇혀있다. 주어진 미로에서 출구를 찾는 과정을 출력하는 프로그램을 만드는 것이 목표이다.

큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First-In, First-Out) 형태의 자료구조이다. 큐가 사용되는 예로는 프린터의 인쇄 대기열, CPU 작업 스케쥴링 등이 있다.

지난 번 글에서 구현한 동적 배열을 사용한 큐에 단점이 있었다. 자료를 꺼내올 때 모든 데이터를 한 칸씩 앞으로 이동해야 하는 점이었다. 원형 큐로 이러한 단점을 보완할 수 있다.

지난번 글에서 원형 큐에 대해 알아봤다. 원형 큐는 데이터의 맨 앞과 뒤의 인덱스를 저장하여 선형 배열을 마치 원형인 것처럼 사용하는 자료구조였다. 이번 글에서는 실제로 원형 큐를 어떻게 구현하였는지 소개한다.

덱(Deque)은 데이터의 양 끝에서 추가, 삭제 등이 가능한 자료 구조이다.

이번 글에서는 지금까지 구현한 큐, 원형 큐, 덱을 실제 문제에 활용하는 것을 작성하려 한다. 백준 온라인 저지 -> '문제' -> '단계별로 풀어보기' -> '큐, 덱'에 포함되는 문제들이다.

'Data Structure' 시리즈를 마치며

자료구조 복습 삼아 버블 정렬을 C로 구현해 보았다.

선택 정렬을 구현해 보았다.

삽입 정렬을 구현해 보았다.주어진 요소마다의 위치를 찾아서 삽입한다.삽입될 때엔 공간을 마련하기 위해 한 칸씩 뒤로 밀려난다.

분할 정복 알고리즘 중 하나인 합병 정렬을 구현해본다. 재귀적 구조로 구현할 수 있다.