Algorithm/Data Structure

큐(Queue)란? 스택의 경우에는 나중에 들어온 데이터가 먼저 나가는 구조였다. 하지만 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO : First In First Out)구조이다. 매표소에서 표를 끊는다고 생각해보자. 당연히 먼저 와서 줄을 선 사람이 먼저 표를 받고 자리를 떠날 수 있다. 만약 뒤에 온 사람이 먼저 표를 받는다면 먼저 온 사람이 몹시 화가 나는 상황이 발생할 것이다. 따라서 매표소 시스템을 구현하려면 큐를 사용해야 할 것이다. 큐의 기본 구조 큐의 기본 구조를 알아보자. 큐의 앞 부분을 전단(front), 뒷 부분을 후단(rear)라고 한다. 데이터의 이동 방향은 화살표 친 것과 같다. 그림으로 큐 이해하기 큐에서 필요한 연산들 create(max_size) ..

✔ 스택(Stack) 스택(stack)은 동사로 '쌓다'를 의미합니다. 맞아요!! 스택은 걍 냅다 쌓는 것임!! 사실 핵심 내용은 그게 다예요. 쉽게 박스에 자료들을 넣는다고 생각해보세요. 박스의 엉덩이쪽으로 자료를 넣을 수 있나요?.. 웃기고 싶은 게 아니라면 굳이 그런 행동을 하지는 않겠죠 무조건 박스의 위쪽으로 자료를 넣고 뺄 때도 위쪽으로 뺍니다. 스택에서의 입출력은 박스처럼 맨 위에서만 일어납니다. 아래의 그림처럼요. 이런 방식을 Last In First Out(LIFO) 방식이라고 합니다. 함수 호출 스택은 컴퓨터 안에서도 사용되는데요. 그 예 중 하나로 함수 호출이 있습니다. 컴퓨터에서는 수많은 함수 호출이 일어납니다. 함수는 실행이 끝나고 나면 자신을 호출한 함수로 되돌아가야 하는데요. 이..

삽입 정렬 ( Insertion Sort ) 삽입 정렬은 손 안의 카드를 정렬 하는 방법과 유사하다. 기존의 정렬된 카드 사이에 새로운 카드 위치를 찾아 삽입한다. 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해 자신의 위치를 찾아 삽입한다. 방식 - 두번째 자료부터 시작해 왼쪽의 자료들과 비교한 뒤 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입한다. - 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시켜야 한다. 코드 void insert_sort(int list[], int n) { int key; int j; for (int i = 1; i < n; i++) { // 두 번째 값부터 봐야하므로 index = 1 key = list[i]; for (j = i - 1; j ..

Bubble sort 방식 거품정렬(bubble sort)이란, 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 앞서 포스팅 했던 선택 정렬과 비슷하게 크기가 순서대로 되어있지 않으면 swap한다. 이번에도 예시로 살펴보자. 1회차 24 36 10 6 12 24 10 36 6 12 24 10 6 36 12 24 10 6 12 36 36의 위치 고정 2회차 10 24 6 12 36 10 6 24 12 36 10 6 12 24 36 24의 위치 고정 3회차 6 10 12 24 36 12의 위치 고정 ... 위와 같은 과정을 반복하여 마지막에는 오름차순으로 정렬 된다. 시간 복잡도 선택정렬과 같은 O(n^2) 코드 swap 함수 void swap(int& x, int& y) { int temp = x;..

정렬 알고리즘에 대해 알아보기 앞서, 배열에 저장된 값에는 관계 연산자가 정의된 유형의 키가 있다. 정렬은 요소를 배열 내에서 오름차순 또는 내림차순으로 재정렬 하는 것을 의미한다. 단순 선택 정렬 (Straight selection sort) 단순 선택 정렬이란, 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다. 방식 예를 들어, 0 36 1 24 2 10 3 6 4 12 위와 같은 배열이 있고, 아직 정렬하지 않은 부분을 빨간색으로 표시했다고 생각해보자. 1. 배열에서 가장 작은 값은 6이다. 2. 6을 정렬하지 않은 부분의 첫 번째 요소와 교환한다. 0 6 1 24 2 10 3 36 4 12 다음으로 가장 작은 값은 10이다. 10을 정렬하지 않은 부분의 첫번째 요소와..

C++ 링크드리스트로 리스트 구현하기개요이번 포스팅에서는 링크드리스트에 대해 알아보고 링크드리스트의 종류 중 단순 연결 리스트(singly linked list)를 C++로 구현해볼 것이다.링크드리스트란? 그림과 같이, linked list는 줄로 연결된 상자들의 집합이다.줄은 포인터로 구현 가능하며, 상자 안에는 데이터가 들어간다.줄을 따라가면 다음 상자를 찾을 수 있다. 데이터들은 메인 메모리상의 어디에나 흩어져서 존재할 수 있다.이런식으로 물리적으로 흩어져 있는 자료들을 서로 연결해 하나로 묶는 방법을 연결 리스트(linked list)라고 한다. 이전 포스팅에서 링크드리스트의 장점 중 하나로, 삽입이나 삭제 시 앞뒤의 데이터들을 이동할 필요가 없는 점을 언급했다. 이 부분에 대해 더 알아보자.링크..

포스팅에 앞서C++로 리스트를 구현하는데에는 구조체와 포인터, 동적할당에 대한 이해가 필요합니다. 따라서 이해가 부족한 경우 이전 포스팅을 먼저 보시는 것을 추천합니다.리스트란?리스트(list)는 우리가 자료를 정리하는 방법 중 하나다.예를 들어, 학생의 목록이 적혀있는 출석부라든가, 들어야 할 강의 목록과 같은 것을 리스트로 관리한다.리스트의 특징을 살펴보자. 리스트에는 항목들이 차례대로 저장되어 있다.리스트의 각 항목은 순서 또는 위치(index)를 가진다.리스트를 가지고 할 수 있는 기본적인 연산에는 어떤 것들이 있을까? 삽입 : 리스트에 새로운 항목을 추가한다.삭제 : 리스트에서 항목을 삭제한다.탐색 : 리스트에서 특정한 항목을 찾는다.초기화 : 리스트의 모든 요소를 제거한다.길이 : 리스트의 길..

1. 재귀(recursion)란? 1. 자기 자신을 호출하며 2. 갈수록 더 작은 문제를 풀게 한다. 3. 그러다가 결국 basic case에 수렴하게 되는 것이다. 2. 팩토리얼 팩토리얼으로 재귀함수에 대해 감을 잡아보자. 4! = 4 * 3 * 2 * 1 이다. 그런데 이것을 4! = 4 * 3! 으로 나타낼 수 있고, 3!은 다시 3 * 2! 2!은 2 * 1!이다. 이것을 코드로 나타내보면 다음과 같다. #include using namespace std; int fact(int n) { if (n == 0 || n == 1) { return 1; } else { return n * fact(n - 1); } } int main() { cout 0; i--) { fact *= i; } cout 메..