Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

G1sTagList

2016년 8월 27일 토요일

[자전거따라] 자전거 타고 계곡까지, 광릉 수목원.


무더운 여름도 이제 막바지에 달했네요.
서울 인근에 자전거를 타고 갈 수 있는 계곡이 있다는 소식을 듣고 가보기로 하였습니다.
오늘의 목적지는 한강과 왕숙천의 자전거길을 따라가다보면 도착하는 광릉수목원 입니다.


출발을 하기위해 일행과 함께 뚝섬유원지에서 만나기로 하였습니다.
맑은 하늘에 양때구름이 함께하는 날씨네요.


약간의 정비 후 출발.
한강을 따라 구리를 향해 갑니다.


구리시에 도착.
구리한강시민공원에는 유채꽃 축제가 끝나고 가을을 위한 코스모스들이 자라고 있네요.
구리에서는 한강을 벗어나 왕숙천을 따라 방향을 틉니다.


왕숙천은 처음가는 길인데, 여기도 자전거길이 잘 되어있네요.
처음가는 길이라 중간에 길을 잘못들어 한참을 다시 돌아오기도 했습니다. ㅎㅎ..


잠시 길을 잃었던 퇴계원을 지나니 드디어 광릉수목원이 있는 남양주 진전읍에 도착을 했네요.


계곡에서 내려오는 물에서 놀고 있는 아이들이 부럽기만 합니다.


어느덧 점심시간을 넘긴 시간.
점심을 해결하기 위해 진접읍 시내로 들어가 미리 봐둔 절구만두집을 찾아갑니다.


점심 메뉴는 만두 전골.



전골과 밑반찬이 푸짐하네요.


아.... 바보라서 행복합니다.... 더 이상은 못 먹겟어서 어쩔 수 없이 음식을 남겼네요.
마당 한쪽에는 토끼도 키우고 있군요.

배도 채웠겠다 다시 자전거에 오릅니다.
하천을 따라 오르니 이제 자전거길도 끈기고 하천은 물이 줄어 계곡이 되었네요.


계곡을 따라 숲가운데로 나있는 도로를 따라 자전거를 달립니다.



어느정도 숲을 오르니 광릉에 도착.
광릉은 조선 세조의 릉이라고 하네요.
잠시 내려 입장권이 필요한 릉까지는 오르지 못하고 앞에서 구경을 하고 나옵니다.



다시 자전거에 올라 조금만 올라가니 드디어 오늘의 목적지 광릉수목원에 도착을 합니다.
광릉수목원에는 1일 입장제한인원이 있어 입장하기 위해서는 예약 필요하다고 하네요.


수목원을 들어가지 못하는 것은 아쉽지만 오늘의 목적은 계곡과 산림을 즐기는 것인만큼 자전거를 틀어 왔던 길을 다시 내려갑니다.


확실히 도시 근처에 있는 만큼 계곡을 마음껏 즐길 수 있는곳이 많지는 않네요.
올라오면서 봐둔 계곡 앞에 상을 설치한 음식점으로 향합니다.


계곡 앞에 위치한 마루와 계곡에 발을 담그고 먹을 수 있는 테이블.


계곡 한가운데는 분수도 설치되어있네요.
분수에 살짝살짝 비치는 무지개를 사진에 담아 저장합니다.

점심을 먹은지 얼마안된 만큼 주 메뉴인 백숙이나 오리요리보다는 도토리묵에 막걸리를 주문합니다.


계곡과 분수 무지개를 배경으로 막걸리 한사발.
음주운전은 안되니 딱 한사발씩만 마신 후 계곡에 발을 담궈보기도 하며 휴식을 취합니다.

다시 돌아오는 길.


도시를 배경으로 파란하늘을 담은 하천의 모습. 파란색과 녹색, 흰색의 조화가 아름답네요.


해가 지기 시작하며, 하늘과 강이 모두 아름다운 금색으로 물들어 갑니다.

2016년 8월 23일 화요일

[Algospot] 정리 못하는 정리베


문제 정보


문제ID
JEONGLIBE
출제자
hyunhwan
출처
제1회 알고스팟 새싹 콘테스트
시간제한
10000ms
메모리제한
65536kb
분류
.

문제 설명

아래 주어진 4개의 패턴의 문자에서 (아티스트 명)과 (곡 제목)이 중복되는 것을 제외한 유니크한 숫자를 구하는 문제입니다.

  • (트랙 번호)_(아티스트 명)_(곡 제목).mp3
  • (트랙 번호). (아티스트 명) - (곡 제목).mp3
  • (아티스트 명) - (곡 제목).mp3
  • (아티스트 명)_(곡 제목).mp3

입력값은 다음과 같으며, 비교시 대소문자는 구분하지 않습니다.
(트랙 번호) : 0 ~ 9 숫자,
(아티스트 명), (곡 제목) : 공백, 숫자, 영문자, 괄호 '(', ')'

문제 풀이

패턴이 주어졌으므로 주어진 패턴으로 파싱해서 String 값을 비교하면 되는 간단한 문제입니다.

트랙번호가 있는 패턴이 있고 없는 패턴이 있으므로, 파싱은 뒤에서부터 하는게 좋을 것 같네요.

