출처 

Koreatech OnlineJudge(링크)


문제이해
3xN길이의 판을 1x1 블럭과 2x2 블럭으로 채울 때 판을 꽉 채울 수 있는 방법의 수를 구하는 문제이다. 피보나치 수열을 사용하여 푸는 1056번 문제를 풀었다면 응용하여 풀 수 있다.



문제접근 

n번째 항을 구할 때 n-1번째 항과 n-2번째 항의 값을 가지고 구할 수 있다.

먼저 n-2항에서 n항으로 확장하는 방법은 [그림 1] 처럼 2가지이다.

 

[그림 1]



그리고 n-2항에서 n항으로 확장하는 방법은  [그림 2] 처럼 1가지이다.

[그림 2]



따라서 점화식은

이다.



[그림 3]에서와 같이 n-2항에서 1x1타일 6개를 확장할 수도 있기 때문에

혼동하기 쉬운데, 이 경우는 [그림 2]의 경우에 포함되므로 계산하지 않아야 한다.

[그림 3]



구현
첫 번째 항을 1로 하고, 두 번째 항을 3으로 하여 위 점화식을 반복하여 계산하면 된다.

숫자가 커질 수도 있으므로 오버플로에 주의하며 1,000,000,007로 나누어야 한다.

또한, N=1인 입력도 있으므로 이 경우에도 올바른 값이 나오도록 해야 한다.



실행결과 



코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1055/1055.cpp




출처 

Koreatech OnlineJudge(링크)


문제이해

각 테스트케이스마다 문자열이 한 줄씩 주어진다.

문자열은 R, G, B 3가지 문자로 이루어져 있으며 각 문자마다 

일렬로 배치되어 있는 공의 색깔을 나타낸다.

한 턴에 맨 앞 혹은 맨 뒤의 공 하나만 제거할 수 있을 때

한 가지 색만 남기려면 최소 몇 개의 공을 제거해야 하는지 구하는 문제이다.


문제접근

dequeue 같은 자료구조가 연상되는 문제이지만

몇 가지 경우를 생각해 보면, 연속된 색의 최대길이를 구하는 간단한 문제라는 것을 알 수 있다.

문제의 조건에 따르면, 마지막에는 항상 연속된 구간만 남게 되기 때문이다.


구현

문자열을 선형탐색하며 가장 긴 연속색의 길이를 구한다. (O(n))


실행결과



코드 (컴파일러 : GNU C++11)

https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1028/1028.cpp

출처 

Koreatech OnlineJudge(링크)



문제이해 

배열의 처음부터 끝까지 주어진 간격(1~3) 이하만큼 숫자를 고를 때

최소비용을 구하는 동적 프로그래밍 문제이다.

문제에 직접적으로 서술되어 있지는 않지만, 설명을 보면 첫 번째나 마지막 징검다리는 밟지 않아도 된다는 것을 알 수 있다.



문제접근

간단한 유형의 DP(Dynamic Programming)문제이다.

예를 들어 {28, 85, 89, 70, 1, 43}이 주어질 때는,


89, 1을 고르면 되는데, 89까지의 최적해가 전체 문제의 부분해가 될 수 있는 재귀적 속성(recursive property)이 있다.


배열의 왼쪽부터 시작해서 요소 하나씩 검사해 나가면 되는데,

먼저 처음 원소인 28에 다다르기 위한 최소비용은 당연히 28이다.

그 다음 원소인 85에 가는 방법은 28을 거쳐서 가는 방법과, 85로 바로 가는 방법이 있는데,

85로 바로 가는 방법이 최소비용이므로 최소비용은 85이다.

그 다음 원소인 89 역시 (89까지 도착하기 위한)최소비용이 89이다.


그 다음 원소인 70부터는 아래와 같이 3가지 방법이 있다.

1) 28 -> 70

2) 85 -> 70

3) 89 -> 70

이 중 최소비용은 1번으로, 70까지의 최소비용은 28+70=98이 된다.


그 다음 원소인 1까지 가는 최소비용은 같은 원리로 3가지가 있다.

1) 85까지의 최소비용 + 1

2) 89까지의 최소비용 + 1

3) 70까지의 최소비용 + 1

