공간복잡도 (5) 썸네일형 리스트형 [코드트리] 공간복잡도 SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. 프로그램의 소요시간 뿐만 아니라, 컴퓨터의 메모리가 한정되어 있으므로 공간복잡도도 중요합니다. 공간복잡도도 시간복잡도와 동일하게 점근적 표기법을 사용합니다. function example(n) set arr = [n][n] for i = 0 ... i < n for j = 0 ... j < n arr[i][j] = 1 공간복잡도 = '이 코드가 메모리를 얼마나 차지하고 있을까?' 위 코드에서 set arr = [n][n] 이외의 다른 코드는 메모리를 차지하고 있지 않기 때문에, 공간복잡도는 O(N^2) 입니다. 그렇다면 공간복잡도는 왜 필요할까요? 문제에서 메모리 제한이 80MB라는 식으로.. [코드트리] 반복문의 시간복잡도(2) SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. 반복문 시간복잡도 문제 중 어려웠던 문제입니다. (1) function solution(n, m) set sum = 0 set visited = [n][m] for i = 1 ... i [코드트리] 반복문의 시간복잡도(1) SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. function example(n) while 0 > n or n > 100 if n < 0 n++ else n-- return n 위 코드의 경우 n에 값에 따라 연산의 횟수가 달라질 수 밖에 없습니다. 사실, 시간복잡도는 일반적으로 최악을 기준으로 계산합니다. 우리가 시간복잡도를 계산하는 이유가 프로그램의 성능을 체크하기 위함이었죠? 당연히 입력값이 아주 크거나 시간이 오래 걸리는 데이터도 들어올 가능성이 존재하므로 최악의 경우를 고려하면 어떠한 상황에서도 프로그램의 성능이 뛰어난지 확인할 수 있을 것입니다. 이 점을 상기한 채로, 반복문의 시간복잡도에 대해 알아봅시다. for set .. [코드트리] 시간복잡도의 정의 SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. 프로그램의 효율성을 확인하려면? 먼저 연산이 몇 번 진행되었는지 계산하는 방법이 있습니다. 그러나 연산 횟수를 세는 것은 많은 시간이 걸리고, 코드가 복잡해진다면 매우 어려워집니다. 그래서 연산의 횟수를 점근적 표기법을 통해 추상적으로 표현한 것이 바로 시간복잡도 입니다. set a = 5 if a != 10 print('hello') print 같은 메서드를 O(1)이라고 가정한다면, 대입도 O(1)이고 print도 O(1)이니 if a != 10 만 정확하게 알면 될 것 입니다. 그러나 결국 단순히 두 값을 비교하는 연산을 수행하기 때문에, 결과적으로 조건문도 O(1)의 시간복잡도를 보.. [알고리즘] 알고리즘 개요 및 정의 알고리즘의 정의 : 어떤 입력에도 정확한 출력을 유한한 시간 안에 내는 프로그램 어떤 입력 : 문제의 난이도나, 입력의 크기에 상관없이 문제를 풀 수 있다. 정확한 출력 : 문제가 요구하는 조건을 만족한다. 정답이 요구하는 조건이 무엇인지 명시할 수 있다. 유한한 시간 : 무한루프에 빠지지 않고 납득할 수 있는 시간에 종료한다. ex) 100명의 학생들의 시험 점수 중 최댓값을 구하시오. 수학적 귀납법→ 정확성 : 자명하다. → 시간 : n명의 점수를 읽으면, n-1번 비교. → max(지금까지의 최댓값, i+1번째 학생의 점수) ex) 100명의 학생들의 시험 점수 중 최빈값을 구하시오. ex) 입력 : U={1,2, … , n} 중에서 특정한 수 하나만 빼고 무작위의 순서로 n-1개의 숫자가 한번에 .. 이전 1 다음