뒤에서부터 char 값을 비교하여 '-' 또는 '_' 가 나올 때까지가 곡 제목.
곡 제목의 구분기호 부터 '-', '_', '.' 가 나올 때까지가 아티스트 명이 됩니다.

Show Spoiler : 숨겨진 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 숨겨진 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다.Close Spoiler
문제를 푸는 방법은 여러가지가 있습니다.

제가 구현한 방식처럼 속도를 크게 신경쓰지 않는다면, 위와같이 파싱 후 하나의 패턴으로 만들어서 Set 에 넣은 후 최종 Set의 size를 구하는 식으로도 구할 수 있습니다.

또한 이진탐색트리로 정렬해 가며 직접 유니크한 수를 구할 수도 있을 것 같구요.

String 자체가 비교하기에는 시간이 오래걸리니 해쉬값을 구해서 비교를 해도 좋을 것입니다.

단, 해쉬를 구하는 연산은 속도가 빠르면서 중복이 잘 되지 않도록 고려해야 겠지요.
물론 문제가 무한정 많은 것은 아니기 때문에 쉽고 단순한 연산만으로도 중복이 일어날 확률이 크지는 않을 것 같네요.

지금은 간단히 Set에 String 을 넣는 방법으로 문제를 해결했지만 다음에는 좀 더 대폭 감소하는 것에 도전을 할까 합니다.
== 소스보기 ==

결과

#
458672
문제
JEONGLIBE
언어
cpp
길이
889B
수행시간
72ms
결과
정답
제출일
2016-08-23

2016년 8월 22일 월요일

[Algospot] S@iNT 그룹 권회장의 스타크래프트 대회


문제 정보


문제ID
STARCRAFT
출제자
Taeyoon_Lee
출처
RUN Programming Contest, Spring 2009
시간제한
2000ms
메모리제한
65536kb
분류
.

문제 설명

단판 P%의 승률이 2K-1 판 K선 승제 일 경우 우승 확률을 구하는 문제입니다.

문제 풀이

확률문제네요. 경우의 수나 순열 등...
2K-1 판 중 K 승할 확률, K+1 승할 확률, .... 2K-1 승할 확률를 모두 더하면 됩니다.

이런 문제는 순서를 반대로 생각하는게 식을 표현하기가 간단하죠.

2K-1 승할 확률이란. 단일경기 승리 확률의 2K-1 제곱으로 구할 수 있습니다.
2K-2 승할 확률이란, 단일경기 승리 확률의 2K-2 제곱 곱하기 단일경기 패배할 확률 * 해당 조합이 만들어 질 수 있는 경우의 수 로 구할 수가 있습니다.

조합은 아래 공식으로 구할 수 가 있습니다. (참고 블로그)


이제 위 내용들을 조합해서 식으로 나타내면 아래와 같습니다.



Show Spoiler : 숨겨진 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 숨겨진 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다.Close Spoiler

위에서 구한 식을 코딩으로 구현하기만 하면 문제가 해결 됩니다.
제곱은 pow 함수로 간단히 구할 수 있지만 조합은 for문을 사용해야하는 군요.
Σ 계산까지하면 이중 for문 즉, O(n²) 의 시간복잡도가 나옵니다.

이를 개선하기 위해서는 중복으로 사용할 수 있는 조합의 값을 선처리로 구해놓고 이를 재활용해 사용하면 O(n)의 시간복잡도로 문제를 해결할 수 있습니다.

== 소스보기 ==

여기서 한가지 더, 문제를 풀고나니 선승제라는 표현이 애매한 것이 있어 문제를 다시한번 풀어보았습니다.

제가 전개한 식은 중간에 승리를 했어도 2K-1 판까지 모두 끝냈을 경우를 기준으로 식을 풀고, 코딩을 하였는데요.

경기가 끝나지 않았어도 K승을 모두 끝내버린다면, 경기가 끝나는 경우도 있을 것 같네요.

즉, K 판 동안 K 승 한 경우. K+1 판 동안 K승 한 경우..... 2K-1 판 동안 K승한 경우를 구하였습니다.

식은 아래와 같습니다.


결과는.... 두 해결방법 모두 동일한 결과가 나오네요.
두 식을 비교해서 두 식이 같다는 것을 증명... 하고는 싶으나 제 전공은 수학이 아니므로 여기서 이만 정리하겠습니다.

== 소스보기 ==

첫번째 풀이 결과

#
458451
문제
STARCRAFT
언어
cpp
길이
483B
수행시간
3ms
결과
정답
제출일
2016-08-22

두번째 풀이 결과

#
459962
문제
STARCRAFT
언어
cpp
길이
504B
수행시간
4ms
결과
정답
제출일
2016-08-26

2016년 8월 11일 목요일

[Algospot] 눈치게임

문제 정보

문제ID
GAME
출제자
Yongrok
출처
RUN Programming Contest, Fall 2009
시간제한
5000ms
메모리제한
65536kb
분류
.

문제 설명

이번 문제에서 예시로 들고 있는 것은 바로 눈치 게임입니다.

N명의 참가자가 숫자 K가 끝인 눈치게임을 합니다.
각 참가자 i가 j번째 턴마다 마다 기다리는 시간 W(i,j)가 주어졌을 때, 게임에 진 사람들을 출력하는 문제입니다.

