본문 바로가기

📝 알고리즘

(143)

[코드트리] 공간복잡도 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

[PGS] Lv.1 : 소수 만들기 https://school.programmers.co.kr/learn/courses/30/lessons/12977 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. nums의 각 원소는 1 이상..

이전 1 ··· 13 14 15 16 17 18 다음

728x90

티스토리툴바