티바이트

출처

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()함수 내에서는 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

링크 : 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)

출처

ACM-ICPC Asia Regional - Daejeon (링크)

BAEKJOON Online Judge (링크)

문제이해

 1회에 1$짜리 버스 티켓과 2$짜리 기차 티켓이 있다.

그리고 1일, 7일, 30일 무제한 이용권이 있는데, 여기서는 버스티켓과, 버스와 기차를 모두 탈 수 있는 티켓으로 나뉜다.

 총 여행한 날짜와 각각의 날에 버스와 기차를 이용할 횟수가 입력으로 주어졌을 때 제시된 티켓들을 조합하여 티켓 값의 최소비용을 구하는 문제이다.

문제접근

 d[i]를 i일까지 여행했을 때 든 최소비용으로 정의한다. 그리고 하루 전까지 계산한 최소비용 d[i-1]에 오늘 탈 비용을 더하면 되는데, 7일권과 30일권 티켓도 있으므로 7일전과 30일전에서 각각 7일과 30일 티켓을 구입하여 올 경우도 생각해야 한다. 그러면 다음과 같이 7개의 선택지를 비교하여 min값을 구할 수 있다.

- d[i-1] + 버스 낱개 + 기차 낱개 구입비용

- d[i-1] + 버스 하루이용권 + 기차 낱개 구입비용

- d[i-1] + 하루이용권 구입비용

- d[i-7] + 버스 7일권 + 7일간 기차 최소비용

- d[i-7] + 7일권 구입비용

- d[i-30] + 버스 30일권 + 30일간 기차 최소비용

- d[i-30] + 30일권 구입비용

 주의할 점은 30일 버스티켓을 이용하고 있는 도중에도 7일짜리 버스+기차 티켓을 추가로 사는 것이 이득일 때가 있다는 것이다.

이제 위에서 진하게 표시한 '7일간 기차 최소비용'과 '30일간 기차 최소비용'을 구하는 것이 문제인데,

전자를 보면 7일권과 1일권의 가격 차이 때문에 버스 7일이용권을 구매한 상태에서, 버스+기차 하루이용권을 구매하는 것은, 7일간의 모든 날짜를 하루이용권만 가지고 계산하는 것보다 비용이 같거나 더 든다. 따라서 7일간 기차이용권을 낱개구매하는 것만 고려하면 된다.

30일간 기차 최소비용은 슬라이딩 윈도우를 사용하여, 하루이용권을 구매해야 이득인 연속된 날짜가 7일 이상 있는지 확인하여 할인차액(6$)를 뺀다.

구현

 최대 날짜 수가 10000일인데, 길이가 30인 슬라이딩 윈도우를 사용할 것이므로 조건을 간단히 하기 위해 배열 길이를 10060으로 선언하여 구현하였다.

 기차를 탄 횟수도 저장이 필요하여 역시 10060길이로 선언해서 배열 용량으로 총 20120*4 바이트를 사용하였다.

코드

https://github.com/tibyte/algorithm-problems/blob/master/baekjoon/10456.cpp

출처

Codeforces