즉, j번째마다 가장 작은 W(i,j)값을 가진 i를 제외해가며, j번째의 W(i,j)가 동일한 i들 또는 k까지 갔을 때 남은 i번째 수를 출력해주는 문제입니다.

입력 조건은 아래와 같습니다.

1 ≤ K < N ≤ 500
0 ≤ W(i,j) ≤ 60
1 ≤ i ≤ N
1 ≤ j ≤ K

문제 풀이

크게 설명이 필요하지는 않은 문제로 보여지네요.
매 턴마다 가장 작은 W(i,j)를 가지고 있는 i를 구한 후 해당 i들은 다음 턴의 비교에서 제외해 주며 가장 작은 W(i,j)값을 비교해 나가면 됩니다.

즉, 해당 i가 제외되었는지를 확인할 배열을 두고, 루프를 돌며 최소값의 1개의 i를 찾으며, 최소값이 둘 이상 중복 될 경우 루프를 빠져나와 중복 된 i 또는 마지막 k까지 돌았을 때 남은 사용자를 출력해주면 됩니다.
== 소스보기 ==

결과

#
455377
문제
GAME
언어
cpp
길이
881B
수행시간
581ms
결과
정답
제출일
2016-08-11

2016년 8월 8일 월요일

[Algospot] 마력

문제 정보

문제ID
MAGICPOWER
출제자
mjy0503
출처
2013 KAIST 교내 대회
시간제한
10000ms
메모리제한
65536kb
분류
구현, 그리디

문제 설명

N개의 아이템, M개의 횟수가 주어졌을 때 아이템을 사용하여 얻을 수 있는 최대 마력의 양을 맞추는 문제입니다.
각 아이템은 한번에 얻을 수 있는 마력이 수로 표시 되며, 해당 수는 한번의 사용시 마다 1씩 줄어듭니다.

문제 풀이

매번 그 상황에 가장 큰 값을 가지고 있는 아이템을 선택해 나가면 문제를 해결할 수 있습니다.
즉, 아이템을 정렬한 후 가장 큰 값을 선택하고, 다시 정렬한다음 큰 값을 선택하는 식으로 문제를 해결해 나갈 수 있습니다.

Show Spoiler : 숨겨진 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 숨겨진 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다.Close Spoiler
여기서 조금만 더 생각을 하면, 매번 정렬할 필요가 없다는 것을 알 수 있습니다.

가장 큰 값을 가진 아이템을 1회 사용했을 경우 줄어드는 숫자는 1이므로, 해당 아이템은 가장 큰 값을 가지고 있거나 혹은 두번째로 숫자가 많은 아이템과 동률로 가장 큰 값을 가지고 있을 것입니다.

이를 이용해 처음 한번 정렬한 후에 가장 큰 값을 가지고 있던 아이템을 계속해서 공동 1위가 될 수 있도록 공동 1위들의 아이템들을 한꺼번에 더해줘가며 답을 찾으면 됩니다.

n=3, m=3 입력이 3, 2, 4인 예제를 예를 들어 보겠습니다.

Item비고
3 2 4초기 상태
4 3 2정렬
3 3 2마력 4인 아이템 1개 사용(마력:4*1=4)
2 2 2마력 3인 아이템 2개 사용(마력:3*2=6)

위와같이 1 ~ p 까지의 아이템이 공동 1위, 가장 큰 값을 가지고 있는 아이템들이라고 한다면,
앞으로 남은 사용 횟수 m이 p 보다 클 경우 p*item[p] 값을 더해준 후 m-p를 해가며 반복 후, m이 p 보다 작을 경우 마지막으로 m*item[p] 값을 더해주면 원하는 값을 구할 수 있습니다.

== 소스보기 ==

결과

#
454339
문제
MAGICPOWER
언어
cpp
길이
598B
수행시간
3ms
결과
정답
제출일
2016-08-08

2016년 8월 6일 토요일

[Algospot] 원주율 외우기

문제 정보


문제ID
PI
출제자
JongMan
출처
연습문제
시간제한
1000ms
메모리제한
65536kb
분류
동적계획법

문제 설명

숫자열이 주어졌을 때, 해당 숫자를 세자리에서 다섯자리까지의 조각들로 나누는 최적의 방법을 찾는 문제입니다.

이 때 나누어진 숫자들이 다음과 같은 패턴을 가질 경우 난이도가 부여되며, 난이도가 가장 적은 경우가 최적의 경우가 됩니다.

1. 모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1
2. 숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2
3. 두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4
4. 숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5
5. 그 외의 경우 난이도: 10

풀이 과정

모든 경우의 수를 고려하고, 이 중 최적의 경우를 구하는 문제입니다.
이와 같은 문제의 경우 동적계획법을 이용한 풀이가 가장 접합합니다.

동적 계획법은 문제를 풀기위해 하위문제로 나누어 푼다음 이를 결합하여 최종적으로 문제를 해결해 나가는 방법입니다.

이 때, 이미 해결한 하위문제를 재활용하는 방법으로 문제를 빠르게 해결할 수 있습니다.

동적계획법을 해결하는데도 역시 재귀함수를 많이 사용하지만 꼭 재귀함수를 사용할 필요는 없으며, 여기서도 재귀함수가 아닌 일반적인 반복문을 통하여 문제를 해결할 수 있습니다.

Show Spoiler : 숨겨진 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 숨겨진 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다.Close Spoiler

