알고리즘 (401) 썸네일형 리스트형 7810 static int list[1000001]; //길이가 1,000,001 인 배열 static int __solution(int N, int max, int min) { if (N > N; memset(list, 0, sizeof(int) * 1000001); for (int.. 7510 static queue q; static int solution(void) { int N, sum = 0, ret = 0, mid; cin >> N; mid = N / 2 + 1; for (int i = 1; i N) { while (sum > N && !q.empty()) { sum -= q.front(); q.pop(); } if (sum == N) ret += 1; } } while (!q.empty()) q.pop(); if (N > 1) ret += 1; return ret; } 어떤 수를 연속된 자연수의 합으로 표현 한다면 그 개수가 몇개인지를 구하는 문제이다. 예를들어, 47이 있으면 47 = 23 + 24로 표현 되고, 두수는 연속적이다는 것을 알 수 있다. 그래서 1 부터 차례대로 더해가.. 7991 inline static void __swap(int &t1, int &t2) { int temp = t1; t1 = t2; t2 = temp; } static void __solution(vector &list) { int len = list.size(); for (int i = 0; i = list[j]; j++); if (j < len) //그런 숫자가 있음, { __swap(list[i + 1], list[j]); } else //그런 경우가 없음. { __swap(list[i], list[i + 1]); for (int .. 7988 static string ans[] = { "Yes", "No" }; static int group[200]; static map table; static void set_graph(string& s1, string& s2, list * graph) { int p1, p2; map::iterator itr; if ((itr = table.find(s1)) == table.end()) { p1 = table.size(); table.insert(pair(s1, p1)); } else p1 = itr->second; if ((itr = table.find(s2)) == table.end()) { p2 = table.size(); table.insert(pair(s2, p2)); } else p2 = itr-.. 7985 queue qq[2]; static void clear_q(void) { while (!qq[0].empty()) qq[0].pop(); while (!qq[1].empty()) qq[1].pop(); } static void solution(void) { int K, n = 1, turn = 0; int * list; cin >> K; for (int i = 0; i < K; i++) n list[i]; qq[turn].push(pair(1, n - 1)); //초기 값 for (int level = 1; level 7964 static int solution(void) { int N, D, ret = 0, off = 0; cin >> N >> D; int * ternel = new int[N + 2]; ternel[0] = 1; ternel[N + 1] = 1; for (int i = 1; i > ternel[i]; for (int i = 0; i + D < N + 1; i += off) { for (off = 1; off D) { off = D; ret += 1; //차원 관문 설치 } } delete[] ternel; return ret; } 이 문제를 해결하기 위한 키 포인트 중 하나는 아래의 조건이었다. 모든 차원 관문 사이와 직접적으로 이동이 가능하도록 차원 관문을 재건하려고 한다. (단, 0번 위치와 N+1번 위.. 7965 문제에서 요구하는 수식을 구하기 위해서 아래와 같은 식을 세울 수 있다. f(n) = f(n-1) + n^n 여기서 재귀와 메모아이제이션이 생각났다. 이 방법이 __solution() 이다. 그러나 이 방법은 최대 백만번에 재귀 함수 호출로 인해 스택 오버플로우 문제가 발생하여 사용하지 못했다. 그래서 매모아이제이션을 유지하면서 재귀 대신 반복문으로 진행하였다. 여기서 단순한 방법으로 n^n을 구하면 아마 타임아웃 문제가 발생할 것 같아서 좀 더 효율적으로 n^n을 구해야 한다. 임의의 짝수는 2의 거듭제곱 들의 합으로 구성되며 홀수는 여기에 "1" 만 더한 것이다. 15 = 1 + 2 + 4 + 8 이므로 15^15 = 15^(1 + 2 + 4 + 8) = 15^1 * 15^2 * 15^4 * 15^8.. 7584 static int __solution(long long mid, long long off) { if (mid == off) return 0; else if (off > K; C = K; while (C != 1) //K보다 큰 2의 n승 중 최대값을 구함. { C >>= 1; mid 7732 static char * solution(void) { static char buf[16]; string s1, s2; int h[3], m[3], s[3]; cin >> s1 >> s2; h[0] = (s1[0] - '0') * 10 + (s1[1] - '0'); m[0] = (s1[3] - '0') * 10 + (s1[4] - '0'); s[0] = (s1[6] - '0') * 10 + (s1[7] - '0'); h[1] = (s2[0] - '0') * 10 + (s2[1] - '0'); m[1] = (s2[3] - '0') * 10 + (s2[4] - '0'); s[1] = (s2[6] - '0') * 10 + (s2[7] - '0'); if ((s[2] = s[1] - s[0]) < 0) { s[.. 7853 abcd를 입력한다 했을 때 나올 수 있는 유형은 2 * 3 * 3 * 2 = 36이다. 해당 위치에 문자 양 옆을 보고 그 위치에 올 수 있는 문자의 개수가 정해지는 것이다. a 의 경우는 옆에 b 만 있으므로 a 또는 b 가 올 수 있어서 총 2가지가 있고, b 의 경우는 옆에 a와 c가 있으므로 a, b 또는 c가 올 수 있어서 총 3가지가 있다. 이런 식으로 곱사건을 구하는 것이다. 처음과 끝은 스페셜 케이스로 처리하였다. 문자 두개만 비교하면 되기 때문이다. 3개의 문자를 비교해야 하는 경우는 주석을 참고하면 된다. 반복문안에서 ret 을 1 000 000 007 을 나눈 나머지로 다시 초기화 하는 것을 생각하지 못해서 여러번 fail이 떴었다. 사실 처음에는 전체 결과에서 10억 7을 나눈 나.. 이전 1 ··· 36 37 38 39 40 41 다음