Program Artist를 꿈꾸는 Blog

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

전체 코드(Java)

import java.io.*;
import java.math.BigInteger;

class Main {
    public static void main(String[] args) throws IOException {
        BigInteger[] arr = new BigInteger[91];

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        arr[0] = BigInteger.valueOf(0);
        arr[1] = BigInteger.valueOf(1);

        for (int i = 2; i <= n; i++) {
            arr[i] = arr[i - 1].add(arr[i - 2]);
        }

        System.out.println(arr[n]);
    }
}

풀이

간단하게 DP(Dynamic Programming)을 이용하여 풀이하였다.

• 풀이 원리는 메모이제이션(memoization)의 기본 활용으로, 피보나치 수열의 값은 이전 두 항의 값으로 결정된다.
• 이러한 원리를 이용하여 연산 값을 별도의 배열에 저장하여 다음 계산에 활용하였다.
• 일반적인 재귀 함수를 통해 피보나치 수를 구하면 시간 초과가 발생한다. 따라서 for 문을 이용하여 풀이하였다.
• n이 90일 때 최대값이 long의 범위 안에 있으므로, long을 활용할 수 있지만, 더 큰 값에 대한 계산과 응용을 고려하여 BigInteger를 사용해보았다.

초기의 두 항이 결정되면, 나머지 항은 for 문을 통해 채울 수 있게 된다.

따라서 arr의 0번째, 1번째 인덱스를 할당해주고 for 문에서 입력한 n까지의 배열을 모두 채운 뒤, n번 인덱스를 출력하면 된다.

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

전체 코드(Java)

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int ans = -1;
        int N = Integer.parseInt(br.readLine());

        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(list);

        for (int i = list.size() - 1; i >= 0; i--) {

            int target = list.get(i) * (list.size() - i);

            if (ans < target) {
                ans = target;
            }
        }

        System.out.println(ans);
    }
}

풀이

1. 그리디 알고리즘을 이용한 간단한 문제였다. 문제 풀이의 핵심은 두 가지다.

- 로프의 무게 순으로 리스트를 정렬

- 로프의 개수를 하나씩 늘려가며 최대로 버틸 수 있는 무게를 구함

2. 코드는 크게 세 부분으로 구분된다.

1) 입력을 처리하는 부분

- BuffredReader와 Integer.parseInt를 사용한 일반적인 처리

2) 리스트를 정렬하는 부분

- Collections.sort를 이용한 정렬

- 코드에서는 오름차 순 정렬을 사용하였지만, 내림차 순 정렬을 사용하는 것이 더 간단할 듯 함

3) 로프의 개수를 늘려가며 최대 값을 비교하는 부분

- 오름차 순으로 정렬된 리스트에서 버티는 무게가 가장 큰 로프부터 하나씩 추가

- 로프의 개수가 증가하면 버틸 수 있는 최대 무게는 해당 인덱스 * 추가된 로프의 개수

3. 예시

- 로프의 무게가 5, 25, 15로 주어졌을 때 해결 과정은 아래와 같음

1) 값을 받아 리스트에 넣고, 리스트가 정렬되어 5 15 25 순으로 됨

2) 무게가 가장 큰 로프(마지막 인덱스)인 25가 추가되고, 현재 로프의 개수는 1개이므로, 최대 무게는 25 * 1

3) 무게가 두번째로 큰 로프인 15가 추가되고, 현재 로프의 개수는 2개이므로 15 * 2 > 25 * 1이므로, 최대 무게는 30

4) 무게가 세번째로 큰 로프인 5이 추가되고, 현재 로프의 개수는 3개이므로 5 * 3 < 15 * 2이므로, 최대 무게는 30

5) 따라서 최대 무게는 30

4. 최적화

- 현재 시간은 400ms 이상으로 상당히 느린 결과를 보임

- 정렬 과정을 제거하고, 인덱스 접근을 효율적으로 변경하여 시간을 줄일 수 있을 것으로 예상됨

문제

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
• 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 

아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.

1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다. 

위 예의 괄호 표현은 그림 위에 주어져 있다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다. 

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

