안녕하세요, JM 입니다. 몇주간 미루던 에디토리얼 심심해서 씁니다 (시카고에서 꽤 많이 심심합니다.. 놀아주세영..) 평생 안쓰던 에디토리얼 이럴때만 쓴다능.. 스탱 ㅈㅅ..
SRM404 는 쉬운 거 같으면서도 별로 직관적이지 않은 250 과, 자료구조를 잘 써먹어야 하는 까다로운 500, 그리고 약간의 인사이트를 필요로 하는 950 으로 스무스하게 진행되었습니다. 많은 사람들이 세 문제를 모두 풀었고, 어쩌다 보니 950 을 레코드를 낸 제가 코딩 페이즈에서의 선두를 그대로 유지하여 1등을 하게 되었습니다. ^ㅁ^ .. 라지만 몇주만에 올리는 에디토리얼이니 좀 창피하군요. ^^;;
250 - RevealTriangle
250 은 비교적 설명 자체는 간단하고, 예제만 봐도 이해할 수 있을 정도입니다. 해법은 어떻게 될까요? 물론 크기가 50인 삼각형을 백트래킹으로 해결하긴 힘드니(..) 다른 방법을 써야겠죠. 맨 아래 두 줄을 보면, 다음과 같은 형태일 겁니다:
8 ?
7
? 에 들어간 숫자가 무엇인지를 알기란 별로 어렵지 않죠. 바로 9 입니다. 이렇게, (a + b) % 10 == c 라는 관계에서 a 와 c 가 주어질 때 b 는 유일하게 정의됩니다. 이를 이용해, 아래에서부터 ? 들을 모두 지우며 올라올 수 있습니다. 예를 들어, 마지막에서 세 번째 줄까지가 다음과 같다면
x y 7
8 9
7
y + 7 == 9 에서 y = 2, x + y = 8 에서 x = 6 이란 것을 알 수 있지요. 이런 식으로 밑에서부터 ? 를 없애가며 올라오면 됩니다. 구현은 어떻게 하거나 여러분의 자유~ ^^ 고요, 레코드인 bmerry 씨는 다음과 같이 작성했군요:
class RevealTriangle
{
vector calcTriangle(vector qm)
{
int N = SZ(qm);
for (int i = N - 2; i >= 0; i--)
{
int p = 0;
while (qm[i][p] == '?')
p++;
for (int j = p + 1; i + j < N; j++)
qm[i][j] = (qm[i + 1][j - 1] - qm[i][j - 1] + 10) % 10 + '0';
for (int j = p - 1; j >= 0; j--)
qm[i][j] = (qm[i + 1][j] - qm[i][j + 1] + 10) % 10 + '0';
}
return qm;
}
};
500 - KSubstring
문제를 간략하게 정의하면 다음과 같습니다: 길이가 3000 이하인 non-negative 정수의 나열 A 가 주어질 때, 길이가 같고, 겹치지 않는 두 구간 중에 각 구간의 합이 최소인 것을 찾고 싶습니다. 예를 들어 A 와 두 구간이 다음과 같을 때
1 [7 4] 9 [2 3]
두 구간합의 차이는 |(7+4)-(2+3)| = 6 입니다. 구간합의 최소 차이 val 을 구하고, val 을 만들 수 있는 최대 구간 길이 maxK 를 구하세요.
이 문제에는 크게 두 가지 해법이 있는데, 출제자가 예상한 고상하고 우아한 해법이 있고, 실제 대회에서 모두가 사용한 방법이 있습니다. 전자는 설명하기도 쉽고 깔끔하지만, 영리한 직관이 필요합니다. 후자는 약간 더 복잡하고 귀찮지만 큰 직관의 도약 없이도 만들 수 있죠. 여기서는 후자의 해법을 설명하겠습니다.
후자의 해법은 일단 가장 간단하고 무식한 해법에서 출발한 뒤, 이것을 간단한 자료 구조를 이용해 최적화함으로써 얻을 수 있습니다.
일단, 우리는 K 를 1부터 N/2 까지 변화시켜 가면서 (N/2 보다 큰 K 값은 의미가 없습니다. 왜 그럴까요?) 각 경우에 대한 답을 찾은 뒤, 그 중 가장 좋은 것을 고른다고 가정합시다. 왜냐? 그게 제일 쉬우니까요. (K=1 일 때의 답을 이용해 K=2 일 때의 답을 찾을 수 있다면 참 좋겠지만 ㅎㅎ)
K 가 고정되었다면 가장 간단한 방법은 무얼까요? 물론, 길이가 K 인 모든 구간들의 모든 쌍에 대해 각각의 구간합의 차이를 비교하는 것이겠지요. 다음과 같이요.
for(int k = 1; k <= n/2; ++k)
for(int i = 0; i <= n-2*k; ++i)
for(int j = i+k; j <= n-k; ++j)
{
cand = [i, i+k-1] 구간과 [j, j+k-1] 구간합의 차이;
ret = min(ret, cand);
}
이 알고리즘의 시간 복잡도는 O(N^3) 에 육박하게 되겠지요. 물론 정확하게 말하자면 그것보다 몇 배 정도 적긴 하겠지만, N=3000 인 이 문제에서 쓸 수 있을 만한 알고리즘은 아닙니다. (직접 짜서 시도해 볼 수 있겠지요)
어떻게 하면 이 코드를 좀 더 빠르게 할 수 있을까요? 우리는 모든 쌍 간의 차이를 구하고 싶은 것이 아니라, 합 중 가장 차이가 적은 것만을 찾는다는 것을 생각하면, std::set 을 이용해서 이 문제를 풀 수 있습니다.
이를 위해서는 자신이 사용하는 언어의 자료 구조에 대해 좀 더 잘 알 필요가 있죠. 한국에서는 대부분의 참가자들이 C++ 을 쓰시니 (^^;) C++ 기준으로 설명하겠습니다. STL 의 set 은 내부적으로 균형 이진 검색 트리를 이용해 자료를 저장합니다. 때문에 자료들이 대소순서에 맞춰 정렬되어 내부에 저장되지요. 이를 이용해, set 은 lower_bound 와 upper_bound 라는 중요한 연산을 지원합니다.
lower_bound 멤버 함수는 주어진 값 x 가 순서에 맞춰 삽입될 수 있는 첫 번째 위치의 이터레이터를 반환합니다. upper_bound 멤버 함수는 삽입될 수 있는 마지막 위치를 반환하죠. 예를 들어, 어떤 정수 집합이 1 2 3 3 3 5 5 를 갖는다면, lower_bound(3) 은 첫 번째 3을 가리키는 이터레이터를 반환하고, upper_bound(3) 은 첫 번째 5 를 가리키는 이터레이터를 반환합니다. lower_bound(4) 와 upper_bound(4) 는 둘 다 모두 첫 번째 5를 가리키죠.
이를 이용하면, 다음과 같이 쉽게 문제를 해결할 수 있습니다. [k, 2*k-1] 에 있는 구간부터 시작해 오른쪽으로 구간을 한 칸씩 움직여 가며 이 구간 왼쪽에 있는 구간 중 해당 구간합과 가장 가까운 구간합을 찾는 거죠. 가장 가까운 구간합을 찾는 것은 아래와 같이 set 의 lower_bound 연산으로 할 수 있습니다.
for(int k = 1; k <= n/2; ++k)
{
// sum_a = [0,k-1] 구간합 sum_b = [k,k*2-1] 구간합
int sum_a = 0, sum_b = 0;
for(int i = 0; i < k; ++i)
{
sum_a += A[i];
sum_b += A[i+k];
}
// Loop invariant: sums_left 는 i 왼쪽에 있는
// (겹치지 않는) 구간들의 합을 저장
set sums_left;
for(int i = k; i < n-k+1; ++i)
{
sums_left.insert(sum_a);
// sums_left.lower_bound 를 이용해 sums_left 에
// 들어 있는 숫자 중 sum_b 와 가장 가까운 것을 찾는다
sum_a = sum_a - A[i-k] + A[i];
sum_b = sum_b - A[i] + A[i+k];
}
}
생략되어 있는 부분은 독자를 위한 숙제입니다. ^^;
1000 - SoftwareCompanies
JongMan
안녕하세요, JM 입니다. 몇주간 미루던 에디토리얼 심심해서 씁니다 (시카고에서 꽤 많이 심심합니다.. 놀아주세영..) 평생 안쓰던 에디토리얼 이럴때만 쓴다능.. 스탱 ㅈㅅ..
SRM404 는 쉬운 거 같으면서도 별로 직관적이지 않은 250 과, 자료구조를 잘 써먹어야 하는 까다로운 500, 그리고 약간의 인사이트를 필요로 하는 950 으로 스무스하게 진행되었습니다. 많은 사람들이 세 문제를 모두 풀었고, 어쩌다 보니 950 을 레코드를 낸 제가 코딩 페이즈에서의 선두를 그대로 유지하여 1등을 하게 되었습니다. ^ㅁ^ .. 라지만 몇주만에 올리는 에디토리얼이니 좀 창피하군요. ^^;;
250 - RevealTriangle
250 은 비교적 설명 자체는 간단하고, 예제만 봐도 이해할 수 있을 정도입니다. 해법은 어떻게 될까요? 물론 크기가 50인 삼각형을 백트래킹으로 해결하긴 힘드니(..) 다른 방법을 써야겠죠. 맨 아래 두 줄을 보면, 다음과 같은 형태일 겁니다: calcTriangle(vector qm)
8 ?
7
? 에 들어간 숫자가 무엇인지를 알기란 별로 어렵지 않죠. 바로 9 입니다. 이렇게, (a + b) % 10 == c 라는 관계에서 a 와 c 가 주어질 때 b 는 유일하게 정의됩니다. 이를 이용해, 아래에서부터 ? 들을 모두 지우며 올라올 수 있습니다. 예를 들어, 마지막에서 세 번째 줄까지가 다음과 같다면
x y 7
8 9
7
y + 7 == 9 에서 y = 2, x + y = 8 에서 x = 6 이란 것을 알 수 있지요. 이런 식으로 밑에서부터 ? 를 없애가며 올라오면 됩니다. 구현은 어떻게 하거나 여러분의 자유~ ^^ 고요, 레코드인 bmerry 씨는 다음과 같이 작성했군요:
class RevealTriangle
{
vector
{
int N = SZ(qm);
for (int i = N - 2; i >= 0; i--)
{
int p = 0;
while (qm[i][p] == '?')
p++;
for (int j = p + 1; i + j < N; j++)
qm[i][j] = (qm[i + 1][j - 1] - qm[i][j - 1] + 10) % 10 + '0';
for (int j = p - 1; j >= 0; j--)
qm[i][j] = (qm[i + 1][j] - qm[i][j + 1] + 10) % 10 + '0';
}
return qm;
}
};
500 - KSubstring
문제를 간략하게 정의하면 다음과 같습니다: 길이가 3000 이하인 non-negative 정수의 나열 A 가 주어질 때, 길이가 같고, 겹치지 않는 두 구간 중에 각 구간의 합이 최소인 것을 찾고 싶습니다. 예를 들어 A 와 두 구간이 다음과 같을 때
sums_left;
1 [7 4] 9 [2 3]
두 구간합의 차이는 |(7+4)-(2+3)| = 6 입니다. 구간합의 최소 차이 val 을 구하고, val 을 만들 수 있는 최대 구간 길이 maxK 를 구하세요.
이 문제에는 크게 두 가지 해법이 있는데, 출제자가 예상한 고상하고 우아한 해법이 있고, 실제 대회에서 모두가 사용한 방법이 있습니다. 전자는 설명하기도 쉽고 깔끔하지만, 영리한 직관이 필요합니다. 후자는 약간 더 복잡하고 귀찮지만 큰 직관의 도약 없이도 만들 수 있죠. 여기서는 후자의 해법을 설명하겠습니다.
후자의 해법은 일단 가장 간단하고 무식한 해법에서 출발한 뒤, 이것을 간단한 자료 구조를 이용해 최적화함으로써 얻을 수 있습니다.
일단, 우리는 K 를 1부터 N/2 까지 변화시켜 가면서 (N/2 보다 큰 K 값은 의미가 없습니다. 왜 그럴까요?) 각 경우에 대한 답을 찾은 뒤, 그 중 가장 좋은 것을 고른다고 가정합시다. 왜냐? 그게 제일 쉬우니까요. (K=1 일 때의 답을 이용해 K=2 일 때의 답을 찾을 수 있다면 참 좋겠지만 ㅎㅎ)
K 가 고정되었다면 가장 간단한 방법은 무얼까요? 물론, 길이가 K 인 모든 구간들의 모든 쌍에 대해 각각의 구간합의 차이를 비교하는 것이겠지요. 다음과 같이요.
for(int k = 1; k <= n/2; ++k)
for(int i = 0; i <= n-2*k; ++i)
for(int j = i+k; j <= n-k; ++j)
{
cand = [i, i+k-1] 구간과 [j, j+k-1] 구간합의 차이;
ret = min(ret, cand);
}
이 알고리즘의 시간 복잡도는 O(N^3) 에 육박하게 되겠지요. 물론 정확하게 말하자면 그것보다 몇 배 정도 적긴 하겠지만, N=3000 인 이 문제에서 쓸 수 있을 만한 알고리즘은 아닙니다. (직접 짜서 시도해 볼 수 있겠지요)
어떻게 하면 이 코드를 좀 더 빠르게 할 수 있을까요? 우리는 모든 쌍 간의 차이를 구하고 싶은 것이 아니라, 합 중 가장 차이가 적은 것만을 찾는다는 것을 생각하면, std::set 을 이용해서 이 문제를 풀 수 있습니다.
이를 위해서는 자신이 사용하는 언어의 자료 구조에 대해 좀 더 잘 알 필요가 있죠. 한국에서는 대부분의 참가자들이 C++ 을 쓰시니 (^^;) C++ 기준으로 설명하겠습니다. STL 의 set 은 내부적으로 균형 이진 검색 트리를 이용해 자료를 저장합니다. 때문에 자료들이 대소순서에 맞춰 정렬되어 내부에 저장되지요. 이를 이용해, set 은 lower_bound 와 upper_bound 라는 중요한 연산을 지원합니다.
lower_bound 멤버 함수는 주어진 값 x 가 순서에 맞춰 삽입될 수 있는 첫 번째 위치의 이터레이터를 반환합니다. upper_bound 멤버 함수는 삽입될 수 있는 마지막 위치를 반환하죠. 예를 들어, 어떤 정수 집합이 1 2 3 3 3 5 5 를 갖는다면, lower_bound(3) 은 첫 번째 3을 가리키는 이터레이터를 반환하고, upper_bound(3) 은 첫 번째 5 를 가리키는 이터레이터를 반환합니다. lower_bound(4) 와 upper_bound(4) 는 둘 다 모두 첫 번째 5를 가리키죠.
이를 이용하면, 다음과 같이 쉽게 문제를 해결할 수 있습니다. [k, 2*k-1] 에 있는 구간부터 시작해 오른쪽으로 구간을 한 칸씩 움직여 가며 이 구간 왼쪽에 있는 구간 중 해당 구간합과 가장 가까운 구간합을 찾는 거죠. 가장 가까운 구간합을 찾는 것은 아래와 같이 set 의 lower_bound 연산으로 할 수 있습니다.
for(int k = 1; k <= n/2; ++k)
{
// sum_a = [0,k-1] 구간합 sum_b = [k,k*2-1] 구간합
int sum_a = 0, sum_b = 0;
for(int i = 0; i < k; ++i)
{
sum_a += A[i];
sum_b += A[i+k];
}
// Loop invariant: sums_left 는 i 왼쪽에 있는
// (겹치지 않는) 구간들의 합을 저장
set
for(int i = k; i < n-k+1; ++i)
{
sums_left.insert(sum_a);
// sums_left.lower_bound 를 이용해 sums_left 에
// 들어 있는 숫자 중 sum_b 와 가장 가까운 것을 찾는다
sum_a = sum_a - A[i-k] + A[i];
sum_b = sum_b - A[i] + A[i+k];
}
}
생략되어 있는 부분은 독자를 위한 숙제입니다. ^^;
1000 - SoftwareCompanies
16년 전