알고리즘4 알고리즘문제 시간 제한 알고리즘 문제를 풀다보면 시간제한이란 것이 항상 존재한다. 시간제한은 해당 문제의 풀수있는 알고리즘을 제한하기 위해서 존재한다. 이때 일반적으로 1초 = 1억번 계산한다라고 생각하면 될것. 이 시간과 주어진 문제의 입력조건의 최대값을 참고해서 알맞는 알고리즘을 도출해낼것. 예를 들어서 시간 제한: 2초, input값이 최대 10억일때. 무식하게 for문 2번 사용하는 짓은 절대로 문제가 안풀린다. (O(N^2)이기 때문에) 알고리즘의 복잡도는 O(N)도 부족하다, 적어도 O(NlogN)은 되어야지 해당 문제를 풀수가 있다. 요약) - 시간제한 1초는 대략 1억번이다. - 최대값 생각해서 알고리즘 잘 골라서 풀어라 2023. 5. 1. [알고리즘] 삽입 정렬(Insertion Sort) 다음과 같은 순서의 숫자 정렬들이 있을 때, 삽입 정렬의 정렬 방식은 다음과 같습니다. 숫자 배열: 8 3 2 4 9 8 3 2 4 9 -> 3 8 2 4 9 -> 3 2 8 4 9 -> 2 3 8 4 9 -> 2 3 4 8 9 삽입 정렬의 정렬 방식은 왼쪽 숫자와 오른쪽 숫자를 비교해서 크기가 역순이면 서로 바꾸게 됩니다. 위의 숫자로 설명하자면 처음 8과 3을 보게 됩니다. 8은 3보다 크기 때문에 8과 3의 위치를 바꾸게 됩니다. 이렇게 되면 3과 8은 두 숫자만 보게되면 크기 순서로 이미 정렬이 완료된 상태입니다! 그 다음은 세번째 자리의 숫자인 2를 보게 됩니다. 그리고 2의 왼쪽 자리인 8을 봅니다. 8이 2보다 큼으로 8과 2의 자리를 바꿉니다. 그럼으로 3 2 8 4 9 가 됩니다. 그러고.. 2022. 1. 6. [알고리즘] 버블 정렬(Bubble Sort) 다음과 같은 숫자들이 주어졌을 때 정렬과정은 밑과 같다. 숫자 배열 : 9 6 3 2 7 9 6 3 2 7 -> 6 9 3 2 7 -> 6 3 9 2 7 -> 6 3 2 9 7 -> 6 3 2 7 9 -> 3 6 2 7 9 -> 3 2 6 7 9 -> 2 3 6 7 9 버블 정렬의 시간 복잡도는 선택 정렬과 마찬가지로 O(N^2)이며 그렇게 효율적인 정렬 방법은 아니다. //bubble sort #include #include int main(){ clock_t start, end; double result; start = clock(); int N; std::cout > N; int* arr = new int[N]; std::cout > arr[i]; } char show_process; while(1.. 2022. 1. 6. [알고리즘] 선택 정렬(Selection Sort) 숫자 배열 7 3 2 1 4 가 있을 때 선택정렬의 진행순서는 아래와 같다. 1 3 2 7 4 -> 1 2 3 7 4 -> 1 2 3 4 7 아주 쉽게 설명하면 범위 안의 숫자 중 가장 작은 숫자를 맨 앞에 숫자와 바꾸고 범위를 하나씩 좁히는 식의 정렬 방법이다. 시간 복잡도는 O(N^2)임으로 굉장히 좋지 못하다. // Selection Sort #include #include int main(){ clock_t start, end; double result; start = clock(); int N; std::cout > N; int* arr = new int[N]; std::cout > arr[i]; } char show_process; while(1){ std::cout > show_process.. 2022. 1. 6. 이전 1 다음
