분류 전체보기 (191) 썸네일형 리스트형 이진 트리( BOJ 31966 ) 문제 : https://www.acmicpc.net/problem/31966 문제 파악하기이진 트리의 모습이 순차적으로 주어질 때, 모든 말단 노드의 순서쌍 (a, b)에 대한 f(a, b) 값의 합인 S(T)를 구하는 문제입니다. f(a, b)는 말단노드 a에서 b까지 모두 덮는데 필요한 노드 최솟값을 의미하며, 문제를 해결하기 위해서는 트리의 왼쪽 서브트리와 오른쪽 서브트리를 입력받을 때마다 f(a, b)의 합을 모두 구해서 출력하면 됩니다. 다만, 트리의 입력이 서브트리의 형태로 주어지기 때문에 개수가 입력 값이 증가할수록 노드의 개수가 기하급수적으로 증가하게 됩니다. 따라서, 이 문제를 해결하기 위해서는 트리의 모습을 모두 구하는 것이 아닌, 미리 구해놓은 값을 활용하는 동적 프로그래밍 기법이 필.. 두 배( BOJ 31963 ) 문제 : https://www.acmicpc.net/problem/31963 문제 파악하기 주어진 수열을 오름차순으로 만들기 위해 필요한 연산의 최소 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 2배 하는 연산 1가지이며, 최대 250,000개의 숫자로 구성된 수열이 제시됩니다. 문제 자체는 이해하기 어렵지 않지만 은근 생각할 사항이 많은 문제입니다. 맨 왼쪽 부터 오른쪽 방향으로 숫자들을 하나씩 오름차순으로 맞추는 기본 베이스는 유추하기 쉽습니다. 다만, 여기서 어떻게 해야 시간 초과에 걸리지 않으면서 모든 숫자들을 바꿀 수 있을지는 생각을 필요로 합니다. 여기서 중요한 키워드는 기록하기 입니다. 문제 해결하기이 문제를 효율적으로 해결하기 위해서는 사용할 수 있는 유일한 연산인 2배 연산에 초점을.. 개미( BOJ 2136 ) 문제 : https://www.acmicpc.net/problem/2136 2136번: 개미 길이가 L(2 ≤ L ≤ 1,000,000,000)인 막대기 위에 N(1 ≤ N ≤ 100,000)마리의 개미들이 서로 다른 위치에 살고 있다. 개미들은 크기가 매우 작기 때문에 이 문제에서는 개미가 크기가 없는 점이라고 생각 www.acmicpc.net 문제 파악하기 길이가 L인 막대기 위에 있는 N마리의 개미 중 가장 늦게 떨어지는 개미의 번호와 시간을 구하는 문제입니다. N마리의 개미는 왼쪽 또는 오른쪽 방향으로 움직이며 서로 만나면 반대 방향으로 이동합니다. 개미들이 부딪히는 모든 경우를 시뮬레이션하는 방법을 가장 먼저 떠올릴 수 있지만 개미가 많아질수록 구현도 어려워지고 시간 복잡도 역시 증가합니다. 그.. 유클리드 게임( BOJ 4342 ) 문제 : https://www.acmicpc.net/problem/4342 4342번: 유클리드 게임 유클리드 게임은 두 명이서 하는 게임이고, 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다. 이때, www.acmicpc.net 문제 파악하기 주어진 두 개의 자연수를 사용하여 유클리드 게임을 했을 때, 선공을 하는 사람(동혁)이 이기는지 후공을 하는 사람(동규)이 이기는지 확인하는 문제입니다. 두 사람은 항상 최적의 방법으로 게임을 한다는 설명을 통해 우리는 시작부터 승자와 패자가 결정되었다는 걸 확인할 수 있습니다. 그럼 두 개의 숫자를 가지고 누가 이기는지 어떻게 알 수 있을까요? 이는 유클리드 게임을 분석하.. 옥토끼는 통신교육을 풀어라( BOJ 17838 ) 문제 : https://www.acmicpc.net/problem/17383 17383번: 옥토끼는 통신교육을 풀어라!! 옥토끼가 이런 식으로 문제를 풀면 tncks0121은 옥토끼가 5, 10, 15, 20, 25, 30, 34분에 문제를 풀었으므로 최대 5분동안 휴식을 한 것으로 간주한다. www.acmicpc.net 문제 파악하기 옥토끼가 N개의 문제를 푸는데 필요한 시간 간격의 최댓값이 가장 작아지는 경우를 구하는 문제입니다. 옥토끼는 한 번에 2개의 문제를 풀 수 있으며, 선택한 문제는 끝까지 해결한다고 합니다. 입력된 예시(3 4 5 9 10 14 15)를 보면서 문제를 자세히 이해해보겠습니다. 만약 가장 단순하게 입력된 순서대로 문제를 선택해서 해결한다면 아래와 같은 결과가 나오게 됩니다. .. 트라이(Trie) 트라이 구조는 문자열을 처리하는 알고리즘으로, 여러 문자열을 트리 구조를 활용하여 빠르게 처리하는 자료 구조이다. 맵을 사용한 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 struct Node { map nxt; bool end; Node() { nxt.clear(); end = false; } void insert(char *val) { if(*val == '\0') end = true; else { if(!nxt[*val]) nxt[*val] = new Node(); nxt[*val]->insert(val+1); } } }; Colored by Color Scripter cs 포인터를 사용한 구현 기준 문제 : https://www.acmicpc.net/proble.. 게리멘더링( BOJ 28433 ) 문제 : https://www.acmicpc.net/problem/28433 28433번: 게리맨더링 길이 $N$인 수열 $A_1, A_2, \cdots, A_N$이 주어집니다. 이 수열을 원하는 개수의 연속된 구간으로 나누어서, 각 구간의 합을 계산합니다. 합이 양수인 구간의 개수가 합이 음수인 구간의 개수를 초과 www.acmicpc.net 문제 파악하기 합이 양수인 구간을 음수인 구간보다 많이 만들 수 있는지 판단하는 문제입니다. 각 테스트케이스마다 최대 200,000개의 숫자가 주어지기 때문에 단순히 모든 경우를 확인하는 전탐색 알고리즘보다 효율적인 알고리즘이 필요합니다. 다행히 문제를 잘 살펴보면 나름 규칙성을 찾을 수 있습니다. 그럼 어떤 규칙을 찾을 수 있을까요? 문제 해결하기 문제를 관찰.. 가우스 소거법 가우스 소거법은 연립 방정식의 해를 구하는 방법 중 하나로, O(N3) 알고리즘으로 쉽게 구현할 수 있다. 구현 기준 문제 : https://www.acmicpc.net/problem/22940 22940번: 선형 연립 방정식 하나 이상의 미지수에 대해 최고차항의 차수가 1을 넘지 않는 방정식을 선형 방정식이라 한다. 족, 다음과 같은 식을 의미한다. A1x1 + A2x2 + ... + Anxn = B 선형 연립 방정식이란 유한개의 선형 방 www.acmicpc.net 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 4.. 이전 1 2 3 4 ··· 24 다음