아인스트라세의 SW 블로그

https://www.acmicpc.net/problem/1002

백준저지 1002번 터렛 문제이다.

어떤 지점에서 길이가 같은 점들의 집합이 원이므로, 원 두개를 그린 뒤 그 두개의 원의 교점의 개수를 리턴하면 된다.

이는 두 원의 반지름과, 두 원의 중점 사이의 거리와의 관계를 따져서 값을 출력하면 된다.

두 원의 반지름을 r1, r2 (r1 <= r2)이라고 하고, 중점 사이의 거리를 d라고 하자.

소스코드에서는 floating point의 부정확함을 고려하여서 실제 나타난 거리의 제곱수인 정수를 이용하여 비교를 하였다. 따라서 sqrt(Square root)와 같은 함수는 따로 사용할 필요가 없다.

다음 케이스들을 고려해주면 된다.

1. 원이 두 점에서 만나는 경우

r2 - r1 < d < r1 + r2

2. 두 원이 외접하는 경우 (한점에서 만난다)

d = r1 + r2

3. 두 원이 내접하는 경우 (한점에서 만난다)

d = r2 - r1

and

d != 0

4. 하나의 원이 다른 원을 포함하는 경우 (만나지 않는다)

d < r2 - r1

5. 두 원이 멀리 떨어져 만나지 않는 경우

d > r1 + r2

6. 두 원이 일치하는 경우 (무수히 많은 점에서 만난다)

d = 0

r1 = r2

 

#include <iostream>

using namespace std;

typedef long long ll;

int main() {
    int t;
    cin >> t;
    while(t--) {
        ll x1, y1, r1, x2, y2, r2;
        cin >> x1 >> y1 >> r1 >>x2 >>y2 >> r2;
        ll dx = x1-x2;
        ll dy = y1-y2;

        if (r1 > r2) swap(r1, r2);
        ll add = r1 + r2;
        add = add * add;
        ll sub = r2 - r1;
        sub = sub * sub;
        ll d = dx*dx + dy*dy;
        
        if (d < add && d > sub) {
            cout << 2;
        } else if (d == add || (d == sub && d != 0) ) {
            cout << 1;
        } else if (d < sub || d > add) {
            cout << 0;
        } else if (d ==0) {
            if (r1 == r2)
                cout << -1;
            else
                cout << 0;
        }
        cout << '\n';
    }
    return 0;
    
}

팰린드롬인 부분수열 개수 구하기(Counting All Palindromic Subsequences) 알고리즘에 대하여 포스팅을 해 보도록 하겠습니다.

일단 각각의 정의에 대해서 한번 설명을 간단하게 해 보겠습니다.

팰린드롬(Palindrome)은 앞에서부터 읽으나, 뒤에서부터 읽으나 같은 내용인 단어를 뜻합니다. 예를들어 '토마토'라던지 '바밤바', 'level', 'racecar' 등등이 있겠죠.

부분수열(Subsequence)은 원래 수열이나 배열에서 순서는 그대로 두고 일부 원소를 제거한 수열을 뜻합니다. 예를들어 abcdefg 라는 수열(Sequence)가 있다고 할 떄 abc와 bcd 와 같은 녀석들도 부분수열이 되지만, adg와 같은 녀석도 부분수열이 됩니다. 하지만 순서가 바뀌는 cba 같은 녀석은 부분 수열이 안됩니다.

그러면 이제 어떠한 문자열(String)에 대하여 팰린드롬인 부분수열(Palindromic subsequence)의 개수를 세 보도록 하겠습니다. 

일단은 부분수열이 중복이라도, 위치가 다르면 다른 것으로 세는 경우부터 따져보도록 하겠습니다.

즉, 예시로 'aab'의 팰린드롬 부분수열은 { 'a', 'a', 'b', 'aa' }가 되며, 'a'가 2개이지만 문자열의 첫번째 원소와 두번째 원소로 각각 샌 경우입니다.