먼저 문제를 해결하기 위한 경우의 수를 고려합니다.
여기서 고려해야하는 경우의 수는 기본적으로 숫자를 3자리, 4자리, 5자리로 끊는 것입니다.

수가 길어짐에 따라 이 3가지를 다양하게 사용한 많은 경우의 수가 나오지만, 어떻든 처음 혹은 끝을 보면 저 3가지 경우 중에 하나로 끝나게 됩니다.

그럼 이번 문제를 해결하기 위해 가장 마지막을 채우는 것부터 문제를 작게 쪼개서 나가도록 합니다.

예를 들어 N자리로 이루어진 숫자 열이 주어졌다고 가정을 합니다. 이를 구하는 가장 최적의 수는 다음 3가지 중에 하나로 구해질 수 있습니다.

마지막을 3자리로 했을 때의 난이도 + N-3 자리 까지 최적의 난이도.
마지막을 4자리로 했을 때의 난이도 + N-4 자리 까지 최적의 난이도.
마지막을 5자리로 했을 때의 난이도 + N-5 자리 까지 최적의 난이도.

위와 같이 계속 하위 문제로 최적의 난이도를 구한다면 이번 문제를 해결 할 수 있습니다.
이를 간단하게 코드로 표한하면 아래와 같습니다.

int bestScore(int n){
    if(n<3) return 99999; //99999를 불가능한 경우로 정의한다.
    else if(n<=5) return getScore(0, n);
    int best = 99999;
    for(i=3; i<=5 i++){
       int score = getScore(n-i, i) + bestScore(n-i);
       if(score < best){
           best = score;
       }
    }
    return best;
}

위 함수는 충분히 큰 임의의 수 99999를 계산이 불가능한 경우로 정의하였습니다.
2자릿수 이하의 입력을 받았을 경우 이를 3~5자리로 끊는 것은 불가능 하겠죠.

이제 입력받은 n 열 부터 i 자리수로 끊을 경우의 점수를 계산하는 getScore 함수만 구현하면 문제를 해결 할 수 있습니다.

하지만 여기서, 입력받은 수의 자릿수가 길어지게 될 경우 위 재귀함수의 반복호출이 커지게 되고, 이는 메모리 부하가 크며, 반복해서 재귀함수를 호출하는 것에 의해 속도가 느려질 수 있습니다.

따라서 이제 다시 위 문제를 단순 반복문으로 해결해 보겠습니다.

문제를 해결하는 기본 원리는 알았으므로, 이제 1부터 시작해 최적의 점수를 찾으며, N자리까지 반복해 나갑니다.
이를 위해 최적의 점수를 저장하고 있을 배열을 b를 준비합니다.

int bestScore(int n){
    b[0] = b[1] = 99999;
    b[2] = getScroe(0, 3);
    b[3] = getScore(0, 4);
    b[4] = getScore(0, 5);

    for(int i=5; i<n; i++){
        b[i] = 99999;
        for(int j=3; j<=5; j++){
            int scroe = b[i-j] + getScore(i-j, j);
            if(score < b[i]){
                b[i] = score;
            }
        }
    }
    return b[n-1];
}

여기서 저는 한단계 더 나아가 getScore 함수를 개선했습니다. 즉 반복해서 구하는 getScore 함수가 아닌, 현재 숫자가 위 5가지 case 중 어떠한 패턴이 몇번 반복하고 있는지를 미리 구해놓을 경우 getScore 함수를 3번이나 반복하여 호출하며 소요되는 시간을 줄일 수 있습니다.

또한 이 방법은 바로 전(1,2,4번 case), 혹은 전전(3번 case) 값만 비교하여 패턴이 몇번 반복되고 있는지만 기록하면 되어 getScore 함수보다 빠르게 점수를 구할 수 있습니다.

물론 여기에는 서로 다른 패턴이 서로 다른 횟수만큼 동시에 적용되지 않아야 적용이 가능합니다.

이 문제 같은 경우, 1번(0씩 증가하는 등차수열?)이나 2번(1씩 증가하는 등차수열) 패턴이 적용 될 경우 4번 패턴도 동시에 적용이 되지만 적용 횟수가 다를 수는 없으므로 무조건 점수가 높은 앞에 패턴이 적용된 것으로 하며, 앞에 패턴이 깨질 경우 뒤에 패턴도 같이 깨지게 됩니다.

또한 3번 패턴이 적용 될 경우, 1,2,4번 패턴은 적용 될 수 없으며, 반대의 경우 역시 마찬가지입니다.

이를 구현하기 위해 몇번 case의 패턴이 반복되고 있는지 case의 점수를 기록할 sc 변수와 패턴이 몇번 반복되고 있는지 기록할 nc 변수, 그리고 1,2,4번 case의 반복패턴 비교를 위한 d 변수를 사용합니다.

각각의 case의 패턴이 반복되고 있는지 확인하는 방법은 아래와 같습니다.

1. n[i] == n[i-1]
2. (n[i] - n[i-1]) == 1(or -1)
3. n[i] == n[i-2]
4. (n[i] - n[i-1]) == d (등차수열의 일정하게 증가하는 값.)

여기서 1, 2번은 d 값이 각각 0과 1(or -1)인 등차수열로 보고 4번이 맞는지 확인 후 d 값이 0 혹은 1(or -1)인지 확인하는 과정을 거치면 됩니다.
== 소스보기 ==

