무지개 달팽이

Q. 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력.

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력.

첫째 줄에 정답을 출력한다.

※ " 유셩장 " 블로그를 참고했다.

숫자를 임시 저장하기 위한 변수 tmp를 반복문에 들어가기 전에 초기화 해주지 않았다.

그 결과 다른 곳을 삽질하느라 오답이 많았다.

// 취소값을 만들기 위해 문자 - 전까지 숫자들을 더해준다. !

#include <iostream>
#include <cstring>

using namespace std;

int main() {
	int i, j, tmp, sum, len, ans;
	int num[50] = {0, };
	char s[51];
	
	cin >> s;
	
	len = strlen(s);
	
	j = 0;
	sum = 0; tmp = 0;
	
	for (i = 0; i < len; i++) {
		if (s[i] == '+') {
			sum += tmp;
			tmp = 0;
		} else if (s[i] == '-') {
			sum += tmp;
			num[j] = sum;
			j++;
			sum = 0;
			tmp = 0;
		} else {
			tmp *= 10;
			tmp += (s[i] - '0');
		}
	}
	
	sum += tmp;
	num[j] = sum;
	
	ans = num[0];
	
	for (i = 1; i < 50; i++) {
		ans -= num[i];
	}
	
	cout << ans << endl;
	
	return 0;
}

Q. 아래 예제와 같이 고양이를 출력하시오.

입력.

없음.

출력.

고양이를 출력한다.

문자열을 여러 줄 출력하는 방법을 사용하였다.

※  \ ( 백슬래시 ) 앞에 " 혹은 ' 가 있으면, 확장 문자 ( \\ ) 를 사용하지 않아도 정상적으로 출력 된다.

print("""\    /\\
 )  ( ')
(  /  )
 \(__)|""")

※ 특수 문자를 사용하지 않으면, 첫 따옴표 앞에 r을 붙여서 날 문자열로 바꿔준다.

print(r"""\    /\
 )  ( ')
(  /  )
 \(__)|""")

Q. ACM-ICPC 인터넷 예선, Regional, 그리고 World Finals까지 이미 2회씩 진출해버린 kriii는 미련을 버리지 못하고 왠지 모르게 올 해에도 파주 World Finals 준비 캠프에 참여했다.

대회를 뜰 줄 모르는 지박령 kriii를 위해서 격려의 문구를 출력해주자.

입력.

본 문제는 입력이 없다.

출력.

두 줄에 걸쳐 "강한친구 대한육군"을 한 줄에 한 번씩 출력한다.

두 줄 이상의 문자열을 출력하는 방법을 사용한다.

python은 문자열을 큰 따옴표나 작은 따옴표를 삼중으로 감싸준다.

print('''강한친구 대한육군
강한친구 대한육군''')

Q. 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다.

상근이는 모든 방법을 동원해보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다.

이런 상근이를 불쌍하게 보던, 창영이는 자신이 사용하는 방법을 추천해 주었다.

바로 "45분 일찍 알람 설정하기"이다.

이 방법은 단순하다. 원래 설정되어 있는 알람을 45분 앞서는 시간으로 바꾸는 것이다. 어차피 알람 소리를 들으면, 알람을 끄고 조금 더 잘 것이기 때문이다. 이 방법을 사용하면, 매일 아침 더 잤다는 기분을 느낄 수 있고, 학교도 지각하지 않게 된다.

현재 상근이가 설정한 알람 시각이 주어졌을 때, 창영이의 방법을 사용한다면, 이를 언제로 고쳐야 하는지 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 두 정수 H와 M이 주어진다. (0 ≤ H ≤ 23, 0 ≤ M ≤ 59) 그리고 이것은 현재 상근이가 설정한 놓은 알람 시간 H시 M분을 의미한다.

입력 시간은 24시간 표현을 사용한다. 24시간 표현에서 하루의 시작은 0:0(자정)이고, 끝은 23:59(다음날 자정 1분 전)이다. 시간을 나타낼 때, 불필요한 0은 사용하지 않는다.

출력.

첫째 줄에 상근이가 창영이의 방법을 사용할 때, 설정해야 하는 알람 시간을 출력한다. (입력과 같은 형태로 출력하면 된다.)

