알고리즘 시간초과3 [삼성역량테스트] 16236 아기 상어 풀이일시 : 2021-04-22 문제 : N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다. 더 이상 먹을 수 있는 물고.. 2021. 4. 23. [개념정리] Big - O 시간복잡도 표기 알고리즘 문제를 풀면서 언젠간 한 번쯤 마주할 시간초과를 계산해내기 위한 Big-O 표기법이다. 시간복잡도란 실행시간으로 알고리즘의 효율을 측정한다. 연산 Step 의 수 ex 1부터 N 까지 더할 때 int summ(){ int result = 0; for(int i=1; i O(n^2) T(n) = n^4 + n^3 + n^2 + 1 => O(n^4) T(n) = 5n^3 + 10n^2 => O(n^3) Big-O 표기법의 종류 1 log n n n log n n^2 n^3 2^n O(1) : - 데이터의 양과 상관없이 일정한 실행시간을 가진다 - 상수그래프의 모양을 그린다. O(log n) : - 위와 같은 그래프의 모양을 보인다. - 따라서 데이터양이 많아져도 시간이 조금씩 늘어난다. - bina.. 2021. 3. 13. [백준문제풀이] 1208 부분수열의 합 2 풀이일시 : 2020-12-26 문제 : N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 : 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. ex) 5 0 -7 -3 -2 5 8 출력 : 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 풀이 : 1182번 문제에서 업그레이드 된 문제이다. 시간제한 2->1초 N의 갯수 20->40 연속된 수열을 찾는다 하면 경우의 수가 크지 않겠지만 연속된 수열이라는 말이 언.. 2021. 1. 4. 이전 1 다음 반응형
