pinevienna blog

규칙을 찾기 위해 손으로 하나하나 적어봤다 ​ N=1 - 1 N=2 - 00,11 N=3 - 001, 100, 111 N=4 - 0000, 0011, 1100, 1001, 1111 N=5 - 00001, 10000, 00111, 11100, 10011, 11001, 11111 · · · ​ 쭉쭉 하다보면 f(n) = f(n-1) + f(n-2)의 점화식을 세울 수 있다 (n>2) 123456789101112131415161718192021#include using namespace std; int n;unsigned long long arr[1000001] = { 0,1,2 }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; if (n

지만 신나는 함수 여행... 이걸 그대로 구현하면 시간이 오래 걸리니 줄이라고 한다..내가 줄이니 지는 신나겠지 시간을 줄이려면 과정을 줄여야한다 이미 계산된 값을 다시 계산하기 않기 위해 이전에 계산한 값을 저장해두는 메모이제이션이 동적 계획법이 핵심이란걸 알고 나면 쉽다 (나는 몰랐다) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include using namespace std; int dp[21][21][21] = { 0, }; //(0 = 20) int w(int a, int b, int c) { if (a 20) return w(20, 20, 20); if (dp[a][b][c] > 0)..

피보나치 함수를 호출했을 때 0과 1을 각각 몇 번 호출하는지 출력하는 문제다 ​ 처음엔 시간제한이 있는 줄 모르고 신나게 위 함수에서 printf를 지우고 0과 1을 return 할 때마다 만들어둔 변수에 +1 해준 뒤 최종 return시 그 변수의 값을 출력하는 형태로 짰다 결과는 나오지만 당연히 시간초과... ​ 규칙부터 찾아야 할 것 같다 ​0부터 차례대로 입력해 보면 결과가 피보나치 수열 그 자체임을 알 수 있다 (?) 0이 호출된 횟수는 N-1번째 피보나치 수, 1이 호출된 횟수는 N번째 피보나치 수다 (N!=0) 이제 코딩은 더 쉽다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using names..

능력치를 팀별로 합한 뒤 두 팀의 능력치를 비교한다 재밌는 축구를 위해 모든 경우의 수를 따져 두 팀의 능력치 차이가 가장 적은 경우를 찾아야 한다 ​ 핵심은 (1) 팀을 이룰 수 있는 모든 경우 (코드에서 dfs 함수) (2) 팀 능력치 구하고 비교 (코드에서 update 함수) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include using namespace std; int n, arr[20][20]; int team1[10], team2[10]; in..

삼성 SW 역량 테스트 기출문제로 나왔었던 문제 연산자와 피연산자를 입력받고 연산자 순서를 바꿔가며 계산한 뒤 최솟값과 최댓값을 찾는 문제 ​ 중요한 건 연산자 우선순위를 무시해도 된다는 점 → 하나씩 계산하면 된다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include using namespace std; int t, n[11], oper[4] = { 0, }; int min_num = 1000000000, max_num = -1000000000; void func(int id..