본문 바로가기

알고리즘

 (128)
[코드트리] 공간복잡도 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)의 시간복잡도를 보..
[PGS] Lv.0 (코딩테스트 입문) 9일차 문제 개미 군단 int solution(int hp) { int jang = hp / 5; hp -= 5 * jang; int byung = hp / 3; hp -= 3 * byung; int answer = hp + jang + byung; return answer; } 모스부호 (1) char MORSE_CODE[26][5] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."}; string solution(string letter) { string word = ""; ..
[PGS] Lv.0 (코딩테스트 입문) 8일차 문제 프로그래머스 C++ 배열 자르기 vector solution(vector numbers, int num1, int num2) { vector answer; for(num1; num199) { answer.push_back(alpha[age / 100]); age -= 100*(age/100); } if(tmp>9) answer.push_back(alpha[age / 10]); answer.push_back(alpha[age % 10]); return answer; } → 새로운 풀이 string answer = to_string(age); for(auto& v : answer) v += 'a'-'0'; return answer; // for(반복될 지역변수 : 배열) -> 지역변수가 배열 길이만큼 반복됨..
[PGS] Lv.0 (코딩테스트 입문) 7일차 문제 프로그래머스 C++ 특정 문자 제거하기 string solution(string my_string, string letter) { string answer = ""; answer = regex_replace(my_string, regex(letter), ""); return answer; } 각도기 int solution(int angle) { if(angle==90) return 2; if(angle == 180) return 4; if(angle>0 && angle
[알고리즘] 정렬의 최적성 정렬의 최적성 앞에서 우리는 연속한 두 원소를 비교하는 방식으로 정렬하면, O(n2) 보다 좋은 시간 복잡도를 얻을 수 없다는 것을 보였다. 그 다음에 배운 정렬 방식인 퀵정렬, 병합정렬, 힙정렬 에서는 멀리 떨어진 두 원소를 비교하여 교환함으로써 이보다 빠른 시간 복잡도인 O(n log n) 시간을 얻을 수 있었다. 그렇다면 이제 우리가 다시 비슷한 질문을 해보자. O(n log n)보다 더 빠르게 정렬을 수행할 수 있겠는가? 정리. 두 원소를 비교하여 교환하는 방식으로는 O(n log n)보다 더 빠르게 정렬을 수행할 수 없다. 증명. 의사 결정 트리(decision tree)는 어떤 문제에 대해서 판단을 내리는 과정을 트리로 표현한 것이다. 루트는 문제를 풀기 위해서 처음 시작하는 지점이다. 루트를..
728x90

티스토리툴바