기본적으로 입력 받은 시간 중 변수 M에서 45를 뺀 결과를 구해야 한다.

여기서 주의해야 하는 곳은 (1-1) 변수 M의 값이 45 보다 작은 경우, (1-2)  변수 M에서 값을 빼기 위해, 변수 H의 값에서 1을 뺀 값이 0보다 작아지는 경우 이다.

위 두 경우를 조건문으로 한다.

#include <stdio.h>

int main(void) {
	int h, m;

	scanf("%d %d", &h, &m);

	if (m > 45)
		m -= 45;
	else {
		if (h == 0)
			h += 24;
		h--;
		m += 60;
		m -= 45;
	}

	printf("%d %d\n", h, m);
	
	return 0;
}

Q. 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력.

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력.

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

기본 베이스는 DFS 알고리즘을 이용했다.

우선 입력받은 컴퓨터의 번호 쌍을 바탕으로 인접 행렬을 구현한 뒤, 그리고 DFS 알고리즘에 적용하였다.

이 문제는 1번 컴퓨터로부터 웜 바이러스에 걸릴 수 있는 컴퓨터 수를 구하는 것이기 때문에, 

위 알고리즘에서 방문한 노드의 수 - 1 을 해주어야 한다.

#include <stdio.h>

#define SIZE 101

int visit[SIZE];
int a[SIZE][SIZE];

void dfs(int start, int n) {

    if (visit[start] == 1)
        return;
    
    visit[start] = 1;

    for (int i = 0; i <= n; i++) {
        if (a[start][i] == 1 && visit[i] != 1)
            dfs(i,n);
    }
}

int main(void) {
    int n, e, x, y, ans;

    scanf("%d", &n);
    scanf("%d", &e);

    while(e--) {
        scanf("%d %d", &x, &y);

        a[x][y] = 1; a[y][x] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i][j] != 1)
                    a[i][j] = 0;
            }
        }
    }
    
    dfs(1, n);

    ans = 0;

    for (int i = 2; i <= n; i++) {
        if (visit[i] == 1)
            ans++;
    }
    printf("%d", ans);
    
    return 0;
}

Q. 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 동준이는 레벨을 난이도 순으로 배치했다. 하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다.

이 문제를 해결하기 위해 동준이는 특정 레벨의 점수를 감소시키려고 한다. 이렇게해서 각 레벨을 클리어할 때 주는 점수가 증가하게 만들려고 한다.

각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구하는 프로그램을 작성하시오. 점수는 항상 양수이어야 하고, 1만큼 감소시키는 것이 1번이다. 항상 답이 존재하는 경우만 주어진다. 정답이 여러 가지인 경우에는 점수를 내리는 것을 최소한으로 하는 방법을 찾아야 한다.

입력.

첫째 줄에 레벨의 수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개 줄에는 각 레벨을 클리어하면 얻는 점수가 첫 번째 레벨부터 마지막 레벨까지 순서대로 주어진다. 점수는 20,000보다 작은 양의 정수이다.

출력.

첫째 줄에 점수를 몇 번 감소시키면 되는지 출력한다.

레벨이 올라갈수록 받을 수 있는 점수도 커지도록, 입력받은 수를 수정하는 문제이다.

즉, 중요한 것은 낮은 레벨의 점수가 높은 레벨의 점수보다 무조건 작아야 한다는 것이다.

문제에서 점수는 항상 양수이고, 항상 답이 존재한다고 하였으니까 arr[i] <= i + 1 인 경우는 없다.

그러므로 점수 배열 ( arr ) 에서 arr[i] > arr[i+1] 이 TRUE인 경우에만,

arr[i] 와 arr[i + 1] - 1의 차만큼 답에 더해주고, arr[i]의 값을 arr[i + 1] - 1으로 교체해주는 반복문을 만들어 준다.

#include <stdio.h>

int MAX(int a, int b)
{
    int max;

    if (a >= b)
        max = a;
    else
        max = b;
    
    return max;
}