(http://codeforces.com/problemset/problem/711/B)

문제이해

빈 칸을 의미하는 0이 한 개만 포함되는 불완전한 마방진이 입력으로 주어진다.

가로, 세로, 대각선의 합이 같은 마방진을 성립하게 하려면 어떤 수를 0 자리에 채워 넣어야 하는지 구하는 문제이다.

채워 넣을 수는 양의 정수로 한정된다. 채워 넣을 양의 정수가 없다면 -1을 출력하고, 있다면 그 수를 출력해야 한다.

문제접근

각각의 행 합, 열 합, 대각선 합을 구해서 

합이 다른 것을 찾는데, 그 행이나 열에는 0이 들어있어야 한다.

코드포시스 라운드에 참가할 때 

7 0 5

2 4 6

3 8 1

이런식으로 빈 칸에 0을 채워야 될 경우 -1을 출력해야 하는데

0을 출력해서 계속 W/A가 떴었다..

먼저 0이 들어있는 위치를 구하고,

0이 들어있지 않은 각각의 모든 행과 열들의 합을 구해서 합이 모두 같은지 검사한다.

그리고 그 합들이 모두 같고, 0이 포함되어있는 행/열보다 크면 유효하다고 판단한다.

대각선 2개도 고려해야 한다.

구현 

printf() 함수로 64비트 정수를 출력할 때 서식문자로 %lld 대신 %I64d를 써서 제출.

코드

https://github.com/tibyte/algorithm-problems/blob/master/codeforces/711b.cpp

문제 링크 (알고스팟)
https://algospot.com/judge/problem/read/ASYMTILING

문제 이해

2 x n크기의 직사각형 공간을 2x1혹은 1x2 크기의 타일로 완전히 채우는 방법의 수를 구하는 문제이다.

타일의 배치가 좌우대칭인 것은 제외한다.

풀이

예를 하나 뽑아서 2 x 6 크기의 공간을 채우는 경우를 생각해 본다.

여기서 2 x 6 크기의 공간을 채우는 여러 경우들을 2가지로 나눌 수 있다.

A. 맨 마지막 타일이 세로로 되어 있음

B. 맨 마지막 타일이 가로로 2개 되어 있음

남은 부분의 크기를 보면,

A의 경우 나머지 공간의 너비는 5이고

B의 나머지 공간의 너비는 4이다.

즉, A에서 남은 부분을 채우는 방법의 수는, 이 문제에서 너비가 5인 공간을 채우는 경우의 답과 같다.

B의 나머지 부분을 채우는 방법의 수 역시 너비가 4인 공간을 채우는 경우의 답과 같다.

여기서 이 문제의 재귀적 속성을 발견할 수 있으며

이 문제를 Dynamic Programing (동적 계획법)으로 풀 수 있다는 것을 알 수 있다.

상향식(bottom-up)으로 어떻게 풀 지를 구체적으로 생각해 보면,

- n=1 일 때 (1 가지)

- n=2 일 때 (2 가지)
- n=3 일 때는  (n=2의 가지수) + (n=1의 가지수)

'n=2의 가지수'는 위 그림에서 A의 경우이고, 'n=1의 가지수'는 위 그림에서 B이다.

- n=4일 때는 (n=3)의 가지수 + (n=2의 가지수)

...

...

..

n = k일 때는 (n=k-1 의 가지수) + (n=k-2 의 가지수)

어디서 본 적이 있는 점화식이 나온다. 바로 피보나치 수열이다.

그런데 문제에서 좌우대칭인 경우는 제외하라는 조건이 있다.

이번에는 채워야 할 공간의 크기가 짝수인 것과 홀수인 것으로 나누어 생각해야 한다.

공간의 크기가 홀수일 때 좌우대칭이 되기 위한 조건은

가운데에 블록이 세로로 있어야 하며 분할된 한 쪽 너비는 (int)n/2이다.

공간의 크기가 짝수일 때는 분할된 한 쪽 너비가 n/2이다.

분할된 너비에 해당하는 경우의 수를 빼면 최종적인 답을 구할 수 있다.

구현

대칭인 경우를 제외시키기 위해 너비의 절반을 구해야 하는데,

피보나치 수열을 구하는 과정에서 같이 계산하도록 했다.

그리고 답을 리턴할 때, 이 문제에서 나머지연산한 결과를 요구하므로

계산 과정에서 그 수를 초과하지 않도록 주의하여야 한다.

A - B%mod + mod 와 같이 더해주면 값이 음수가 되는 것을 방지할 수 있다.

문제 주소 : https://algospot.com/judge/problem/read/BOARDCOVER

(알고스팟)

문제 이해

격자 모양의 게임판이 주어진다.

입력으로 주어지는 게임판에는 검은 칸과 흰 칸이 있으며

이 중에서 흰 칸을 아래 4가지 모양의 블록으로 채울 때

남은 칸을 모두 채울 수 있는 경우의 수를 구하는 문제이다.

가능한 답을 완전탐색(exhaustive search)해야 한다.

전략

흰 칸을 블록으로 모두 채운 경우에서

이 중 하나의 블록을 제외하여도 나머지 블록은 칸을 모두 채우고 있는 것을 볼 수 있다.

블록이 4가지 모양에 따라 가지를 뻗어 나가면서 탐색한다.

블록 하나를 배치한 뒤 남은 흰 칸을 재귀호출로 넘긴다.

다시 블록 하나를 배치하고 남은 흰 칸을 재귀호출로 넘긴다.

만약 칸을 더 이상 채울 수 없다면 재귀에서 탈출한다.

그리고 다음 단계에서 다른 모양으로(블록은 회전 때문에 4가지 모양이 있다)

흰 칸 채우기를 수행하기 위해 다시 재귀호출을 한다.

만약 칸을 모두 채웠다면 1을 반환한다.

재귀 구조에서 이 수를 누적하여 계산한다.

풀이

가능한 블록의 모양이 위 그림과 같으므로

함수의 구조는 대략 이렇게 될 것이다.

insert (map, free) {  //2차원배열, 남은 흰 칸 수

    int count = 0;

    if (남은 칸이 3의 배수가 아니면) {

        return 0;

    if (남은 칸이 3이고, 채울 수 있는 형태이면) {

        return 1;

    }

    if (남은 칸이 3이고, 채울 수 없는 형태이면) {

        return 0;

    }

    if (1번 블록을 채울 수 있으면) {

        1번 블록을 채운다;

        count += insert(map, free-3);

        1번 블록을 해제한다:

    }

    if (2번 블록을 채울 수 있으면) {

        2번 블록을 채운다;

        count += insert(map, free-3);

        2번 블록을 해제한다:

    }

    if (3번 블록을 채울 수 있으면) {

        3번 블록을 채운다;

        count += insert(map, free-3);

        3번 블록을 해제한다:

    }

    if (4번 블록을 채울 수 있으면) {

        4번 블록을 채운다;

        count += insert(map, free-3);

        4번 블록을 해제한다:

    }

    return count;

}

이 때 생각해 볼 점은, 처음에 블록을 어디부터 채우고,

그 다음에는 또 어디부터 채울 것이냐다.

여기서는 상단, 좌측을 우선하여 블록을 채우기로 했다.

블록을 채우는 순서는 경우의 수에 영향을 미치지 않기 때문에 하단부터 채워도 결과는 같다.

상단,좌측을 우선하여 블록을 채울 때

기준이 되는 점(초록색)과 추가로 검사해야 하는 점(회색)은 아래그림과 같다.

소스코드(C++)

(설명의 블록 번호와 아래 소스코드의 블록 번호는 다릅니다)

문제 링크 : https://www.algospot.com/judge/problem/read/POTION

(알고스팟)

문제 이해

어떤 약을 한 단위 만드는 데 필요한 n개의 재료들의 양과

현재 넣은 재료의 양이 입력된다.

이 때 약을 만들기 위해 더 넣어야 하는 재료들의 양을 구하는 문제이다.

입력값은 모두 정수이고,

약을 최소한 1단위 이상은 만들어야 한다.

풀이

완성한 약의 양이 꼭 정수단위일 필요가 없다는 점에 주의해야 한다.

따라서 필요한 재료들의 양을 최대공약수로 나누어

들어가야 하는 재료들의 비를 구했다.

예를 들어 들어가야 하는 3가지 재료의 양이 각각 2 4 6 이라면

최대공약수 2로 나누어 1 2 3 라는 비율을 구한다.

이제 들어가야 하는 재료의 양은 1 2 3 의 정수배인

1 2 3

2 4 6

3 6 8

4 8 10

...

...

과 같이 된다.

(정수배인 이유는 입력되는 재료의 양이 정수이므로)

그런데 문제에서 완성 약을 한 단위 이상 만들어야 한다는 조건이 있으므로

2 4 6 다음부터 검사하면 되는것이다.

여기서 현재 넣은 재료가 3 6 7 이라면

재료추가로 만들 수 있는 값이 위 정수배들 중에서 3 6 8 이므로

약을 완성시키기 위해 0 0 1 만큼의 재료를 더 넣어야 하는 것이다.

최대공약수를 구하는 부분은 유클리드 알고리즘을 사용하였고,

n개 수의 GCD를 구하기 위해 해당 알고리즘을 n-1번 반복하였다.

(관련글 : http://www.tibyte.kr/224)

코드

#include <cstdio>

#include <cmath>

using namespace std;

//GCD계산 (유클리드)

int calcGcd(int n1, int n2)

{

int temp;

if (n1 < n2) {

temp = n1;

n1 = n2;

n2 = temp;

}

while (n2 != 0) {

temp = n1%n2;

n1 = n2;

n2 = temp;

}

return n1;

}

int main(void)

{

int numTry;

scanf("%d",&numTry);

while (numTry--)

{

int numElem;

scanf("%d",&numElem);

int *ideal = new int[numElem];

int *curr = new int[numElem];

int gcd;

double curMul = 0;

double maxMul = 0;

int mul;

//비율값 입력받음

for (int i = 0; i < numElem; i++) 

scanf("%d", &ideal[i]);

//비율값의 gcd계산

gcd = ideal[0];

for (int i = 1; i < numElem; i++) 

gcd = calcGcd(gcd, ideal[i]);

//ideal값 재계산

for (int i = 0; i < numElem; i++)

ideal[i] = ideal[i]/gcd;

//현재넣은값 입력받음

for (int i = 0; i < numElem; i++) {

scanf("%d", &curr[i]);

curMul = (double)curr[i] / ideal[i];

if (curMul >maxMul ) maxMul = curMul;

}

mul = ceil(maxMul);

for (int i = 0; i < numElem; i++) {

ideal[i] *= mul;

printf("%d ", ideal[i] - curr[i]); 

}

printf("\n");

}

return 0;

}

문제 링크 : http://judge.koreatech.ac.kr/problem.php?id=1007

32bit 크기의 정수 N개 (N은 1<=N<100001인 홀수)가 입력으로 주어진다.

하나를 제외한 나머지 수는 모두 짝이 있다. (짝수 번 중복된다.)

예시 

입력 : -1 2 0 -1 2

출력 : 0

입력 : 2 2 2 2 5

출력 : 5

입력 : 2 2 2 2 2

출력 : 2

(2와 2가 짝, 다시 2와 2가 짝이 되면 2 하나가 남는다.)

생각 1

integer범위 길이만큼의 배열을 만들어서 각각 몇 번 나왔는지 센다.

=> 메모리 용량 4GB가 필요하므로 비효율적

생각 2

입력이 들어올 때마다 리스트에 넣는다.

리스트에 넣을 때, 리스트를 선형탐색하여 자신과 같은 수가 있으면 그 수를 뺀다.

마지막에 남은 수를 출력한다.

시간복잡도 : O(n^2)

공간복잡도 : O(n)

생각 3

생각2에서 리스트 대신 트리를 사용한다.

시간복잡도 : O(nlogn)

공간복잡도 : O(n)

생각 4

임의의 정수 a, b, c에 대해 a xor b xor c xor b = a xor c 인 성질을 이용한다.

(어떤 정수에 임의의 정수를 짝수 번 xor 하면 원래대로 돌아온다.)

문제에서 한 수를 제외한 나머지 수들은 모두 짝수 번 반복되므로

들어오는 입력을 모두 xor연산하여 누적시키면 답이 나올 것이다.

시간복잡도 : O(n)

공간복잡도 : O(1)

소스코드 (C++)

#include <cstdio>

using namespace std;

int main(void)

{

int numTry;

scanf("%d",&numTry);

while (numTry--)

{

int leng;

scanf("%d",&leng);

int acc = 0;

int num;

for (int i = 0; i < leng; i++) {

scanf("%d",&num);

acc ^= num;

}

printf("%d\n", acc);

}

return 0;

}