일지
-
알고리즘...17일지 2021. 7. 8. 12:33
병합 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. MergeSort.hpp #pragma once #include "../Common.hpp" void MergeSort(int arr[], int tempArr[], int p, int r, bool printData = false, int n = 0); void Merge(int arr[], int tempArr[], int p, int q, int r); /// /// 주어진 배열을 정렬한다. /// /// 정렬을 진행할 배열 /// 배열의 길이 /// 중간 결과 출력 여부 void MergeSort(int arr[], int n, bool printData = false) { if (printData) { Common:..
-
JUNGOL...86일지 2021. 7. 7. 12:14
Beginner_Coder/자료처리/버블정렬 문제 거품 정렬(Bubble sort)이란? 두 인접한 원소를 검사하여 자리를 바꾸는 과정을 반복하며 정렬하는 방법이다. 다음과 같은 과정으로 정렬을 한다. 1. 첫번째 값과 두번째 값을 비교하여 첫번째 값이 크면 자리를 바꾼다. 2. 두번째 값과 세번째 값을 비교하여 두번째 값이 크면 자리를 바꾼다. 3. 위와 같이 반복하여 N-1번째 값과 N번째 값을 비교하여 N-1번째 값이 크면 자리를 바꾼다. 이 단계가 끝나면 N번째에 가장 큰 수가 자리하게 된다. (한단계완료) 4. N번째를 제외하고 1~3을 반복하면 N-1번째에 두 번째로 큰수가 자리한다. (2단계 완료) 5. 위와같은 작업을 N-1번 반복하면 모든 데이터가 순서대로 정렬된다. 예를 들어 수열 {6..
-
알고리즘...16일지 2021. 7. 7. 12:02
병합 정렬 입력 배열을 반으로 나누고 나눈 배열을 하나의 배열로 병합하여 정렬을 진행한다. 병합 정렬 알고리즘 배열의 크기를 반으로 나누는 과정을 각각의 크기가 1이 될 때까지 반복하고 이후 각각의 배열을 병합할 때 정렬을 진행한다. 병합 정렬 알고리즘 MergeSort(A[], p, r) { if (p < r) then { q ← └(p + r) / 2┘ MergeSort(A, p, q) MergeSort(A, q + 1, r) Merge(A, p, q, r) } } Merge(A[], p, q, r) { 정렬되어 있는 두 배열 A[p...q]와 A[q + 1...r]을 합쳐 정렬 된 하나의 배열 A[p...r]을 만든다. } 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
JUNGOL...85일지 2021. 7. 5. 11:35
Beginner_Coder/자료처리/삽입정렬 문제 삽입정렬(Insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방법이다. 수열이 {5 4 3 7 6}이 있을 경우의 삽입정렬 과정은 다음과 같다. 처음상태에서 처음 값 5 앞에 아무것도 없으므로 5는 이미 정렬된 상태가 되므로, 이후 4부터 정렬과정을 살펴보자. ※ 3단계의 경우 7은 앞의 "3 4 5"보다 크므로 제자리에 삽입된다. n개의 수열이 주어지면 위와 같은 방법으로 정렬하는 과정 각 단계를 출력하는 프로그램을 작성하시오. 입력 형식 첫줄에 수열의 길이 N(4≤N≤100)이 주어진다. 두 번째 줄에 N개의 0이상 100이하의 정수가 주어진다. 출력 형식 처음 상..
-
알고리즘...15일지 2021. 7. 4. 17:42
삽입 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. InsertionSort.hpp #pragma once #include "../Common.hpp" /// /// 주어진 배열을 정렬한다. /// /// 정렬을 진행할 배열 /// 배열의 길이 /// 중간 결과 출력 여부 void InsertionSort(int arr[], int n, bool printData = false) { if (printData) { Common::PrintArray(arr, n); } for (int i = 1; i = 0; j--) { if (arr[curIdx] < arr[j]) { Common::S..
-
JUNGOL...84일지 2021. 7. 4. 10:18
Beginner_Coder/자료처리/선택정렬 문제 선택 정렬(selection sort)이란 내부정렬 알고리즘의 하나로 다음 순서대로 실행하여 정렬을 한다. 1. 주어진 수열 중에 최소값(같은 값이 여러 개 있는 경우 처음 값)을 찾는다. 2. 찾은 최소값을 맨 앞의 값과 자리를 바꾼다. 3. 맨 앞의 값을 뺀 나머지 수열을 같은 방법으로 전체 개수-1번 반복 실행한다. n개의 주어진 수열을 위와 같은 방법으로 정렬한다. 수열이 주어지면 선택정렬의 과정을 한 단계씩 출력한다. 입력 형식 첫줄에 수열의 길이 N(4≤N≤100)이 주어진다. 두 번째 줄에 N개의 0이상 100이하의 정수가 주어진다. 출력 형식 처음 상태를 제외하고 정렬과정의 각 단계별 결과를 "출력형식"과 같이 출력한다. 입력 예 5 6 ..
-
JUNGOL...83일지 2021. 7. 3. 14:15
Beginner_Coder/자료처리/큐(queue) 문제 큐는 먼저 들어온 데이터가 먼저 출력된다. 이러한 구조를 선입선출(FIFO - First In First Out)이라고 한다. 이러한 큐 자료구조는 보통 우리의 생활에서는 매우 일상적인 자료구조이다. 큐 자료구조의 형태를 가장 흔히 볼 수 있는 게 “줄서기”가 될 것이다. 은행 창구에서 줄을 서거나, 버스를 기다리기 위해서 줄을 설 경우 가장 먼저 줄을 선 사람이 가장 먼저 은행 업무를 처리하거나, 버스를 타게 된다.(새치기 하는 경우는 생각하지 말자) 그림과 같은 큐 자료구조를 설계하고, 처리조건에 맞는 출력을 하시오. ≪처리조건≫ 1. 주어지는 명령은 다음의 3가지이다. 2. "i a"는 a라는 수를 큐에 넣는다. 이때, a는 10,000 이하..
-
JUNGOL...82일지 2021. 7. 2. 10:16
Beginner_Coder/자료쳐리/스택 (stack) 문제 Stack은 "더미"란 뜻을 가진다. 책 더미, 신문 더미 등에 사용하는 단어이다. 책 더미를 예로 들어 보자. 책 더미를 쌓았다고 했을 때, 이 책 더미에서 책을 가져오는 가장 정상적인 방법은 제일 위에 있는 책을 가져오는 방식이다. 다시 말하면 가장 먼저 들어간 책은 가장 나중에 꺼낼 수 있을 것이다. 이런식으로 자료가 가장 밑에 쌓이고(입력). 자료를 가져올 때(출력)는 가장 위(최근)의 자료를 가져오는 자료구조를 Stack하고 한다. 이러한 Stack의 특징 때문에 흔히 "FILO(First-In-Last-Out : 선입후출)" 혹은 "LIFO(Last-In-First-Out : 후입선출)"라고 한다. 그림과 같이 Stack을 설계하고 ..