전체 코드(Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();

        int ans = 0;
        int size = 0;

        for (int i = 0; i < s.length() - 1; i++) {
            char c = s.charAt(i);
            char n = s.charAt(i+1);

            if ('(' == c && ')' == n) {
                ans += size;
                i++;
                continue;
            }

            if ('(' == c) {
                ans++;
                size++;
            } else if (')' == c) {
                size--;
            }
        }

        System.out.println(ans);
    }
}

풀이

1. 처음에는 예제의 입력과 출력을 살펴보며 규칙성을 찾고자 하였다.

1) 레이저가 나올 때 그 앞의 '(' 개수 만큼 쇠 막대기의 총 개수가 증가한다는 것을 알았다

2) 막대를 자를 때 추가되는 개수와 기존 막대의 개수를 고려하여 여는 괄호가 등장할 때 마다 총 합의 개수를 1씩 늘려줘야 한다

- 쇠막대를 한 번 자르면 기존 1개의 막대 + 추가 1개의 막대로 생각할 수 있다

- 이 상태에서 한 번 더 자르면 기존 2개의 막대 + 추가 1개의 막대로 생각할 수 있다

  - 레이저는 '(' 다음 ')'이 나오게 되므로, 매 루프 시 현재 인덱스의 문자와 다음 인덱스의 문자를 검사하여 레이저를 처리하였다.

  - 이 부분은 ')'가 등장할 때 예외 처리를 통해 심플하게 구성할 수 있을 듯 하다.

- s.length() - 1 까지 for 루프를 도는 이유는, 어차피 마지막은 닫는 괄호로 끝날 것이기 때문이다. 마지막 닫는 괄호는 결과에 영향을 주지 않는다.

2. 규칙성을 찾은 다음에는 스택 자료구조를 사용하면 간단하게 해결될 것으로 보였다.

- 하지만 코드를 구상하면서 스택의 사이즈만을 사용하는 것을 깨닫게 되어 굳이 스택을 구현하지는 않았다.

- 대신 현재의 여는 괄호 개수를 기록할 변수인 'size'를 이용하였다

3. 상기의 규칙성에 따라 기본적인 문법 만을 이용하여 구현하였다. 

문제

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. (0 < A,B < 1010000)

출력

첫째 줄에 A+B를 출력한다.

전체 코드(Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		BigInteger A = new BigInteger(st.nextToken());
		BigInteger B = new BigInteger(st.nextToken());
		
		System.out.println(A.add(B));
		
		br.close();
	}
}

풀이

• BigInteger를 사용하여 간단하게 해결
  • StringTokenizer로 입력받은 문자열을 공백 기준으로 자름
  • BigInteger로 계산(add 메소드)
• 개선점 : char 형 배열을 이용해 계산하면 속도가 훨씬 빨라질 것으로 추정
  • 현재 속도는 260ms로 매우 느린편
  • 하지만 코드의 생산성에서 볼 때 이 코드가 매우 간결하고 좋다고 할 수 있음

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

전체 코드(Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		if (N == 4 || N == 7) System.out.println("-1");
		else if (N % 5 == 0) System.out.println(N / 5);
		else if (N % 5 == 1 || N % 5 == 3) System.out.println(N / 5 + 1);
		else if (N % 5 == 2 || N % 5 == 4) System.out.println(N / 5 + 2);
		
		br.close();
	}
}

풀이

• 상당히 고생했던 문제
  • "-1"이 출력되는 상황을 제대로 파악하지 못함
  • 알고보니, -1이 출력되는 경우는 N이 4거나 7일 때 두 가지 경우만 존재
• 나머지에 대한 출력은 N % 5를 이용한 모든 경우의 수를 고려
  • N % 5에서 나올 수 있는 경우의 수는 0, 1, 2, 3, 4
  • 각각의 상황에 대한 출력
• 처음에는 System.exit(0) 메소드를 이용해서 프로그램을 종료하였으나, 시간이 느리게 측정
  • 이 부분을 없애는 쪽으로 바꿨더니 30~40ms의 속도 개선이 있었음
  • 또한 System.exit(0) 전에 bw.write를 사용하는 경우 메시지가 출력되지 않고 종료되는 현상 발생 가능
• System.out.println과 bw.write의 속도 차이는 적은 출력 개수에서는 별로 차이가 나지 않음