TIL 23-05-06 백준 알고리즘 - 세준세비

https://github.com/sdoram/Algorithm

https://github.com/sdoram/algorithm_solving_process

GitHub - sdoram/algorithm_solving_process: 알고리즘 풀이 과정 python 파일

 

1. 백준 알고리즘 - 세준세비

 문제점

https://www.acmicpc.net/problem/1524

1524번: 세준세비

 시도해 본 것들

 

첫 코드 작성 

T = int(input())

for _ in range(T):
    N, M = map(int, input().split())
    N_power = sorted(list(map(int, input().split())), reverse=True)
    M_power = sorted(list(map(int, input().split())), reverse=True)
    while len(N_power) != 0 and len(M_power) != 0:
        if N_power[-1] == M_power[-1]:
            M_power.pop()
            continue
        N_power.pop() if N_power[-1] < M_power[-1] else M_power.pop()
    print('S' if len(N_power) != 0 else 'B')

결과를 보고 잘 출력이 되길래 제출 시도 후 ValueError

어디서 터지는 것인지 잘 이해가 안 되는 상태인데 일단 맥거핀으로 생각한 무승부의 경우를 추가 

 

무승부 결과 추가

if len(N_power) == 0 and len(M_power) == 0:
        print('C')
    else:
        print('S' if len(N_power) != 0 else 'B')

여전히 ValueError발생

 

입력 바꿔보기 

N_power = sorted(
        list(map(int, sys.stdin.readline().lstrip().rstrip().split())))
    M_power = sorted(
        list(map(int, sys.stdin.readline().lstrip().rstrip().split())))

혹시 공백이 어떤식으로 섞여 들어갈까 싶어서 lstrip(), rstrip()으로 공백 제거했지만 여전히 에러 발생  

방법을 도저히 모르겠어서 문제만 보고 있을 때 '각 테스트 케이스는 줄 바꿈으로 구분되어 있다.' 문구 발견

 

입력 테스트하기 

테스트 케이스 개수 입력 후 바로 공백으로 줄바꿈 시도시 드디어 ValueError발생

import sys
T = int(input())
for _ in range(T):
    # 테스트 케이스를 줄바꿈으로 구분 입력
    input()
    N, M = map(int, input().split())
    # lstrip(), rstrip()으로 좌우 공백 제거
    N_power = sorted(
        list(map(int, sys.stdin.readline().lstrip().rstrip().split())))
    M_power = sorted(
        list(map(int, sys.stdin.readline().lstrip().rstrip().split())))
    # N과 M이 0이 아닐때까지
    while N and M:
        if N_power[0] == M_power[0]:
            M_power.pop(0)
            M -= 1
            continue
        if N_power[0] < M_power[0]:
            N_power.pop(0)
            N -= 1
        else:
            M_power.pop(0)
            M -= 1
    print(f'S :{N_power}, B :{M_power}')
    print('S' if N != 0 else 'B')

줄바꿈을 생각하지 못하고 특정 케이스에서 로직이 작동하지 않는다는 생각에 코드만 바꿨다. 하지만 지금 보면 코드는 다르지만 로직은 다를 게 없는 상태 같다. 

그리고 input()을 각 테스트의 시작 지점에 추가하자 제대로 통과했다. 

 해결 방법

수정한 로직 

import sys
T = int(input())
for _ in range(T):
    # 테스트 케이스를 줄바꿈으로 구분 입력
    input()
    N, M = map(int, input().split())
    # lstrip(), rstrip()으로 좌우 공백 제거
    N_power = sorted(
        list(map(int, sys.stdin.readline().lstrip().rstrip().split())))
    M_power = sorted(
        list(map(int, sys.stdin.readline().lstrip().rstrip().split())))
    # N과 M이 0이 아닐때까지
    while N and M:
        if N_power[0] == M_power[0]:
            M_power.pop(0)
            M -= 1
            continue
        if N_power[0] < M_power[0]:
            N_power.pop(0)
            N -= 1
        else:
            M_power.pop(0)
            M -= 1
    # print(f'S :{N_power}, B :{M_power}')
    print('S' if N != 0 else 'B')

메모리: 40416 KB, 시간: 3820 ms

 

첫 번째 로직

T = int(input())

for _ in range(T):
    input()
    N, M = map(int, input().split())
    # pop으로 가장 작은 수를 꺼내기 쉽도록 sorted(reverse=True)
    N_power = sorted(list(map(int, input().split())), reverse=True)
    M_power = sorted(list(map(int, input().split())), reverse=True)
    while len(N_power) and len(M_power):
        if N_power[-1] == M_power[-1]:
            M_power.pop()
            continue
        N_power.pop() if N_power[-1] < M_power[-1] else M_power.pop()
    print('S' if len(N_power) else 'B')

메모리: 40416 KB, 시간: 328 ms

이 코드가 가독성이나 시간 복잡도 모두 좋은 것 같다.  

 알게 된 점

오늘도 문제를 잘 읽자가 되어버렸다. 

 

1. 백준 알고리즘 - 이항계수 1

 문제점

https://www.acmicpc.net/problem/11050

11050번: 이항 계수 1

 

 시도해 본 것들

문제를 이해하기 위해 수식 찾아보기 

총 개수 N, 고르는 개수 K일 때 
N! / K!(N-K)!

수식은 N개에서 K 개씩 고르는 경우 가질 수 있는 경우의 수를 구하는 수식이다. 

 분자가 N 팩토리얼

분모가 K팩토리얼 * (N-K) 팩토리얼

 

팩토리얼 함수로 만들기 

def factorial(num):
    number = 1
    for n in range(1, num+1):
        number *= n
    return number

팩토리얼을 사용하기 위한 math나 재귀함수? 가 있는 것 같지만 math는 아직 사용할 때가 아닌 것 같고, 재귀함수는 아직 몰라서 사용할 수 없다. 

 

 해결 방법

# 팩토리얼 구하기 함수
def factorial(num):
    number = 1
    for n in range(1, num+1):
        number *= n
    return number


N, K = map(int, input().split())
n = factorial(N)
r = factorial(K)
n_r = factorial(N-K)
print(n // (r*n_r))

경우의 수를 구하는 것 자체는 먼저 수식을 찾아보고 그것을 구현해서 어렵지 않게 가능했다. 

 알게 된 점

이 문제는 수식을 만들기만 하면 되는 문제로 어렵지 않았지만, 이제 이 수식을 활용해야 할 단계가 오면 수식을 구현하는 것은 당연하고 수식 자체에 대한 이해도 챙겨야 할 것 같다. 

수식을 코드로 만드는 문제를 접하기 시작하고 복잡한 알고리즘을 효율적으로 만들려면 수식의 필요성이 느껴지는 만큼 알고리즘의 형태로도 수식을 꾸준히 접해야겠다.