일단 이 문제에 대해서 풀이법을 스스로 한번 생각해보는 것을 추천한다고 합니다.

다음 GeeksforGeeks 포탈에서 문제를 한번 풀어볼 수 있습니다. 로그인이 필요하긴 합니다만 별도의 개발환경 설정 없이 문제를 풀어볼 수 있습니다.

http://practice.geeksforgeeks.org/problems/count-palindromic-subsequences/1

이 문제 답안의 특징을 살펴보면, 일단 길이가 1인 문자열에 대해서는 팰린드롬 부분수열이 무조건 1개입니다. 그 보다 긴 경우를 고려를 해야 하는데 부분문제로 나누어서 풀이할 수 있습니다. 즉 다이나믹 프로그래밍으로 해결을 할 수 있지요. 아래와 같은 recurrence가 나타납니다.

classic dynamic programming problem, which can be solved using the following recurrence:

• Let $P(L, R)$ be the number of palindromic subsequences in $S[L...R]$, then
• $P(L, R) = \begin{cases} 1 &\text{if } L = R \\P(L + 1, R) + P(L, R - 1) - P(L +1, R - 1) &\text{if } S(L) \neq S(R) \\ P(L + 1, R) + P(L, R - 1) + 1 &\text{if } S(L) = S(R)\end{cases}$

< 출처: csacademy.com >

P(L,R)은 부분문자열 S[L...R]에서 나타나는 팰린드롬 부분수열이고, L과 R은 부분문자열의 시작과 끝 인덱스 번호입니다. L=R인 경우는 길이가 1인 부분 문자열입니다.

S(L) != S(R)인 경우는 왼쪽에서 범위가 1만큼 줄어든 P(L+1, R)과 오른쪽에서 범위가 1만큼 줄어든 P(L, R-1)의 개수를 더한 뒤, 중복으로 더해진 P(L+1, R-1)를 빼 줍니다. P(L+1, R)와 P(L, R-1) 둘 다 P(L+1, R-1)의 범위에서 나타난 정답값을 중복으로 포함하기 때문에 빼 준 것이죠.

S(L) = S(R)의 경우에는 위 경우와 달리 중복으로 더해준 P(L+1, R-1)을 빼지 않고 또 1을 더해줍니다. 

 { P(L+1, R-1)에 해당하는  개수 } = { P(L+1, R-1) 부분수열의 양 끝에 S(L)과 S(R)을 붙인 새로운 팰린드롬 부분수열 개수 }

이기 때문이죠. 그리고 추가적으로 1을 더한 값은 S(L)과 S(R)로만 이루어진 길이가 2인 부분수열의 개수입니다.

이렇게 재귀적인 방법으로 문제를 풀 수 있으며, 재귀 트리를 그려보면 겹치는 부분문제들이 있으므로 이를 메모이제이션(memoization)한 다이나믹 프로그래밍을 이용하여 효율적으로 문제를 해결할 수 있습니다.

Top-Down 방식으로 작성한 DP 솔루션 코드입니다.

 
/*
Please note that it's Function problem i.e.
you need to write your solution in the form of Function(s) only.
Driver Code to call/invoke your function would be added by GfG's Online Judge.*/
int** cps;

int get(int start, int end, string& str);
/*You are required to complete below method */
int countPS(string str)
{
    int ans;
    int len = str.length();
    cps = (int**) calloc(sizeof(int*) , (len+1));
    for (int i=0; i < len+1; i++) {
        cps[i] = (int*) calloc(sizeof(int), (len+1));
    }
    
    
    ans = get(0, len-1, str);
    //free allocated memory
    for(int i=0; i <len+1; i++) {
        free(cps[i]);
    }
    free(cps);
    return ans;
   //Your code here
}

