알고리즘 시*련아 (11) 썸네일형 리스트형 백준 시간 초과와 시간 복잡도 *발 안녕 너희는 백준 2477번 참외밭 문제를 풀어보았니? 문제에서 젖비린내 난다고? *발 샤워부터 하고 와 파오후 *들아ㅋㅋ 거두절미(去頭截尾)하고 시간 초과가 났던 이 문제를 다시 생각해 보면서 시간 복잡도와 수행 시간에 대해 알아보자고 cpu가 1초안에 수행할 수 있는 연산은 1억번이라고 생각하는것이 국룰이란다 그러면 상당히 간단해 지는데, 시간제한이 1초라면 (N은 입력) 대략 O(1), O(log N) N C++ 백준 1008번에 관해 참... 나 자신에게 깊은 실망을 하게된 문제다 이 문제로 말할것 같으면 두가지 핵심인 자료형과 출력만 잘 생각해주면 되는 문제다. 먼저 자료형으로 말할것 같으면 소수표현이 가능한 실수 자료형을 사용하는것이 당연하다. C++에 있는 실수 자료형으로 말할것 같으면, float와 double이 있다 두 자료형의 크기는 각각 4byte, 8byte이다.(운영체제에 따라 다르겠지만) 자료형 크기 소수점이하 정밀도 float 4byte 6자리 double 8byte 15자리 실수자료형의 소수표현 오차는 가수부분의 크기가 크면 클수록 작다. 오차범위 10^9자리까지 허용하는 이번 문제를 위해서는 double을 사용하는것이 인지상정이다. 좋다 double을 사용하자 그럼 이젠 출력만 잘 해주면 된다. 항상 블로그 포.. C++ STL sort() - 정렬6 물론 나는 대회 발끝에도 닿아보지 못한 사람이다 하지만 나는 상당히 이상적인 사람이다. 이상적인 사람의 특징은 지금 당장은 쓸모가 없어도 나중에 필요할거 같다면서 요긴해 보이면 모든지 가져간다는 것이다. (적어도 나는 그렇다) 아무튼 오늘 배운 STL sort()도 그런것이다. 나의 은사 동빈나 선생님이 말씀하시길 알고리즘 대회에서 자신이 직접 정렬 알고리즘을 짜는것은 시간 낭비라고 하셨다. 유튜브에서 그대로 배껴온 내 정렬 알고리즘 대신 몇 십년간의 진화를 거듭해온 컴퓨터과학의 로니콜먼같은 사람이 먼저 만들어 놓은 C++ 표준라이브러리의 sort()를 사용하는것이 현명하다. 기본적인 사용법이다 #include #include //STL 함수들을 사용하려면 꼭 추가해 주어야 한다 using namespa.. C++ 병합 정렬(합병 정렬) - 정렬5 이 정렬 알고리즘은 대단하다 평균 O(nlogn)이 나오는 아주 대단한 정렬이라고 볼 수 있다. 병합 정렬. 나는 비록 합병 정렬이라고 부르지만. 아무튼 이 대단한 합병 정렬은 분할 정복법의 교과서 같은 알고리즘이라고 볼 수 있다 병합 정렬의 아이디어는 1. 배열의 모든 원소를 분할 시킨다 2. 분할된 모든 원소를 합병하면서 정렬한다 합병 정렬에서 합병은 실제 정렬이 일어나는 부분이다 1. i, j 로 합병할 두 배열의 첫원소를 가르킨다 (이때 두 배열 이미 정렬이 되어있는 상태이다) 2. i와 j를 비교하여 더 작은 원소를 sorted 배열에 추가하고 + 1을 해준다 3. i 또는 j가 합병할 배열의 끝에 도달했다면 4. 나머지들을 sorted 배열에 추가한다 5. 마지막으로 sorted 배열의 내용물.. C++ 퀵정렬 - 정렬4 퀵 정렬은 대놓고 이름에다가 퀵을 붙여놓은 아주 대담한 정렬이다 그동안의 정렬과 다른 점은 시간 복잡도에 있는데 평균적으로 O(n²)의 시간 복잡도를 가지고 있는 선택, 버블, 삽입과 달리 퀵 정렬은 평균적으로 O(nlogn)의 시간 복잡도를 가지고 있다. 퀵 정렬이 log시간을 가질 수 있는 이유는 분할 정복 알고리즘이기 때문이다 퀵 정렬의 아이디어는 1. 피봇을 정하고 (대부분의 경우 가장 앞의 원소) 2. 왼쪽부터 차례로 피봇보다 큰 값을 3. 오른쪽부터 차례로 피봇보다 작은 값을 찾는다 4. 두 값을 찾았다면 서로 자리를 바꾼다 5. 만약 피봇보다 큰 값의 인덱스와 피봇보다 작은 값의 인덱스가 작아지면 (엇갈리면) 6. 피봇보다 작은 값과 피봇의 자리를 바꾼다 7. start ~ 작은 값 인덱스-.. C++ 삽입 정렬 - 정렬3 삽입 정렬은 O(n²) 정렬 알고리즘 중 가장 효율적인 알고리즘이다 삽입 정렬은 한 원소를 선택하여 그 원소를 알맞은 위치에 삽입하는 알고리즘이다 아이디어는 1. 한 원소를 선택하여 2. 선택한 원소보다 작은 원소를 만날때까지 앞의 원소와 비교한다 3. 앞의 원소가 선택한 원소보다 작다면 선택한 원소와 자리를 바꾼다 4. 선택한 원소보다 작은 원소를 만나면 멈춘다 언뜻 보면 버블 정렬과 유사해 보이지만 다른 점은 정렬을 멈추는 지점을 알기 때문에 선택 정렬이나 버블 정렬과 다르게 불필요한 정렬을 하지 않는다 선택 정렬에서는 왼쪽의 원소들은 이미 정렬이 되어있다는 가정을 하기 때문에 왼쪽으로 탐색했을 때 자기 자신보다 작은 원소가 있다면 거기서 멈추면 된다 int* InsersionSort(int* arr.. C++ 버블정렬 - 정렬2 두번째로 가장 간단한 정렬 알고리즘이다 아이디어는 1. 바로 옆의 값과 비교하여 큰값을 오른쪽으로 보낸다 2. 옆으로 한칸 이동하여 배열 끝까지 반복한다 3. 끝까지 반복하면 가장 큰 수가 가장 오른쪽에 위치하게 된다 1~3까지가 1회전 4. 배열의 개수만큼 회전한다 int* BubbleSort(int* arr, int size){ for(int i=0; i arr[j+1]){// 이미 정렬이 되어 있기 때문이다 && 추가적으로 -1을 해주는 이유는 // 원소들을 비교할때 j+1을 하기 때문이다. int temp = arr[j]; arr[.. C++ 선택정렬 - 정렬1 정렬중에서 가장 간단하고 직관적인 정렬이다 아이디어는 1. 배열중에서 가장 작은 숫자를 선택한다 2. 선택한 숫자와 가장 앞에있는 숫자를 교체한다 int* SelectionSort(int* arr, int size){ int min, index = 0, temp; for(int i=0; i < size; i++){ min = 10000; for(int j=i; j < size; j++){ //~i 까지 정렬이 되어있으므로 i에서 부터 시작 if(arr[j] < min){// 배열의 최소값을 찾는다 min = arr[j]; index = j; } } temp = arr[i];//최솟값과 가장 앞의 값을 교체한다 arr[i] = arr[index]; arr[index] = temp; } return arr;.. 이전 1 2 다음
