JinWoo Kim

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

6 minute read

  • 오늘은 다소 난이도가 낮은 문제더라도, 기초를 다진다는 느낌으로 여러 문제를 풀어보았다.

1. 요세푸스 문제 0

  • 요세푸스 문제는 다음과 같다.

    • 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다.
    • 이제 순서대로 K번째 사람을 제거한다.
    • 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.
    • 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
    • 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.
      • 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

  • N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

  • 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

  • 예제와 같이 요세푸스 순열을 출력한다.

풀이

import sys

N, K = list(map(int, sys.stdin.readline().split()))

deq = [x for x in range(1, N + 1)]
arr = []
yosepus = K
string = '<'

for i in range(0, N):
    if len(deq) == 1:
        string += str(deq[0]) + '>'
        break
    else:
        string += str(deq[yosepus-1]) + ', '
        deq.remove(deq[yosepus-1])
        yosepus += K-1
        if yosepus > len(deq) > 1:
            while yosepus > len(deq):
                yosepus -= len(deq)

print(string)

채점 결과

  • 정답

리뷰

  • 인덱스를 K-1씩 증가시키고, 인덱스 범위 초과시 인덱스 범위만큼 인덱스를 감소시키며 하나씩 출력하는 방식을 사용했다.

더 나은 풀이


N, K = map(int, input().split())
l = list(range(1, N+1))
p = list()
i = 0
while l:
    i = (i+K-1) % len(l)
    p.append(str(l.pop(i)))

print('<'+', '.join(p)+'>')

더 나은 풀이법 리뷰

  • 큰 알고리즘의 흐름은 비슷한 편이다.

  • 반복문을 돌리는 횟수에 대하여,

    • 내 풀이에서는 0~N의 횟수를 지정했다.

    • 이 풀이의 경우 수열 l을 pop연산으로 줄여나가는것을 감안하여 l의 길이를 while문의 조건으로 설정했다.

  • 인덱스 범위 초과시 인덱스의 처리 방식에 대하여,

    • 내 풀이에서는 인덱스 + (K-1)을 len(수열)보다 작아질때까지 빼주었다.

    • 이 풀이의 경우, (인덱스+K-1) % len(수열)을 통해 같은 결과를 깔끔하고, 반복문을 사용하지 않으면서 구현했다.

2. 블랙잭

  • 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다.
    • 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다.

  • 블랙잭은 카지노마다 다양한 규정이 있다.

  • 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

  • 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다.

  • 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

  • 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다.

  • 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

  • N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

  • 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다.

  • 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

  • 합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

  • 첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

풀이


import sys
from itertools import permutations
from collections import Counter

N, M = list(map(int, sys.stdin.readline().split()))
card_list = list(map(int, sys.stdin.readline().split()))

c = list(Counter([x+y+z for x,y,z in list(permutations(card_list,3))]).keys())

print(sorted([x for x in c if M-x >= 0])[-1])

채점 결과

  • 정답

리뷰

  • 카드 N장중 3장을 골라 M에 최대한 가까운 합을 만드는 순열을 찾는 문제이다.

  • 카드의 갯수가 3~100 사이이므로, itertools.permutations를 통해 순열을 구했다.

  • 순열을 이루는 숫자들의 합을 리스트로 반환하고, Counter를 통해 중복되는 값들을 제거했다.

  • M에서 최대한 가까운 값 = M-x이 가장 작은 값이므로, M-x가 0이상인 값들을 골라 그중 가장 큰 값(= M-x가 가장 작은 값)을 반환해주었다.

더 나은 풀이


def P(n,m,c):
	t=set()
	for i in range(n-2):
		for o in range(i+1,n-1):
			for p in range(o+1,n):
				s=c[i]+c[o]+c[p]
				if s<=m:
					t.add(s)
					break

	return max([*t])
print(P(*map(int,input().split()),list(sorted(map(int,input().split()))[::-1])))

더 나은 풀이 리뷰

  • print문부터 해석하면, 다음과 같은 구조로 이루어져 있다.

    • P함수로 *args형식으로 다음에 입력될 N,M값을 보낸다.
      • *args는 *다음에 올 파라미터가 몇개일지 모를때 주로 사용된다.
      • 이번에는 무조건 첫줄에 오는 파라미터가 두개이므로, map()함수등과 연계하여 N,M값을 추출하여 P함수로 전송했다.
    • 두번째줄에 입력된 수열을 내림차순으로 정렬하여 P함수의 c값으로 보낸다.

  • P함수를 해석하면 다음과 같다.

    • 0~n-2 범위에서 i, i+1~n-1범위에서 o, o+1~n-2 범위에서 p를 구해 c의 i,o,p번째 값을 더해준 s를 구한다.
      • c는 내림차순이므로, s는 가장 큰값 세개를 더한 값부터 작아지는 형식을 띄게 된다.
    • s값이 m이하인 값을 set()에 저장하여 중복값을 제거하고, 그중 가장 큰 값을 return한다.
      • m이하인 값들중 가장 큰 값 = m에 가장 가까운 값이므로 정답이 된다.