int get(int start, int end, string& str) {
    if (start > end) return 0;
    if (start == end) return 1;
    if (cps[start][end]) return cps[start][end];
    
    if (str[start] == str[end]) {
        cps[start][end] = get(start, end-1, str) + get(start+1, end, str) + 1;
    } else {
        cps[start][end] = get(start, end-1, str) + get(start+1, end, str) - get(start+1, end-1, str);
    }
    return cps[start][end];
}
 

그리고 이제 중복을 허용하지 않는 팰린드롬 부분수열의 개수를 세는 경우를 따져보도록 하겠습니다.

앞선  예시에서 'aab'의 팰린드롬 부분수열은 중복을 허용하는 경우{ 'a', 'a', 'b', 'aa' }가 되며, 중복을 허용하지 않는 경우는 { 'a', 'b', 'aa' } 가 됩니다.

중복을 허용하지 않는 경우 중복을 허용하는 경우 보다 조금 더 까다로운데, dynamic programming의 점화식의 인자가 2개에서 3개로 늘어나게 됩니다. 3번째 인자는 가장 바깥에 감싸고 있는 알파뱃을 나타내는 시그마입니다.

• Let $DP(L, R, \sigma)$ be the number of distinct palindromic subsequences in $S[L..R]$ which are bordered with $\sigma$.
• $DP(L, R, \sigma) = \begin{cases} 0 &\text{if } L > R \\ 1 &\text{if } L = R \ \text{and} \ S(L) = \sigma \\DP(L + 1, R, \sigma) + DP(L, R - 1, \sigma) - DP(L +1, R - 1, \sigma) &\text{if } S(L) \neq \sigma \ \text{or} \ S(R) \neq \sigma \\ 2 + \sum_{\theta \in \{a, b, .., z\}} DP(L + 1, R - 1, \theta) &\text{if } S(L) = S(R) = \sigma \end{cases}$

S(L)=S(R)=sigma 의 경우는 DP(L+1, R-1, *)를 모두 더하는데, 원래 있던 각각의 부분수열들의 가장 바깥에 σ 글자로 패딩을 입힌 글자들을 셉니다. 그리고 더해주는 2의 경우는 { 'σ' , 'σσ' }의 경우가 됩니다. 기존의 팰린드롬 문자열들은 σ 패딩을 입혔기 때문에 모두 길이가 3 이상이므로, 중복이 될 일은 없습니다.

그러면 약간 헷갈릴 수 있는 부분이, 글자가 σ가 아닌 길이가 1인 팰린드롬 문자열들의 경우는 어떻게 하냐고 할 수 있는데, 해당 항목들은 DP(L, R, σ)가 아닌 닌 곳에서 세고있기에 상관이 없습니다. 

예를 들어서 'aba' 문자열에 대하여 팰린드롬 부분수열은 다음과 같습니다.

{ a, b, aa, aba }

위 Recurrence를 적용해보면

DP(1, 3, a) = DP(2, 2, *) + 2

DP(2, 2, *) = { b }

입니다. 따라서 DP(2, 2, *)에 a로 패딩을 입힌 새로운 팰린드롬 부분수열 { aba } 과, +2에 해당하는 { a, aa }를 합집합 한 결과인 { a, aa, aba }가 DP(1, 3, a)에 해당되고, { b }는 DP(1, 3, b)에 포함됩니다.

따라서 DP(1,3,a) = { a, aa, aba } 이고 / DP(1,3,b) = { b } 이됩니다. 

따라서 글자가 σ가 아닌 길이가 1인 팰린드롬 문자열들의 경우는 DP(L, R, σ)에서 세고 있지 않기에 위의 의문은 해결이 되었습니다.

제가 해당 솔루션을 보고 이해가 가지 않은 부분들을 고심하면서 해결한 내용을 블로그에 포스팅 해 보았는데, 혹시나 궁금하신점이나 의견있으시면 댓글로 달아주시면 내용에 반영하도록 하겠습니다.

[참고]

http://www.geeksforgeeks.org/count-palindromic-subsequence-given-string/

https://csacademy.com/contest/round-57/task/distinct-palindromes/solution/