결과

#
453748
문제
PI
언어
cpp
길이
864B
수행시간
5ms
결과
정답
제출일
2016-08-06

2016년 8월 5일 금요일

[Algospot] 게임판 덮기

문제 정보

문제ID
BOARDCOVER
출제자
JongMan
출처
알고리즘 문제 해결 전략
시간제한
2000ms
메모리제한
65536kb
분류
탐색

문제 설명

H*W 크기의 흰색과 검은색으로 구성된 게임판이 주어졌을 때 해당 게임판을 L자 모형의 격자로 덥을 수 있는 모든 경우의 수를 구하는 문제입니다.

문제 풀이

모든 경우의 수를 찾는 문제이며, 격자를 넣는 순서는 해결방법과는 무관합니다.
이와같은 문제를 푸는데는 깊이우선탐색을 사용한 백트래킹 알고리즘이 효과적입니다.

백트래킹 알고리즘은 해를 얻을때까지 모든 가능성을 검토하는 것으로, 분기점들을 만날때마다 하나의 분기를 선택해 탐색을 해나가며, 오답을 찾을 경우 이전 분기점으로 돌아가 다시 탐색을 시작하여, 결국 모든 분기점을 돌며 탐색을 하는 방법입니다.

일반적으로 백트래킹 알고리즘에서는 재귀함수를 많이 사용하며, 이번 문제를 해결하는데에도 역시 재귀함수를 사용하였습니다.

백트래킹에서 가장 중요한 것은 오답인 경우를 빠르게 찾아 재귀를 줄이고 탐색속도를 향상시키는 것이며, 이번 문제 역시 이를 중점적으로 문제를 풀어나가야 주어진 제한 시간내에 문제를 해결 할 수 있습니다.

Show Spoiler : 숨겨진 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 숨겨진 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다.Close Spoiler

이번 문제의 가장 기본적인 알고리즘은 빈칸을 찾고, 해당 칸에 격자를 하나씩 넣어가며 빈칸을 채워가는 것입니다.

우선 게임판을 탐색할 순서부터 정의합니다. 순서는 문제를 해결하는데 아무런 영향을 주지는 않으나 아래에서 설명할 보드에 격자를 놓을 때 중심점을 정의하는데 같이 고려를 해야 할 필요가 있습니다.

저는 상단, 좌측부터 탐색을 하기로 정의하였으며, 격자의 중심도 이에 맞춰 상단 좌측를 중심으로 정의 하였습니다.

이후 빈칸에 격자를 넣을 수 있는 경우의 수와 격자를 넣는 방법에 대해 정의를 합니다.
격자는 다음과 같이 ㄱ 과 ㄴ 형태와 이를 상하 반전한 4개의 방법이 있으며, 위에서 언급한 것과 같이 격자의 상단 좌측을 중심으로 격자를 넣도록 하였습니다.


위 그림의 파란색 칸이 중심칸입니다.
격자의 중심점과 탐색방향을 위와같이 상단, 좌측을 기준으로 뒀을 경우 탐색을 해나가면서 격자를 넣을때 아래 그림과 같이 이미 탐색한 영역과 격자를 넣는 영역이 겹치지 않게 됩니다.


이제 파란색 중심점을 i번째 높이 j번째 칸을 기준으로 정의하면 파란색과 검은색 점들의 좌표는 다음과 같습니다.

case 1 : (i, j), (i, j+1), (i+1, j+1)
case 2 : (i, j), (i, j+1), (i+1, j)
case 3 : (i, j), (i+1, j), (i+1, j+1)
case 4 : (i, j), (i+1, j-1), (i+1, j)

이제 위와 같이 탐색하며, 격자를 넣는 코드를 구현하기위해 두개의 함수를 만듭니다.
각각 상단 좌측부터 게임판을 탐색하며 빈칸을 찾는 board(int h, int w) 함수와 입력받은 칸들에 격자를 넣는 cover(int h1, int w1, int h2, int w2, int h3, int w3) 함수입니다.

board 함수는 입력받은 h, w 부터 정해진 순서대로 보드판을 탐색해 나가며, 빈칸을 찾고 그 빈칸에 격자를 넣는 4가지 경우에 따라 cover 함수를 호출합니다.

cover 함수는 입력받은 좌표 (h1, w1), (h2, w2), (h3, w3)에 격자를 넣을 수 있는지 확인하고, 격자를 넣을 수 없다면 함수를 종료하고, 격자를 넣을 수 있다면, 격자를 넣은 후 다시 board 함수를 호출해 새로운 빈칸을 찾습니다.

즉 두 함수가 서로가 서로를 호출하며, 탐색과 격자를 넣는 것을 반복해 게임판을 채워나가며, 모든 게임판을 채웠을 경우 Count를 증가시키며, 게임판을 모두 채울 수 있는 경우의 수를 찾아나갑니다.
== 소스보기 ==

결과

#
453571
문제
BOARDCOVER
언어
cpp
길이
1.0KB
수행시간
3ms
결과
정답
제출일
2016-07-05

[Algospot] 달과 그림자


문제 정보


문제ID
MOON
출제자
Taeyoon_Lee
출처
2014 KAIST ACM-ICPC 모의대회
시간제한
3000ms
메모리제한
65536kb
분류
.

