목록전체 글 (58)
-
- 삽입 정렬을 보완한 정렬 알고리즘 - 삽입 정렬의 단점은 비효율적으로 값의 교환 횟수가 많아질 수 있다는 점이다. ex) 10개의 배열 요소 중, 8번째 값을 정렬된(왼쪽) 리스트에 삽입할 위치를 찾기 위해 그만큼 비교 연산을 해야함. - 쉘 정렬은 이러한 삽입 정렬의 단점을 보완하여 정렬할 배열을 여러개의 부분 배열로 나누어 나누어진 배열에 대해 삽입 정렬을 수행한다. 따라서 서로 멀리 떨어진 요소들간의 비교 연산또한 효율적으로 할 수 있다. - 쉘 정렬은 중간 크기의 목록에 효율적. 병합, 힙, 퀵 정렬보다는 현저히 느리지만 속도가 우선시 되지 않는 5천개 정도의 요소를 가진 목록에는 좋을 수 있음 - 셸 정렬에서는 요소들이 멀리 떨어진 위치로 이동할 수 있다는 장점이 있다. 이런 것이 가능한 이..
- 매 반복마다 뒤쪽의 정렬되지 않은 요소들의 목록에서 요소를 삭제하고 삭제한 요소를 앞쪽의 이미 정렬된 목록 내 알맞은 자리에 삽입. - 입력 데이터에서 삭제될 요소는 정렬되지 않은 목록에서 무작위로 선택(보통 앞에서 차례대로) - 0번과 1번 인덱스는 정렬이 되어 있다고 가정(반복되면서 알아서 정렬됨) - 시간 복잡도 Worst: O(n^2) Best: O(n) Average: O(n^2) - 공간 복잡도: O(1) - 삽입 정렬은 미리 데이터가 어느 정도 정렬 되어 있거나 입력 데이터가 적을 경우 사용. --> 병합 정렬 or 퀵 정렬과 같은 분할 정복 알고리즘의 base case로 사용되기도 함 void insertion_sort(int arr[], int size_arr) { for (int i..
- 선택 정렬은 작은 양의 데이터에 유용. - 구현이 쉽고 제자리 정렬(추가 저장 공간이 필요 없음) --> bubble sort나 insertion sort 등도 마찬가지. 그냥 temp 변수 선언으로 치환 할 뿐. 알고리즘 1. 목록에서 최소값을 찾는다. 2. 찾은 최소값을 맨 앞의 값(혹은 현재 위치의 값)과 교체 3. 배열의 전체 요소가 정렬될 때까지 이 과정을 반복. - 시간 복잡도 Worst: O(n^2) Best: O(n) Average: O(n^2) - 공간 복잡도: O(1) void selection_sort(int arr[], int size_arr) { for (int i = 0; i < size_arr; i++) { int min = i; for (int j = i + 1; j < ..
- 일반적으로 버블 정렬보다 삽입 정렬의 복잡도가 더 좋다고 함. - 유일한 장점/사용 이유? 는 입력 목록이 이미 정렬되어 있는지를 탐지할 수 있다는 점 - 시간 복잡도 Worst: O(n^2) Best: O(n) --> 이미 정렬되어 있는 경우. Average: O(n^2) - 공간 복잡도: O(1) - 개선된 Bubble 정렬 코드 --> Swap 하는 부분에 flag 변수를 넣어서 한 바퀴 도는 동안 flag 변수가 바뀌지 않았다면 이미 정렬이 완료된 것이기에 Loop를 끝낸다. void bubble_sort_advanced(int data[], int n) { int i, j; int temp; int flag = 1; for (i = n - 1; flag&&i >= 1; i--) { flag ..
Stable/Unstable 정렬 --> 비교 대상의 Key가 여러개 값을 가질때 혹은 같은 값을 가지는 데이터가 여러개 있을 때, 정렬후에 기존의 순서를 유지하는지에 따라 Stable과 Unstable로 나뉜다. 비교 Key가 한 개일때는 나누는 것이 굳이 의미 없지만 여러개일 경우(구조체 함수 데이터) 특정한 데이터를 기준으로 Sorting할 경우 Stable/Unstable 정렬의 종류를 고려하여 적용해야 한다. 예를들어 Dave A Alice B Ken A Eric B Carol A 위와 같은 데이터를 정렬하려면 두 가지를 기준으로 정렬할 수 있다. 여기서 중복되는 데이터가 있는데 정렬 전 원래의 순서를 기억할것이냐 말것이냐에 따라 Stable과 Unstable 알고리즘을 선택해야 한다. Stab..
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 핵심 로직은 map 에서 1이상을 가지는 값의 갯수를 저장해두고 사용한다. DFS 순회를 할 때마다 4방향을 조사하여 0의 갯수만큼 차감해주..
불필요한 코드를 생성해서 당연히 시간초과 + 오답이 나왔다. 개인적으로 가장 싫어하고 어려워하는 유형의 문제이다. 차라리 조합으로 문제를 풀면 접근이라도 쉬울텐데. 여기서 배운 점은 1000000번 루프를 돌려봐야 1초안에 끝난다는 것! 기본적인 로직은 i 가 루프를 돌면서 자릿수만큼 더해주는데 이 값을 저장한 변수가 Input 값과 같으면(처음 같을 때가 당연히 최소값!) 출력, i가 1000000을 넘어가면 당연히 못찾은 경우로 간주! 코드: #include#includeusing namespace std; int N; //int fun(int n){//vector vec;//int tmp = n;//while (tmp > 0){//int get = tmp % 10;//vec.push_back(get..
그냥. 노가다로 풀었다. rotate 함수를 호출할때마다 x,y의 좌표의 경계와 그 다음을 위치를 체크하여 맵의 범위를 벗어나려하면 스킵하였다. 문제를 정확히 읽어야만... 맵의 숫자를 주사위에 카피하고 맵의 숫자를 0으로 초기화 해주지 않아 한참을 고생하였다. 코드: #include using namespace std; int n, m, x, y, k, o;int map[21][21];int cube[4][3];int cp[4][3];int nx;int ny; //동쪽은 1, 서쪽은 2, 북쪽은 3, 남쪽은 4 void copy_cube(){for (int i = 0; i < 4; i++){for (int j = 0; j < 3; j++){cp[i][j] = cube[i][j];}}}int rotate..