때는 몇일 전 이었습니다. 여느때 처럼 코드포스와 백준저지를 들락날락하며 새 문제를 풀거나 새 콘테스트가 열리는지 확인하고, 지난 못 푼 문제들 튜토리얼을 읽고 다시 풀어보고 하던 때였습니다. 모르는 사람에게 코드포스 쪽지가 와 있길래 읽어보니 다음과 같은 내용이었습니다.

새로운 온라인 저지 플랫폼인 CS Academy란 것이 있는데, 매 주 콘테스트 라운드를 연다고 합니다. 그리고 제가 코드포스에서 액티브한 유저라서 해당 사이트로 초대를 한다고 하네요..(머쓱) 아직 실력은 갈 길이 멀지만 열심히 한다고 생각해주니 고마웠습니다. 그리고 코드포스 계정과 연동도 가능하다고 하고, 이번주 토요일에 경기가 있으니 한번 참여해보라는 뭐 그런 내용이었습니다. 그래서 한번 방문해 보았습니다.

https://csacademy.com/

사이트 디자인은 마치 안드로이드 폰 UI와 비슷한 형태였습니다. 깔끔하면서도 만든지 얼마 안 된 것 같은 그런 UI이지만 뭐 편리한 기능들은 꽤 많고 다 잘 작동했습니다. 생각보다 공부하기 좋은 기능들이 많이 있는데, 일단 제가 가장 좋아하는 1주일 정도마다 열리는 Round가 있고, 꽤나 자주 열리는 Hourly가 있습니다. 아직 Round를 한번 참여해본 것 말고는 사용을 해 보지 않아서 자세한 이야기는 못 드리겠네요.

콘테스트 외에 주제별로 풀어볼 수 있는 Problem set 기능도 제공합니다. Tasks라고 표현을 하는것 같습니다.

일단 코드포스 보다는 역사가 짧긴 한 것 같습니다. 코드포스가 Contest 번호가 400번대를 넘어섰는데, CS Academy는 58번째 Round를 진행하고 있네요.

Contest Round 외에도 Lesson이라고 해서 주제별로 Computer Science 관련된 자료구조나 알고리즘에 대한 공부 자료들이 있습니다. 그 외에도 그래프나 기하학적인 도형들을 그리는 툴도 있네요. 

그리고 특이했던 것 중 하나가 Contest Round 방식이었습니다. 코드포스와 비슷하게 Division을 1과 2로 나누어서 수준별 차이를 두고, Rating 시스템도 있습니다.

특히나 인상 깊었던 Contest Round 화면입니다. 온라인에서 실시간으로 코딩을 할 수 있고, 컴파일 및 실행과 제출을 한번에 할 수 있습니다. 매번 코드포스에서 문제를 풀 때에는 구름 IDE를 켜서 했던 것에 비해 비교적 간편했습니다.

언어도 다양하게 지원을 합니다. 문제들은 쓸데없는 문장 없이 간결했습니다.

또 특히나 좋았던 점은 아직 사용자가 많지 않아서 그런 것 일수도 있지만 서버 상태가 매우 쾌적했다는 것입니다. 랙이나 시간 지연없이 잘 동작했고, 문제 제출 시 몇번째 Test Case까지 맞았는지와 각각의 실행시간과 메모리 사용량을 알려줍니다.

그리고 콘테스트가 끝나면 Chatting 방에서 해당 라운드에 참여했던 사람들과 이야기를 할 수 있습니다. 그리고 약 15분만 기다리면 튜토리얼(문제에 대한 해설)과 Rating 변동 사항도 알려줍니다.

이번에 처음으로 한번 참여해 보았지만 편리하고 좋은 경험이었습니다. 앞으로도 CS Academy에서 계속 공부를 해 볼 생각입니다.

해당 플랫폼에 대한 더 정갈한 정리는 추후 제가 이 플랫폼을 많이 이용해본 뒤에 올리도록 하겠습니다.