시간복잡도11 [코드트리] 반복문의 시간복잡도(1) SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. function example(n) while 0 > n or n > 100 if n < 0 n++ else n-- return n 위 코드의 경우 n에 값에 따라 연산의 횟수가 달라질 수 밖에 없습니다. 사실, 시간복잡도는 일반적으로 최악을 기준으로 계산합니다. 우리가 시간복잡도를 계산하는 이유가 프로그램의 성능을 체크하기 위함이었죠? 당연히 입력값이 아주 크거나 시간이 오래 걸리는 데이터도 들어올 가능성이 존재하므로 최악의 경우를 고려하면 어떠한 상황에서도 프로그램의 성능이 뛰어난지 확인할 수 있을 것입니다. 이 점을 상기한 채로, 반복문의 시간복잡도에 대해 알아봅시다. for set .. 2023. 2. 6. [코드트리] 시간복잡도의 정의 SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. 프로그램의 효율성을 확인하려면? 먼저 연산이 몇 번 진행되었는지 계산하는 방법이 있습니다. 그러나 연산 횟수를 세는 것은 많은 시간이 걸리고, 코드가 복잡해진다면 매우 어려워집니다. 그래서 연산의 횟수를 점근적 표기법을 통해 추상적으로 표현한 것이 바로 시간복잡도 입니다. set a = 5 if a != 10 print('hello') print 같은 메서드를 O(1)이라고 가정한다면, 대입도 O(1)이고 print도 O(1)이니 if a != 10 만 정확하게 알면 될 것 입니다. 그러나 결국 단순히 두 값을 비교하는 연산을 수행하기 때문에, 결과적으로 조건문도 O(1)의 시간복잡도를 보.. 2023. 2. 6. [알고리즘] 정렬의 최적성 정렬의 최적성 앞에서 우리는 연속한 두 원소를 비교하는 방식으로 정렬하면, O(n2) 보다 좋은 시간 복잡도를 얻을 수 없다는 것을 보였다. 그 다음에 배운 정렬 방식인 퀵정렬, 병합정렬, 힙정렬 에서는 멀리 떨어진 두 원소를 비교하여 교환함으로써 이보다 빠른 시간 복잡도인 O(n log n) 시간을 얻을 수 있었다. 그렇다면 이제 우리가 다시 비슷한 질문을 해보자. O(n log n)보다 더 빠르게 정렬을 수행할 수 있겠는가? 정리. 두 원소를 비교하여 교환하는 방식으로는 O(n log n)보다 더 빠르게 정렬을 수행할 수 없다. 증명. 의사 결정 트리(decision tree)는 어떤 문제에 대해서 판단을 내리는 과정을 트리로 표현한 것이다. 루트는 문제를 풀기 위해서 처음 시작하는 지점이다. 루트를.. 2023. 1. 16. [알고리즘] 비교 기반 정렬 문제 정렬 문제→ 여러 방법이 존재하며, 방법마다 특징이 다름 → 시간복잡도, 최적성에 대해 증명이 쉬움 → n개의 서로 다른 수가 주어질 떄, 이들을 이동하여 점점 커지게(오름차순) 또는 점점 작아지게(내림차순)으로 만드는 문제 가정 : 정렬한 데이터가 담긴 배열의 각 원소를 O(1)시간에 접근 가능하다. (= 데이터가 메인 메모리에 저장되어 있다.) 버블 정렬 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해가면서, 큰 수가 오른쪽으로 가도록 교환함. 맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해서 반복 정확성 : 자명함 시간 복잡도 : 처음 가장 큰 원소를 구할 때 n-1번 비교, 두 번째 큰 원소를 구할 때 n-2번 비교 (n-1) + (n-2) + … + 1 =.. 2023. 1. 16. [알고리즘] 알고리즘 개요 및 정의 알고리즘의 정의 : 어떤 입력에도 정확한 출력을 유한한 시간 안에 내는 프로그램 어떤 입력 : 문제의 난이도나, 입력의 크기에 상관없이 문제를 풀 수 있다. 정확한 출력 : 문제가 요구하는 조건을 만족한다. 정답이 요구하는 조건이 무엇인지 명시할 수 있다. 유한한 시간 : 무한루프에 빠지지 않고 납득할 수 있는 시간에 종료한다. ex) 100명의 학생들의 시험 점수 중 최댓값을 구하시오. 수학적 귀납법→ 정확성 : 자명하다. → 시간 : n명의 점수를 읽으면, n-1번 비교. → max(지금까지의 최댓값, i+1번째 학생의 점수) ex) 100명의 학생들의 시험 점수 중 최빈값을 구하시오. ex) 입력 : U={1,2, … , n} 중에서 특정한 수 하나만 빼고 무작위의 순서로 n-1개의 숫자가 한번에 .. 2023. 1. 16. 이전 1 2 다음 728x90 반응형
