JinWoo Kim

백문이 불여일견, 백견이 불여일행.

5 minute read

1. 설탕 배달

  • 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다.

  • 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

  • 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다.

  • 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

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

입력

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

출력

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

풀이

import sys

N = int(sys.stdin.readline())

arr = []

for i in [x for x in range(0, N // 3 + 1)]:
    for j in [x for x in range(0,N // 5 + 1)]:
        if 3 * i + 5 * j == N:
            arr.append(i+j)

print(min(arr) if arr else -1)

채점 결과

  • 정답

리뷰

  • 3kg짜리를 0,1,2…개일때 5kg짜리를 0,1,2..개 드는 경우를 구한다.
  • 봉투 두개의 무게 합이 N일때, 봉투 개수의 합을 배열에 저장한다.
  • 봉투 개수 합의 최소를 return하고, 만약 봉투 두개의 무게 합이 N이 되는 조합이 없을 경우 -1을 출력한다.

2. 빠른 A+B

  • 본격적으로 for문 문제를 풀기 전에 주의해야 할 점이 있다. 입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다는 점이다.

  • C++을 사용하고 있고 cin/cout을 사용하고자 한다면, cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 개행문자(\n)를 쓰자.

  • 단, 이렇게 하면 더 이상 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다.

  • Java를 사용하고 있다면, Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용할 수 있다.

  • BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다.

  • Python을 사용하고 있다면, input 대신 sys.stdin.readline을 사용할 수 있다.

  • 단, 이때는 맨 끝의 개행문자까지 같이 입력받기 때문에 문자열을 저장하고 싶을 경우 .rstrip()을 추가로 해 주는 것이 좋다.

  • 또한 입력과 출력 스트림은 별개이므로, 테스트케이스를 전부 입력받아서 저장한 뒤 전부 출력할 필요는 없다. 테스트케이스를 하나 받은 뒤 하나 출력해도 된다.

  • 자세한 설명 및 다른 언어의 경우는 이 글에 설명되어 있다.

  • 이 블로그 글에서 BOJ의 기타 여러 가지 팁을 볼 수 있다.

입력

  • 첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다.

출력

  • 각 테스트케이스마다 A+B를 한 줄에 하나씩 순서대로 출력한다.

풀이

import sys

N = int(sys.stdin.readline())
for _ in range(0, N):
    sys.stdout.write(str(sum(list(map(int, sys.stdin.readline().split()))))+'\n')

채점 결과

  • 정답

리뷰

  • 후술할 3번 문제를 풀기 위해, 입력/출력 딜레이를 최소화 시키는 방법을 연습할 겸 풀었던 문제다.

  • sys.stdin.readline()과 sys.stdout.write()를 활용해 최대한 입출력에 걸리는 시간을 줄여보았다.

3. 수 정렬하기 3

  • N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

  • 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

  • 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

풀이

import sys

arr = [0] * 10001

N = int(sys.stdin.readline())

for _ in range(0,N):
    arr[int(sys.stdin.readline())] += 1

for i in range(0,len(arr)):
    if arr[i] != 0:
        cnt = arr[i]
        while cnt > 0:
            sys.stdout.write(str(i)+'\n')
            cnt -= 1

채점 결과

  • 정답

리뷰

  • 이전에 여러번 다룬 정렬문제와 유사해 보이지만, 이번 문제의 핵심은 엄청난 양의 입력 갯수(최대 $10^8$개)이다.

  • 이로 인해 일반적으로 정렬하기 위해 배열에 수를 일일히 저장하는 순간, 모조리 메모리 초과로 탈락하게 된다.

  • 이 문제를 돌파하기 위해서는, 주어지는 수의 범위가 1~10000 사이의 자연수임을 이용해야 한다.

  • [0]으로 초기화한 10001 크기의 배열을 생성하고, 각 숫자가 나올때마다 배열의 해당 인덱스에 저장된 값을 1 더해주는 방식으로 진행한다.

    • 인덱스와 값이 1:1로 매칭된다는 점에서 어찌보면 딕셔너리와 사용법이 비슷하다고 볼수 있을듯 하다.

  • 1만번 반복하는 정도로는 시간, 메모리 모두 초과될 일은 없으므로, 인덱스를 해당 인덱스 값만큼 반복해서 출력해주면 끝.

    • 이때, 한번에 출력시키겠다고 괜히 ''.join()등의 함수를 쓰거나 그 외의 방법으로 한줄의 문자열로 출력시키려는 시도를 하다가는 바로 메모리 초과가 발생한다.

    • 생각해보면, 문자열 하나에 4byte로 잡아도 $4 * 10^8$ byte.

      • 1MB = $10^6$ 바이트인것을 감안할때, 메모리 초과가 나도 전혀 이상하지 않은 크기이다.

4. Hashing

  • APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다.
  • 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다.

  • 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.

  • 이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다.
  • 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, …, z)로만 구성되어있다고 가정하자.
  • 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, …, z에는 26으로 고유한 번호를 부여할 수 있다.
  • 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다.
    • 예를 들어서 문자열 “abba”은 수열 1, 2, 2, 1로 나타낼 수 있다.
  • 해시 값을 계산하기 위해서 우리는 문자열 혹은 수열을 하나의 정수로 치환하려고 한다.
    • 간단하게는 수열의 값을 모두 더할 수도 있다.
    • 해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 M으로 나눠주자.

    • 짜잔! 해시 함수가 완성되었다. 이를 수식으로 표현하면 아래와 같다.

    • $H = \sum_{i=0}^{l-1}{a_i} \mod M $
  • 해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져있다.
  • 다들 비둘기 집의 원리에 대해서는 한 번쯤 들어봤을 것이다$^1$.
  • 그 원리에 의하면 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다.
  • 이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다.

  • 위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니까 조금 더 개선해보자.

  • 어떻게 하면 순서가 달라졌을때 출력값도 달라지게 할 수 있을까? 머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다.
  • 가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다.

  • 이를 수식으로 표현하면 아래와 같다.

    • $ H = \sum_{i=0}^{l-1}{a_ir^i} \mod M $
  • 보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다.

  • 우리가 직접 정하라고 하면 힘들테니까 r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891(놀랍게도 소수이다!!)로 하자.

  • 이제 여러분이 할 일은 위 식을 통해 주어진 문자열의 해시 값을 계산하는 것이다.
  • 그리고 이 함수는 간단해 보여도 자주 쓰이니까 기억해뒀다가 잘 써먹도록 하자.

입력

  • 첫 줄에는 문자열의 길이 L이 들어온다. 둘째 줄에는 영문 소문자로만 이루어진 문자열이 들어온다.

  • 입력으로 주어지는 문자열은 모두 알파벳 소문자로만 구성되어 있다.

출력

  • 문제에서 주어진 해시함수와 입력으로 주어진 문자열을 사용해 계산한 해시 값을 정수로 출력한다.

Small(50점)

  • $1 \le L \le 5$

Large(50점)

  • $1 \le L \le 50$

풀이

import sys

N = int(sys.stdin.readline())

target = sys.stdin.readline().strip()

sum_ = 0
for i in range(0, len(target)):
    sum_ += (ord(target[i])-96) * (31 ** i)

print(sum_ % 1234567891)

채점 결과

  • 정답(100점)

리뷰

  • 처음으로 풀어본 서브태스크 문제다.

  • 이런류의 문제는 100점을 맞는것을 기본 전제로 두라는 말을 들은적이 있기에, Large 케이스를 맞추는것을 기본 전제로 두고 시작했다.

  • 입력받는 값은 모두 영어 소문자로 이루어진 문자열이라 하였으므로, 아스키 코드값으로 변환시켜 96을 빼주면 $a_i$에 해당하는 부분은 구할수 있을것으로 생각했다.

  • 31의 i거듭제곱에 대한 경우, 나올수 있는 최대값이 $31^{26}$인데, 이걸 그냥 깡으로 연산하는것이 맞는지 회의감이 들었지만, 일단 돌려보고 안되면 최적화 하자는 마음가짐으로 그냥 짰다.

  • 그렇게 넣고 돌렸는데..예상 외로 시간 및 메모리 오류가 발생하지 않아 상당히 놀랐다.

    • 심지어 메모리 사용량 30840KB, 시간 72ms로 상당히 난폭한 계산식에 비해 깔끔한 결과였다.

You May Also Enjoy