기억해 놓은 정보로 계산하면,

1) 86

2) 90

3) 98

이므로 1까지의 최소비용은 86이 된다.


이러한 과정을 배열의 끝까지 반복하면 된다.


문제에서 주어진 점프력이 3이므로 현재 위치에서 3개 전까지의 수를 봐야 하는 것이다.



실행결과 



코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1011/1011.c





출처

Koreatech OnlineJudge (링크)




문제이해

소수 719333은 큰 자리부터 순서대로 붙여 나간 각각의 수

7, 71, 719, 7193, 71933이 모두 소수이다.

문제에서 이러한 수를 '접두 소수'라고 정의한다.

수의 길이 n이 주어졌을 때 n자리인 접두 소수를 출력하는 문제이다.

 



문제접근

우선 소수를 판별하는 함수를 작성해야 한다.

n이 소수인지 판별할 때 2부터 n까지 나눠봐서

나누어 떨어지는 경우가 있으면 소수가 아니고, 없으면 소수이다.

그런데 이렇게 하면 n이 커지는 경우 연산량이 비례해서 늘어나므로 연산량을 줄여야 한다.

약수는 대칭성이 있기 때문에 sqrt(n)까지만 나눠봐도 소수를 판별할 수 있다.


다음은 n자리의 접두소수를 백트래킹(Backtracking)으로 구해야 하는데, 

한 자리 소수인 2, 3, 5, 7부터 시작하여 다음 자리수를 검사한다.




3부터 시작하는 경우 다음 자리는 짝수와 5의 배수를 제외한

31, 33, 37, 39를 소수판별하면 되는 것이다.




구현

재귀함수나 스택, 큐 등을 사용하여 구현할 수 있다.


main()함수 내에서 다음과 같이 2, 3, 5, 7와 전체 자리수를 주어 시작하고,

print(2, digit);

print(3, digit);

print(5, digit);

print(7, digit); 


print()함수 내에서는 digit이 1이 되었을 때 탈출하면서 출력을 하도록 조건을 주었다.


그리고 아래와 같이 다음 자리에 해당하는 재귀호출을 한다.

n *= 10;