int main(void)
{
    int n, ans = 0;

    scanf("%d", &n);
    
    int arr[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    for (int i = n - 2; i > -1; i--)
    {   

        if (arr[i] >= arr[i+1]) {

            ans += arr[i] - (arr[i+1]-1);

            arr[i] = arr[i+1]-1;
        }

    }

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

    return 0;
}

Q. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력.

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력.

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

11053 번과 유사한 문제이다. 그래서 같은 코드를 제출하였더니, 시간 초과가 났다.

해결하기 위해 LIS 알고리즘에 대해 구글링해 본 결과, 수열의 크기가 전의 문제보다 더 크다는 점이 문제점이라는 것을 알아 냈다.

( ※ 참고 블로그 : https://jason9319.tistory.com/113 )

위 블로그를 통해 공부한 결과는 아래와 같다.

이 문제는 LIS 알고리즘을 이분 탐색의 방향으로 봐야 한다.

우선 특정 수열의 값을 정렬할 배열을 새로 하나를 만들어 주어야 한다.  위 블로그에서는 벡터를 이용하였는데, c언어를 사용하기 위해 stack 을 이용하였다.

이제 반복문을 사용하여, 수열의 값이 stack[top]의 값과 비교하는 과정을 거친다.

1. 수열의 값 < stack[top] 이면, 수열의 값보다 ① 크면서 ② 그 중에서 가장 작은 수와 자리를 교체해주는 lower_bound를 해준다.

2. 수열의 값 > stack[top] 이면, push 해준다.

3. 수열의 값 == stack[top] 이면, 이 과정을 뛰어 넘는다. ( = continue )

#include <stdio.h>

#define STACK_SIZE 1000000

int stack[STACK_SIZE];
int top = -1;

int isEmpty()
{
    if (top < 0)
        return 1;
    else
        return 0;
}

int isFull()
{
    if (top >= STACK_SIZE)
        return 1;
    else
        return 0;
}

void push(int x)
{
    if (isFull() == 0)
        stack[++top] = x;
}

int pop()
{
    if(isEmpty() == 0)
        return stack[top--];
}

int main(void)
{
    int n, tmp;

    scanf("%d", &n);

    int arr[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    push(arr[0]);

    for (int i = 1; i < n; i++)
    {
        if (stack[top] < arr[i]) 
            push(arr[i]);
        else if (stack[top] < arr[i])
            continue;
        else
        {   
            for (int j = top; j > -1; j--)
            {   
                if (arr[i] > stack[j])
                    break;

                tmp = j;
            }

            stack[tmp] = arr[i];
        }

    }
    
    printf("%d ", top + 1);
    
    return 0;    
}

Q. KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.

예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.

3 7 5 2 6 1 4

아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.

3 7 4 5 2 6 1

이제, 7번 아이를 맨 뒤로 옮긴다.

3 4 5 2 6 1 7

다음 1번 아이를 맨 앞으로 옮긴다.

1 3 4 5 2 6 7

마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.

1 2 3 4 5 6 7

위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다. 따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.

N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

입력.

첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

출력.

첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

최소 횟수로 아이들을 이동시켜서 번호 순서대로 줄을 세우는 문제이다.

번호 순서대로라고 하는 것은 오름차순으로 정렬하는 것과 같다. 이때, 유용하게 사용될 알고리즘이 있다.

바로 " 최장 증가수열 (= LIS 알고리즘) " 이다.

위 알고리즘은 한 수열에서 가장 긴 증가 수열의 길이를 구할 수 있다. 예를 들어, 10 50 30 40 이라는 수열이 있다고 하면, 가장 긴 증가 수열은 10 50 30 40 이다. 즉, LIS 값은 3이다.

이 문제에 적용해 본다면, 그 증가 수열에 해당하지 않는 나머지 수를 배열하면 되므로

 " N - LIS 알고리즘 결과 값 "

이 답이 되겠다.

※ LIS 알고리즘의 기본 예제가 되는 문제는 백준11053 번이다.

#include <stdio.h>

int main(void)
{
    int n, tmp = 0;

    scanf("%d", &n);

    int arr[n], dp[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    for (int i = 0; i < n; i++)
    {   
        dp[i] = 1;

        for (int j = 0; j < i; j++)
        {
            if (arr[i] > arr[j])
            
            	// 아래는 arr의 원소 값보다 작은 원소 값이 모두 count 되지 않도록 하는 조건문
                if (dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;
        }

        if (tmp < dp[i])
            tmp = dp[i];
    }

    printf("%d", n - tmp);
    
    return 0;
}