본문 바로가기

전체 글

 (105)
1929번: 소수 구하기 알고리즘 분류를 보기 전까지 한참 해맸다. 시간초과를 해결하는 게 관건인데 에라토스테네스의 체를 이용해 해결할 수 있다. #include int check[1000001] = { 0 }; int main(void) { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int min, max; std::cin >> min >> max; check[1] = 1; for (int i = 2; i
1759번: 암호 만들기 가볍게 풀 수 있는 문제 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 #include #include #include #include #include int main(void) { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int len, N; std::cin >> len >> N; std::vector alphabet(N); for (int i = 0; i > alphabet[i]; } std::vector t..
1525번: 퍼즐 퍼즐을 풀어서 1차원 형태의 문자열을 사용해 문제를 해결했다. 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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 #include #include #include #include #include typedef struct { int y, x; } dif; dif dir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; in..
1208번: 부분수열의 합2 상당히 어려웠던 문제다. 1182 부분수열의 합에서 확장된 버전인데 속도가 관건이다. 개수의 범위가 40까지이므로 한번의 재귀 호출로는 해결이 불가능해보인다. 나는 입력 받은 배열을 앞과 뒤, 둘로 나눠 계산을 진행했다. (int형으로는 모든 케이스를 커버하지 못한다) 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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 #include #include #include int len, resu..
1182번: 부분수열의 합 문제를 풀다보면 사고력이 많이 부족하단 걸 느낀다. 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 #include #include void DFS(std::vector val, int len, int cur, int sum, int result, int *count) { if (cur == len) { if (sum == result) { *count += 1; } return; } DFS(val, len, cur + 1, sum + val[cur], result, count); DFS(val, len, cur + 1, sum, result, count); } int main(vo..
1168번: 요세푸스 문제2 혼자 힘으로 풀지 못했다. 퍼포먼스를 만족키지 못했는데 다른 사람들의 풀이를 참조해서 vector의 erase를 사용하면 된다는 걸 알았다. (erase는 memmove로 구현해서 매우, 매우 빠르다고 한다) 하지만 이 문제는 세그먼트 트리를 사용하라는 목적으로 만든 것 같다. 세그먼트 트리를 알아보자... #include #include int main(void) { int len, term; std::cin >> len >> term; std::vector arr(len); for (int i = 0; i
1167번: 트리의 지름 시작점을 어디로 잡아도 상관없다. 선택한 시작점에서 가장 깊은 곳을 찾아낸 후 그곳에서 최대 지름을 구한다. (처음 주어진 시작점이 가장 깊은 곳이 아닐수도 있다는 것에 숙지하고 있어야한다) #include #include #include #include #include std::vector val[100001]; bool check[100001] = { false }; int max = 0, final = 0; void BFS(int pos) { std::queue mQueue; mQueue.push({ pos, 0 }); check[pos] = true; while (!mQueue.empty()) { int front = mQueue.front().first; int count = mQueue.fro..
1149번: RGB거리 가장 익숙해지지 않는 dp문제 #include #include int main(void) { int len; std::cin >> len; int val[1001][3] = { 0 }; for (int i = 0; i val[i][j]; } } int store[3] = { 0 }; int red, green, blue; red = val[0][0]; green = val[0][1]; blue = val[0][2]; for (int i = 1; i store[2] ? store[2] : store[1]; val[i][1] += store[0] > store[2] ? store[2] : store[0]; val[i][2] += store[0] > store[1] ? store[1] : store[0]; }..

티스토리툴바