for (int i = 1; i < 10; i += 2) {

if (i == 5) continue;

if (isPrime(n + i)) {

print(n + i, digit-1);

}





실행결과





코드

https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1010/1010.cpp





출처

Koreatech OnlineJudge (링크)



문제이해

10진수 숫자 A와 진법을 나타내는 수 B가 주어질 때

A를 B진법으로 표현하여 출력하는 문제이다. 



문제접근

수학 교과과정에 나오는 것과 같이 A를 B로 계속 나누면서

매 과정마다 나머지를 기록하면 변환할 수 있다.

자세한 과정과 코드는 이전에 쓴 글(http://tibyte.kr/261) 참고.



구현

재미로 숏코딩을 해 보면, gets()를 사용하여 케이스 수를 버리고, scanf()의 EOF반환값을 이용하여 120B까지 줄일 수 있다. 

숏코딩 정리 : http://tibyte.kr/270



입출력 예시



코드

https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1031/1031.c


공부목적으로 Koreatech OnlineJudge 문제를 정리해봅니다.
간단한 문제는 제외하고 시간나는대로 한 문제씩 포스팅 예정입니다.
난이도는 주관적 판단입니다...
(2016년 12월 8일 현재 12문제 작성)


번호

문제명

분류

난이도

1005

0을 만들자 - Large


★★

1007

유일한 수

비트연산

1008

순환 소수

수학

★★★

1010

접두 소수

백트래킹

1011

징검다리

DP

1014

다이얼 자물쇠

MST

★★★

1016

소수로 만들어진 숫자

DP

★★

1017

돈을 줍자

DP

1018

문자열 거리 최소화 하기

문자열 검색

1019

숫자 바꿔치기

반복문

★★★

1027

인접한 문자 제거하기 HARD

스택

1028

단색이 좋아좋아 HARD

반복문

1030

한번 주식 거래하기


1031

다양한 진법 변환

수학

1042

두번 주식 거래하기


★★★

1043

위성 사진

그래프

★★

1046

빠른 길 찾기

그래프

1048

AP 배분

수학

★★★

1055

판 채우기

DP

★★

1057

걸기 쉬운 전화번호

DP

1058

동전 거슬러 주기

DP

★★

1059

구간 나누기

DP

★★

1060

팰린드롬 만들기

DP

★★

1067

펠린드롬 길게 만들기

 

 

1068

숫자 이어 붙이기


★★

1073

물 주기

수학

★★★

1074

유일한 수 두개

비트연산

★★




십진수 11을 이진수로 바꾸려면 

아래와 같은 과정을 거치면 된다.

ⓛ 11을 2로 나누면 몫은 5, 나머지는 1이다.
② 5를  2로 나누면 몫은 2, 나머지는 1이다.
③ 2를 2로 나누면 몫은 1, 나머지는 0이다.
④ 1을 2로 나누면 몫은 0, 나머지는 1이다.

나머지가 순서대로 1, 1, 0, 1로 나오는데 이것을 뒤집으면
1, 0, 1, 1이 나오게 되고 이것이 십진수 11의 이진수 표현 1011이다.






십진수 m을 n진법으로 나타내는 과정도 이와 같다.

 m을 n으로 나누어 m을 몫으로 갱신하고 나머지 b1를 얻는다.

 m을 n으로 나누어 m을 몫으로 갱신하고 나머지 b2를 얻는다.

...

...


이같은 과정을 m이 0보다 작아질 때까지 반복하고,

얻은 b수열을 뒤집으면 n진법 표현을 얻을 수 있다.




아래는 C++로 구현한 코드이다. (예외처리는 하지 않음)

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
#include <iostream>
#include <string>
#include <algorithm>
 
int main()
{
    std::string marks = "0123456789ABCDEF";
    std::string str;
    int num, base;
 
    std::cin >> num >> base;
    
    for(;num>0;) {
        str += marks[num%base];
        num /= base;
    }
    
    std::reverse(str.begin(), str.end());
    
    std::cout << str << std::endl;
    
    return 0;
}
cs




C++의 string를 사용하는 대신, 배열의 뒤쪽에서부터 값을 채워나가면

뒤집는 동작을 하는 코드를 사용하지 않아도 된다.

대신 출력할 때 시작 위치 주소를 맞게 설정해야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
 
int main()
{
    int num, base;
    char res[32];
    int i = 30;
 
    scanf("%d%d"&num, &base);
    
    for(;num>0;) {
        res[i--= "0123456789ABCDEF"[num%base];
        num /= base;
    }
    res[31= '\0';
    
    printf("%s\n", res+i+1);
    
    return 0;
}
cs







링크 : http://codeforces.com/contest/723


A : The New Year: Meeting Friends

 세 사람이 있는 수직선 위의 세 지점이 주어지고, 모두의 이동거리의 합이 최소가 되는 약속지점을 찾는 문제이다. 교내대회에서 유사한 문제를 풀어본 적이 있어서 금방 해결할 수 있었다. 위치를 정렬했을 때 중간값이 되는 지점을 찾아야 하는데,  입력이 항상 3개라 조건문으로도 찾을 수 있겠지만 코드를 빨리 작성하려고 std::sort()를 사용하여 해결했다.


B : Text Document Analysis

 주어지는 문자열에서 괄호 밖에 있는 단어 중 가장 긴 단어와, 괄호 안에 있는 단어의 개수를 구하는 문제. 

괄호 안에 있는 단어 수를 셀 때, 언더스코어 또는 여는 소괄호 다음에 나오는 단어를 카운팅하는 것으로 간단하게 짤 수 있었다.


C : Polycarp at the Radio

 문제를 이해하지 못해서 시간만 소비하고 포기...


D : Lakes in Berland

 물과 육지를 나타내는 2차원 배열이 입력으로 주어지고, 호수의 개수를 주어진 수로 줄일 때 메워야 하는 영역의 최소 수를 구하는 문제이다.

  먼저 호수와 바다를 구분하기 위해 바깥쪽에 있는 물을 따로 표시했다. 최대 입력의 크기인 50x50보다 더 큰 52x52 배열을 만들고 바깥의 물을 BFS하여 바다로 표시했다.

 그리고 안쪽의 물 역시 BFS를 사용하여 영역의 개수를 세고, 각 영역의 크기와 시작점을 구조체로 저장해 두었다. 그리고 영역크기 순으로 소팅하여 작은 것부터 채우는 것으로 코드를 작성하였다.


A, B, D를 풀고 C도 풀어보려다가 시간이 다 되어 E, F번 문제는 못 풀어보았다..



Rank : 640

Rating : 1456 -> 1531 (+75)

 


격자 위에 원을 그려야 하거나 원 모양의 범위를 적용할 때

다음과 같은 식을 사용할 수 있다.



d가 0보다 크면 원 외부, d가 0보다 작으면 원 내부로 판단하는 것이다.


그러나 원을 그릴 때는 범위 내의 모든 점에 대입해야 할 뿐만 아니라 

매번 곱셈 연산을 3번 사용하여야 한다.



midpoint algorithm을 사용하면 이를 효율적으로 해결할 수 있다.

(원의 반지름이 n일 때 O(n))



원리




[그림1]

이 알고리즘의 원리는 결정된 한 점이 있을 때

한 칸 옆인 에 대응되는 y 값이 인지 인지 판단하는 것이다.  (위 그림에서 까만색 점 2개)



[그림 1]과 같이 원에 포함되는 것으로 결정된 한 점

가 있을 때 가 원의 내부인지 외부인지 판별하는 식은 아래와 같이 나타낼 수 있다.



중간점이 원 내부에 포함될 경우(p<=0), [그림1]에서 p의 위쪽 점을 선택하고,

p점이 원 밖일 경우(p>0) p의 아래쪽 점을 선택하는 것이다.


같은 방법으로 을 다음과 같이 점화식으로 나타낼 수 있다.




이제 을 결정해야 하는데,

위에서 서술한 바와 같이 의 부호에 따라 선택되므로 다음과 같이 나타낸다.



이를 활용하여 의 식을 간단히 하면



코드를 좀더 간편하게 하기 위해 대신 를 활용하면

최종적으로 아래 식을 얻을 수 있다.




한편 p의 초기값 는 위에서 식에 x의 초기값 0과 y의 초기값 r을 대입하여

5/4 - r이라는 것을 알 수 있다.


그런데 p의 점화식을 보면 초기값 외에는 모두 정수의 덧셈/뺄셈 연산이므로 (2x는 x+x로 계산)

p0을 int형으로 하고 1-r로 두어도 무방하다.




위 과정을 x > y가 되기 전까지 반복한다.

[그림 2]




실제로 그려보면 아래 그림과 같은 8분원(octant)을 얻을 수 있다.


[그림 3]




그리고 아래와 같이 대칭인 8개 점을 동시에 그리면 전체 원이 그려진다.

(x, y)

(x, -y)

(-x, y)

(-x, -y)

(y, x)

(y, -x)

(-y, x)

(-y, -x)


[그림 4]




4방향으로 뚫려 있는 부분은 따로 채워준다. 


[그림 5]



8개 부분을 따로 표시해 보면 아래 그림과 같다.


[그림 6]







원 채우



y값이 변할 때 해당 y좌표에 해당하는 부분을 모두 칠하면

가운데 정사각형 영역을 제외한 부분을 채울 수 있다.(하단 코드 참조)


[그림 7]



나머지 정사각형 부분은 쉽게 채울 수 있다.(하단 코드 참조)


[그림 8]


모두 단색으로 칠해보면 아래 그림과 같은 원이 나온다.


[그림 9]




콘솔창에서는 한계가 있어 Javascript를 사용하여 그린 큰 원.


[그림 10]






구현



[그림 9]를 그릴 때 작성한 C언어 코드이다.

gcc컴파일러로 컴파일 가능하다.


나머지 코드들은

https://github.com/tibyte/algorithms/tree/master/bresenham/midpoint_circle

에서 다운로드 가능.


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
81
82
83
84
#include <bits/stdc++.h>
 
const int SIZE = 28;
 
void drawCircle(int arr[SIZE][SIZE], int r, int x, int y);
void display(int arr[SIZE][SIZE]);
 
int main(void)
{    
    int arr[SIZE][SIZE] = {0,};
    
    drawCircle(arr, 111113);
    display(arr);
    
    return 0
}
 
 
void drawCircle(int arr[SIZE][SIZE], int r, int cx, int cy)
{
    int x, y;
    int p;
    
    x = 0;
    y = r;
    p = 1 - r;
    
    arr[y+cy][x+cx] = 1;
    arr[-y+cy][x+cx] = 1;
    arr[x+cy][y+cx] = 1;
    arr[x+cy][-y+cx] = 1;
 
    x = 1;
    while(x < y) {
        
        if(p < 0) {
            p += x++ 1;
        }
        else {
            p += x++ 1 -y-y;
            --y;
            for(int i=0; i<x; i++) {
                arr[y+cy][i+cx] = 1;
                arr[-y+cy][i+cx] = 1;
                arr[y+cy][-i+cx] = 1;
                arr[-y+cy][-i+cx] = 1;
                arr[i+cy][y+cx] = 1;
                arr[-i+cy][y+cx] = 1;
                arr[i+cy][-y+cx] = 1;
                arr[-i+cy][-y+cx] = 1;
            }
        }
        arr[y+cy][x+cx] = 1;
        arr[-y+cy][x+cx] = 1;
        arr[y+cy][-x+cx] = 1;
        arr[-y+cy][-x+cx] = 1;
        arr[x+cy][y+cx] = 1;
        arr[-x+cy][y+cx] = 1;
        arr[x+cy][-y+cx] = 1;
        arr[-x+cy][-y+cx] = 1;
        
        ++x; 
    }
 
    for(int i=cy-y+1; i<cy+y; i++) {
        for(int j=cx-y+1; j<cx+y; j++) {
            arr[i][j] = 1;
        }
    }
}
 
 
void display(int arr[SIZE][SIZE])
{    
    for(int i=0; i<SIZE; i++) {
        for(int j=0; j<SIZE; j++) {
            if(arr[i][j])
                printf("■");
            else
                printf(" ");
        }
        printf("\n");
    }
}
cs





html5 canvas를 사용할 때 자바스크립트(javascript)로 여러 줄 텍스트(multiline text)를 표시할 방법이 없어서 함수를 만들어보았다.


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
var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");
 
ctx.font="15px Consolas";
drawTextBox(ctx, "다람쥐 헌 쳇바퀴에 타고파\n다람쥐 헌 쳇바퀴에 타고파"1001001701.2)
 
function drawTextBox(ctx, text, x, y, fieldWidth, spacing) {
  var line = "";
  var fontSize = parseFloat(ctx.font);
  var currentY = y;
  ctx.textBaseline = "top";
  for(var i=0; i<text.length; i++) {
    var tempLine = line + text[i];
    var tempWidth = ctx.measureText(tempLine).width;
 
    if (tempWidth < fieldWidth && text[i] != '\n') {
      line = tempLine;
    }
    else {
      ctx.fillText(line, x, currentY);
      if(text[i] != '\n') line = text[i];
      else line = "";
      currentY += fontSize*spacing;
    }
  }
  ctx.fillText(line, x, currentY);
  ctx.rect(x, y, fieldWidth, currentY-y+fontSize*spacing);
  ctx.stroke();
}
cs





fillText()가 한 줄 짜리 텍스트만 출력할 수 있으므로 이를 여러 번 써서 멀티라인 텍스트필드처럼 보이도록 만드는 것이다.


코드의 동작 방식은 아래와 같다.

1) 임시변수(tempLine)에 쓸 문자열을 한개씩 더한다.

2) 더하면서 캔버스 컨텍스트의 measureText()를 이용하여 너비를 재고, 이것이 지정된 텍스트필드 너비를 넘었을 경우 한 줄을 fillText()로 화면에 그린다.

3) 매개변수로 입력받은 행간격 비율(spacing)만큼 아래로 간격을 띄워서 1)부터 반복한다.


1)에서 개행문자('\n')을 만났을 경우에도 줄바꿈을 한다.




전체 소스코드는 아래 링크에 업로드하였다.

https://github.com/tibyte/algorithms/tree/master/html5canvas-textfield





실행결과는 아래와 같다.





+ Recent posts