본문 바로가기

분류 전체보기89

기수정렬 (Radix sort) 숫자의 각 자리 수는 0~9로 이루어져있기 때문에 자리 수 별로 정리한다고 생각하면 쉽다 1. 우선 일의 자리를 기준으로 해당하는 위치에 배열 후 정렬 2. 그다음 10의 자리 수를 기준으로 정렬 3. 위 과정을 반복하며 최고 자리수까지 정렬하면 된다. 위 그림을 보면 알수 있듯이 먼저들어온 수가 먼저 나가기 때문 queue자료구조를 사용하여 구현해 볼 것이다. 주의 해야할 점은 최대 자리수 보다 작은 자릿수 즉 최대자릿수가 1000일때 1~999 같은 세자리 수는 앞에 자리수를 0으로 계산해 줘야한다. #include #include #include #include #include using namespace std; int arr[20]; queue que[10]; void radixSort(int*.. 2021. 9. 15.
알고리즘의 복잡도 입력 n에 대한 알고리즘의 성능을 평가하는 지표로써 시간복잡도와 공간 복잡도를 사용 시간복잡도 : 알고리즘의 수행시간을 평가 공간복잡도 : 알고리즘에 사용되는 메모리용량에 따라 평가 대표적인 복잡도 카테고리 O(log N) O(N) : 1차(linear) O(n log n) O(n^2) : 2차(quadratic) O(n^3) : 3차(cubic) O(2^n) : 지수(exponential) O(n!) 함수가 다항식일 때 최고차항만을 계산하여 표기함 시간복잡도 함수 증가율 * bigO 표기법 정의 : 주어진 복잡도함수 f(n)에 대해서 g(n) = O(f(n))을 만족한다(= g(n)의 증가율, 기울기가 낮다라고 말할 수 있다.) 정리하자면 시간복잡도에 대한 표기를 bigO 표기법으로 하며, bigO표기.. 2021. 9. 15.
선택 정렬(Selection Sort) 개인적으로 가장 직관적이고 구현하기 쉬운방법 인것같다 반복문이 돌때마다 최솟값을 찾아서 해당 index에 배치하면 된다 버블 정렬과 비슷하지만 교환이 일어나는 횟수는 버블정렬에 비해 적다 시간복잡도는 O(N^2)으로 10개의 배열의 경우 첫번째 배열에서 9개의 원소를 탐색 그다음은 8개 .. 7개.. 이런식으로 최악의 경우와 최선의 경우 상관없이 n-1 + n-2 + ... + 1 이런식이며 n(n-1)/2으로 시간복잡도는 O(N^2)이다. #include using namespace std; int main() { int arr[] = { 6,9,8,1,3,4,2,5,7 }; int arrSize = sizeof(arr) / sizeof(int); int tmp; for (int i = 0; i < a.. 2021. 9. 7.
삽입 정렬(Insertion Sort) 위 그림처럼 하나 key값이 파고들면서 제위치를 찾아간다고 생각하면 이해하기 쉽다 맨 첫번째 원소는 정렬 되어 있다고 가정한 후 두번째 원소부터 비교를 시작하는데 인덱스를 줄여나가면서 앞 원소가 더 큰값이라면 위치를 바꾸는 것을 반복 한 사이클이 돌 때마다 위 그림상 노란색으로 표시 되는 부분이 정렬 순서거 확정된다. 최악의 경우 시간복잡도는 O(N^2)이다. ex) 4 3 2 1을 삽입정렬한다고 가정하면 두번째 원소부터 4와 비교 -> 1번 연산 3,4, 비교 -> 2번연산 2,3,4,비교 -> 3번연산 즉, n(n-1)/2 와 같다. #include using namespace std; int main() { int arr[] = { 6,9,8,1,3,4,2,5,7 }; int arrSize = si.. 2021. 9. 7.
버블정렬(Bubble Sort) 정렬알고리즘을 이해하는 가장 쉬운 방법은 시각적으로 보는 것이라 생각한다. 인접한 요소끼리 대소를 비교해서 큰값을 뒤로 작은값을 앞으로 보낸다고 생각하면 쉽다 위 그림처럼 인접한 요소를 비교해 큰값을 뒤로 보내다 보면 1회차 반복이 끝났을 때 최댓값이 가장 마지막 자리로 가게된다 시간 복잡도는 O(N^2) #include using namespace std; int main() { int arr[] = { 6,9,8,1,3,4,2,5,7}; int arrSize = sizeof(arr) / sizeof(int); int tmp; for (int i = 0; i arr[j]) .. 2021. 9. 7.
[그리디] 백준 4796 캠핑 C++ https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 풀이 : 기본적인 그리디 문제라서 푸는데 그리 오래 걸리지 않았다 문제 읽고 이해하고 푸는데까지 10분?20분? 정도 걸린거같은데 계속 틀렸습니다 떠서 아무리 오류를 찾아도 찾지 못해서 코드를 첨부터 다른방법으로 다시 짰다.. 근데 또 틀렸습니다. 나옴.. 알고보니 출력할때 case 를 Case라고 대문자를 C를 써야하는데 소문자 c를 써서 틀린거였음.. 덕분에 풀이는 두가지 !! 오히려 좋.. 2021. 9. 2.

티스토리툴바