문제 설명

달과 그림자의 반지름 m, s와 두 중심사이의 거리 c가 주어졌을 때 그림자에 가려지지 않은 달의 넓이를 구하는 공식 문제입니다.


m, s, c의 조건은 다음과 같이 주어집니다.


  • (2 <= m < s < c <= 12, c < m + s)
  • 풀이 과정

    우선 두원이 겹치는 경우의 수는 다음과 같이 4가지의 경우의 수로 나누어 볼 수 있습니다.

    case 1 : 두 원이 완전히 겹치는 경우 (c <= s - m)
    case 2 : 두 원이 겹치지 않는 경우 (c > s + m)
    case 3 : 한개의 원의 중심이 다른 원에 포함 된 경우 (c < s)
    case 4 : 원의 중심과 두원이 맞닿는 점을 잇는 선들의 각도가 모두 예각인 경우.

    여기서 m, s, c의 조건을 확인한 결과 우리는 4번 case의 경우만 고려하면 된다는 것을 알 수 있습니다.

    그럼 문제를 풀기위해 위 그림에 중심선과 두원이 맞닿는 점, 그리고 두 중심섬을 잇는 선을 그리고 주어진 정보 m, s, c를 표시하면 다음과 같습니다.


    설명을 위해 편의상 각 점들을 대문자 M, S와 A, B로 표기하였습니다.

    위 그림을 보신분들 중 문제를 해결하기 위한 방법을 눈치채신 분들도 있으실 것 같습니다.

    문제에서 요구하는 답은 겹치지 않는 노란색 원의 넓이입니다. 이를 구하기 위해, 도형을 다음과 같이 분리할 수 있습니다.

    두개의 원과 M,A,B를 잇는 부채꼴과 삼각형, S,A,B를 있는 부채꼴과 삼각형.

    여기서 다음과 같은 식을 만들어 볼 수 있습니다.

    원(M) - ( 부채꼴(M,A,B) - 삼각형(M,A,B) ) - ( 부채꼴(S,A,B) - 삼각형(S,A,B) )
    = 원(M) + 삼각형(M,A,B) + 삼각형(S,A,B) - 부채꼴(M,A,B) - 부채꼴(S,A,B)
    = 원(M) + 사각형(M,A,S,B) - 부채꼴(M,A,B) - 부채꼴(S,A,B)

    이제 주어진 정보를 가지고 원과 부채꼴, 삼각형을 구하면 문제를 해결할 수 있습니다.

    Show Spoiler : 숨겨진 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 숨겨진 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다. Close Spoiler

    원과 부채꼴, 삼각형의 넓이를 구하는 공식은 다음과 같습니다.

    원의 넓이 = πr²
    부채꼴의 넓이 = 1/2r²θ
    삼각형의 넓이*2 = 1/2ah * 2 = ah

    하지만 주어진 정보로는 원의 넓이 π * m * m 는 구할 수 있지만
    부채꼴의 넓이를 구하는 공식 1/2 * m * m * θ₁ 과 1/2 * s * s * θ₂ 의 각도 θ₁과 θ₂,
    사각형의 넓이를 구하는 공식 1/2 * a * h의 밑변 a와 높이 h가 추가적으로 필요합니다.

    여기서 필요한 값들을 구하기 위해 위 그림에서 A와 B를 잇는 임의의 선를 추가합니다.


    (눈만 아프게 색깔만 늘어나네요.)
    해당 선은 위에서 보는 것과 같이 c와 수직으로 만나며, 동일한 길이의 두개의 임의의 선 h로 나누어지며, c를 나눈 임의의 선 c1과 c2로 나누어질 수있습니다.

    이제 사각형 M,A,S,B의 넓이는 동일한 넓이를 가지며 밑변이 c, 높이가 h인 두 삼각형 M,A,S와 M,B,S의 넓이의 합으로 구할 수 있습니다.

    그리고, 부채꼴의 넓이를 구하기 위한 각도를 구하기 위해서는 사각형을 4등분하고 있는 직각삼각형을 이용하여 삼각함수와 역삼각함수를 이용하여 구할 수 있습니다.

    즉, M,A,B로 이루어진 부채꼴의 각도는 asin(h/m)으로 구할 수 있으며, S,A,B로 이루어진 부채꼴의 각도는 asin(h/s)로 구할 수 있습니다.

    여기까지 정리하면 다음과 같습니다.

    원(M)의 넓이 = π * m * m
    사각형(MASB)의 넓이 = (1/2 * s * h) * 2 = s * h
    부채꼴(MAB)의 넓이 = 1/2 * m * m * (asin(h/m) * 2) = m * m * asin(h/m)
    부채꼴(SAB)의 넓이 = 1/2 * s * s * (asin(h/s) * 2) = s * s* asin(s/m)

    이제 미지수는 h밖에 남지 않았네요.

    마침, 우리가 알고있는 정보 m, s, c의 세개의 선으로 이루어진 삼각형 MAS가 존재합니다.
    그리고 세변의 길이를 알고있을 때 헤론의 공식을 이용하여 삼각형의 넓이를 구할 수 있으며, 이를 밑변 s로 나눈 후 2를 곱하면 높이 h를 구할 수 있습니다.

    헤론의 공식은 다음과 같습니다.


    위 공식으로 h를 구하면,

    msc = (m + s + c) / 2
    h = sqrt( msc * (msc - m) * (msc - s) * (msc - c) )

    멀리 돌아왔네요.
    이제 여기서 구한 공식을 코딩을 통해 구현하면 답을 구할 수 있습니다.

    == 소스보기 ==

    결과

    #
    453372
    문제
    MOON
    언어
    cpp
    길이
    333B
    수행시간
    3ms
    결과
    정답
    제출일
    2016-08-05

    2016년 8월 4일 목요일

    [Algospot] 문제 순서는 난이도 순이 아닙니다


    문제 정보


    문제ID
    FIX
    출제자
    Taeyoon_Lee
    출처
    2014 KAIST ACM-ICPC 모의대회
    시간제한
    3000ms
    메모리제한
    65536kb
    분류
    구현

    문제 설명

    k번째로 쉬운 문제가 k번째에 배치된 경우를 Count 하는 문제입니다.
    간단하게 현재 입력값이 몇번째 입력인지를 확인하면 되는 문제네요.

    풀이 과정

    간단한 문제인 만큼 별도로 내용을 적지는 않아도 될 것 같네요.
    for문을 통해 i를 1부터 증가시켜가며 입력받은 값과 i를 비교해 주었습니다.

    == 소스보기 ==

    결과

    #
    453081
    문제
    FIX
    언어
    cpp
    길이
    263B
    수행시간
    2ms
    결과
    정답
    제출일
    2016-08-04

    2016년 8월 3일 수요일

    [Algospot] 삽입 정렬 시간 재기


    문제 정보


    문제ID
    MEASURETIME
    출제자
    JongMan
    출처
    알고리즘 문제 해결 전략
    시간제한
    2000ms
    메모리제한
    65536kb
    분류
    자료구조, 정렬, 트리

    문제 설명

    삽입정렬 시간재기 문제는 정렬알고리즘 중 O(n²)의 시간복잡도를 가진 삽입정렬 알고리즘에서 정렬을 하기위해 숫자가 움직이는 횟수를 구하는 문제입니다.

    삽입정렬(Insertion sort)은 앞에서 부터 차례대로 정렬시켜 나가며, 이미 정렬되어 있는 부분과 비교하여, 자신의 위치를 찾아 정렬 시키는 알고리즘으로 일반적인 O(n²)의 정렬 알고리즘인 선택정렬이나 거품정렬 보다는 빠른 속도를 가집니다.

    풀이 과정

    이 문제 풀이의 핵심은 순차적으로 입력을 받으며, 먼저 입력 받은 값 중 현재 값보다 큰 수가 몇개인지를 Count 하는 것입니다.
    물론 모든 값을 입력 받은 후에 계산을 하여도 되지만, 모든 값을 입력받은 후 처리를 하였을 때 얻을 수 있는 장점이 없으므로  편의상 입력을 받으며, 바로 처리하는 방법으로 문제를 풀어 나갔습니다. 

    우선 간단하게 문제를 해결하는 방법으로 입력값들을 배열에 담아 새로 입력을 받을 때 마다 이전 입력 값들과 현재 값을 비교하여 큰 수들을 Count 하는 방법입니다.
    #include <stdio.h>
    int main(void) {
      int c,n,i,j,A[1000000], count;
      scanf("%d",&c);
      while(c--){
        count=0;
        scanf("%d",&n);
         for(i=0; i <n; i++){
          scanf("%d",&A[i]);
          // 이전 입력값과 현재 값을 비교하여 큰 수를 Count.
          for (j=0; j <i;j++){
            if (A [j]>A [i]){ 
              count++; 
            }
          }
        }
        printf("%d\n", count);
      }
      return 0;
    }
    아주 간단한 방법입니다만 예상대로 시간이 너무 오래 걸리는 단점이 있습니다.
    위 연산은 n 개의 값을 입력받는다고 했을 경우 0+1+ ~ +(n-1) = n(n-1)/2 의 시간복잡도 O(n²)를 가집니다.

    사실 이 문제에는 위 방법이 아닌 더 간단한 아이디어로 문제를 풀 수 있는 방법이 있습니다. 그건 바로 직접 삽입정렬을 수행하며, 숫자가 움직이는 횟수를 Count 하는 방법입니다.
    #include <stdio.h>
    int main(void) {
      int c,n,i,j,A[1000000],in,count;
        scanf("%d",&c);
        while(c--){
          count=0;
          scanf("%d",&n);
           for(i=0; i <n; i++){
            scanf("%d", &in);
            //삽입정렬을 수행하며 숫자가 움직이는 횟수를 Count.
            for (j=i-1; j>=0;j--){
              if (A[j]>in) {
                A[j+1] = A[j];
                count++; 
              } else {
                break;
              }
            }
            A[j+1] = in;
          }
          printf("%d\n", count);
        }
      return 0;
    }
    하지만 역시 삽입정렬은 위 첫번째 연산보다는 빠르겠지만 최악의 경우 0+1+ ~ +(n-1) = n(n-1)/2 의 시간복잡도 O(n²)를 가지는 연산으로 시간초과에 걸리게 됩니다. 

    이 문제를 해결하기 위해서는 좀 더 빠르게 정렬을 수행하며, 현재 값보다 큰 값들을 찾을 수 있는 연산이 필요합니다.
    Show Spoiler : 아래 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 아래 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다. Close Spoiler
    이번 문제에서 제가 찾은 방법은 '이진 탐색 트리'를 이용한 방법입니다.
    이진 탐색 트리는 자식 노드를 2개만 가지는 이진 트리를 이용한 탐색 알고리즘으로서,
    일반적으로 좌측 자식 노드에는 현재 값보다 작은 값이, 우측 자식 노드에는 현재값보다 큰 값이 위치하게 트리를 구성합니다.

    이와 같이 트리를 구성할 경우 O(nlogn)의 시간복잡도로 정렬을 구현할 수가 있습니다.

    여기에 각 노드에 자신보다 큰 자식노드(우측 노드)의 수를 가지고 있다면, 탐색을 해 나가면서 이전에 입력받은 값중에 현재 값보다 큰 값이 몇개인지를 알 수 있습니다.

    제가 구현한 방식은 배열을 이용한 방법으로 A[n][4]의 배열을 만든 후 A[n][0] 에는 입력받은 값을, A[n][1] 에는 우측 자식 노드의 수를, A[n][2] 좌측 자식노드의 index를, A[n][3]에는 우측 자식노드의 index를 저장합니다.
    Value
    nRight
    left
    right

    배열은 입력받은 순서대로 index 0 부터 index n-1까지 입력을 저장이 되며, 초기 A[i][0]에 입력받은 값을, A[i][1], A[i][2], A[i][3]은 0으로 세팅합니다.
    이 후, Root 인 i=0 부터 탐색을 하며, 우측으로 이동할 때 마다 우측노드수(A[i][1])를 1씩 증가시키며, 좌측으로 이동할때는 해당 우측노드수(A[i][1])+1 을 Count에 추가해주면 결과를 구할 수 있습니다.

    설명만으로는 이해가 어려울 수 있으니 예제입력 4, 2, 5, 3, 1를 가지고 설명을 하겠습니다.
    index 0 번째가 곧 Root 노드가 되며, 처음 입력받는 값 4가 A[0][0]에 값이 저장됩니다.

    Value 4 0 0 0 0
    nRight 0 0 0 0 0
    left 0 0 0 0 0
    right 0 0 0 0 0

    다음 index 1에 두번째 입력값 2을 저장 한 후 Root 노드 인 A[0][0] 부터 탐색을 하며 이진탐색트리를 만들어갑니다.
    index 1의 입력값 2가 4보다 작으며, A[0]의 좌측노드가 없으므로 A[0][2]에 index 값 1이 저장됩니다.

    Value 4 2 0 0 0
    nRight 0 0 0 0 0
    left 1 0 0 0 0
    right 0 0 0 0 0

    이 때의 Count는 1+A[0][1] = 1+1 = 1 이 됩니다.

    다음으로 index 2에 세번째 입력값 5를 저장한 후 Root 노드부터 탐색합니다.
    index 2의 입력값 5가 4보다 크며, A[0]의 우측노드가 없으므로 A[0][3]에 index 값 2가 저장됩니다.
    그리고 index 0보다 큰 값이 추가되었으므로 A[0][1]를 1 증가합니다.

    Value 4 2 5 0 0
    nRight 1 0 0 0 0
    left 1 0 0 0 0
    right 2 0 0 0 0

    이 때의 Count는 좌측으로 이동한 적이 없으므로 0이 됩니다.

    다음으로 index 3에 네번째 입력값 3를 저장한 후 Root 노드부터 탐색합니다. A[0][0]과 비교(3<4) -> A[1][0]과 비교(3>2) 이므로 A[1][2]에 index 3를 저장 후 A[1][1]를 1 증가합니다.

    Value 4 2 5 3 0
    nRight 1 1 0 0 0
    left 1 0 0 0 0
    right 2 3 0 0 0

    이 때의 Count는 좌측으로 A[0]에서 1번 이동하였으므로 1+A[0][1] = 1+1 = 2가 됩니다.

    마지막 index 4에 다섯번째 입력값 1를 저장한 후 Root 노드부터 탐색합니다. A[0][0]과 비교(1<4) -> A[1][0]과 비교(1<2)이므로 A[1][2]에 index 4를 저장합니다.

    Value 4 2 5 3 1
    nRight 1 1 0 0 0
    left 1 4 0 0 0
    right 2 3 0 0 0

    이 때의 Count는 좌측으로 A[0], A[1]에서 2번 이동하였으므로 2+A[0][1]+A[1][1] = 2+1+1 = 4가 됩니다.

    이제 Count를 모두 더하면 0+1+0+2+4 = 7이 됩니다.
    이는 다음과 같이 결과를 확인할 수 있습니다.

    A비고
    4 2 5 3 1초기 상태(이동 0)
    2 4 5 3 12를 왼쪽으로 1칸 옮김(이동 1)
    2 4 5 3 15를 이동하지 않음(이동 0)
    2 3 4 5 13를 왼쪽으로 2칸 옮김(이동 2)
    1 2 3 4 51를 왼쪽으로 4칸 옮김(이동 4)

    == 소스보기 ==

    결과

    #
    452827
    문제
    MEASURETIME
    언어
    cpp
    길이
    690B
    수행시간
    226ms
    결과
    정답
    제출일
    2016-08-03