3. 스택

  • 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

  • 명령은 총 다섯 가지이다.

    • push X: 정수 X를 스택에 넣는 연산이다.

    • pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다.
      • 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

    • size: 스택에 들어있는 정수의 개수를 출력한다.

    • empty: 스택이 비어있으면 1, 아니면 0을 출력한다.

    • top: 스택의 가장 위에 있는 정수를 출력한다.
      • 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

  • 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다.

  • 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다.

  • 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

  • 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이(deque 사용)

import sys
from collections import deque

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

stack = deque()

for _ in range(0,N):
    line = list(sys.stdin.readline().split())

    if line[0] == 'push':
        stack.append(line[1])
    elif line[0] == 'pop':
        print(stack.pop() if stack else -1)
    elif line[0] == 'size':
        print(len(stack))
    elif line[0] == 'empty':
        print(0 if stack else 1)
    elif line[0] == 'top':
        print(stack[-1] if stack else -1)

풀이(deque 미사용)

import sys

N = int(sys.stdin.readline())
stack = []

for _ in range(0, N):
    line = list(sys.stdin.readline().split())

    if line[0] == 'push':
        stack.append(line[1])
    elif line[0] == 'pop':
        if stack:
            print(stack[-1])
            del stack[-1]
        else:
            print(-1)
    elif line[0] == 'size':
        print(len(stack))
    elif line[0] == 'empty':
        print(0 if stack else 1)
    elif line[0] == 'top':
        print(stack[-1] if stack else -1)

채점 결과

  • 정답

리뷰

  • 스택 구조를 구현하면 되는 문제였다.

  • 다만, 파이썬은 이미 훌륭한 deque가 있기 때문에 그냥 구현하는건 밋밋해서 deque없이도 한번 구현해보았다.

    • 코드에서 그다지 차이나는 점은 없었으나, 풀이 결과 나타나는 시간은 라이브러리를 안쓴쪽이 20ms정도 빨랐다.

    • 라이브러리를 불러오는데도 추가적으로 시간이 소모되는것 같다.

    • 물론, 라이브러리 불러오는 시간때문에 시간초과된다는 핑계는 어림도 없을것이지만, 나름 흥미로운 결과였다.

다른 풀이 및 리뷰

from sys import stdin

stack = []
next(stdin)
for line in stdin:
    command = line.split()
    if command[0] == 'push':
        stack.append(command[1])
    elif command[0] == 'pop':
        if stack: print(stack.pop())
        else: print(-1)
    elif command[0] == 'size':
        print(len(stack))
    elif command[0] == 'empty':
        if stack: print(0)
        else: print(1)
    elif command[0] == 'top':
        if stack: print(stack[-1])
        else: print(-1)

  • sys 라이브러리에서 stdin만 불러온 후, 어차피 첫줄의 N만큼 줄이 나올것이기에 next(stdin)을 통해 한줄 넘긴다.

  • stdin 객체는 ‘\n’을 기준으로 구분된다.
    • 그렇다고 ‘\n’을 알아서 정리해주지는 않는다.
    • 이번 예제에서는 split()을 통해 알아서 정리된 경우.
  • 나머지 알고리즘은 같으니 생략.
import sys

stack = list()

command = dict(
    push=lambda x: stack.append(x),
    pop=lambda: stack.pop() if stack else -1,
    size=lambda: len(stack),
    empty=lambda: 0 if stack else 1,
    top=lambda: stack[-1] if stack else -1
    )

in_data = sys.stdin.readlines()
for c in in_data[1:]:
    c = c.strip()
    if c[:2] == 'pu':
        command['push'](c.split()[1])
    else:
        print(command[c]())

  • 특이하게도, 딕셔너리에 lambda식을 통해 함수를 구현해두고, 인덱스로 커맨드를 넣는 방식을 통해 명령을 실행하고 있었다.

  • 그냥 이런 방식도 되는구나 싶어 참신함에 선정해 보았다.

3. 이항 계수

  • 자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 $\binom{N}{K}$를 구하는 프로그램을 작성하시오.

입력

  • 첫째 줄에 $N$과 $K$가 주어진다. (1 ≤ $N$ ≤ 10, 0 ≤ $K$ ≤ $N$)

출력

  • $\binom{N}{K}$를 출력한다.

풀이


import sys
from itertools import combinations

N,K = list(map(int,sys.stdin.readline().split()))
print(len(list(combinations([x for x in range(0,N)],K))))

채점 결과

  • 정답

리뷰

  • 조합론에서, 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.
    • (출처 : 위키백과)

  • 쉽게 말해, $_NC_K$ 구하라는 소리다.

  • itertools.combination 활용하여 풀어줬다.

더 나은 풀이

def combine(n, k):
    if k == 0:
        return 1
    if k == n:
        return 1
    if memo[n][k] != -1:
        return memo[n][k]
    return combine(n - 1, k - 1) + combine(n - 1, k)


N, K = [int(x) for x in input().split(' ')]
memo = [[-1 for k in range(K + 1)] for n in range(N+1)]
print(combine(N, K))

더 나은 풀이법 리뷰

  • 재귀함수를 통해 파스칼의 법칙 점화식을 구현하고, 그걸 통해 $_NP_K$를 구했다.

You May Also Enjoy