TIL 코딩공장

백준 파이썬 공부 2025.09.03
11729번 하노이 탑 이동 순서 (골드 5)

1. 문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 
각 원판은 반경이 큰 순서대로 쌓여있다. 
이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 
단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

<그림 생략>

2. 입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

3. 출력
첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 
두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 
이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다

4. 문제 풀이
전형적인 재귀문제의 대표격인 하노이 탑이다.

>>코드

def CountHanoi(n):
    if n == 1:
        return 1
    else:
        return CountHanoi(n-1)*2 + 1

def PrintHanoi(a, b, n):
    if n == 1:
        print(a, b)
    else:
        c = 6-a-b
        PrintHanoi(a, c, n-1)
        print(a, b)
        PrintHanoi(c, b, n-1)
        
    
n = int(input())
print(CountHanoi(n))
PrintHanoi(1, 3, n)

5. 문제 링크
https://www.acmicpc.net/problem/11729

백준 파이썬 공부 2025.03.31
2805번 나무 자르기 (실버 2)

1. 문제
상근이는 나무 M미터가 필요하다. 
근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 
정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 
상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 
먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 
높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 
그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 
따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다.
 
예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 
상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 
상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 
절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 
이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. 
(1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 
나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 
상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 
높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

3. 출력
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

4. 문제 풀이
전형적인 이분탐색 문제로서
start를 0 end를 max(tree) 즉 나무 중 가장 높이가 큰 나무 길이로 해놓고,
높이를 이분탐색 해가면서 자를 나무의 높이를 찾아가는 방식으로 실시한다.
다만, 필요한 나무의 길이인 m이 딱 나오지 않을 경우도 있기 때문에
필요한 나무의 길이보다 자른 총 나무의 길이가 길 때, 
자를 나무의 길이를 매번 저장해 놓으면서 갱신하는 방식을 필요로 한다.

>>> 코드

import sys

n, m = map(int, sys.stdin.readline().strip().split())
tree = list(map(int, sys.stdin.readline().strip().split()))

start = 0
end = max(tree)
while start <= end:
    mid = (end + start) // 2
    
    length = 0
    for i in range(n):
        if tree[i] > mid:
            length += tree[i] - mid
    if length >= m:
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)

5. 문제 링크
https://www.acmicpc.net/problem/2805

20240130 백준 C언어 공부
11021번 A+B - 7

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

2. 입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (0 < A, B < 10)

3. 출력
각 테스트 케이스마다 "Case #x: "를 출력한 다음, A+B를 출력한다. 
테스트 케이스 번호는 1부터 시작한다.

>>>코드

# include <stdio.h>
int main(void){
    int n, a, b;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d %d", &a, &b);
        printf("Case #%d: %d\n", i, a+b);
    }
    return 0;
}

>>>문제링크
https://www.acmicpc.net/problem/11021

20240323 백준 파이썬 공부
1003번 피보나치 함수

1. 문제
다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

- fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
- fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
- 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
- fibonacci(0)은 0을 출력하고, 0을 리턴한다.
- fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
- 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
- fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. 
N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. 
N은 40보다 작거나 같은 자연수 또는 0이다.

3. 출력
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

>>>코드

for _ in range(int(input())):
    n = int(input())
    zero = [1, 0]
    one = [0, 1]
    if n >= 2:
        for i in range(n-1):
            zero.append(zero[-1]+zero[-2])
            one.append(one[-1]+one[-2])
    print(zero[n], one[n])

>>> 해설
이 문제에서 중요한 것은 피보나치 수를 출력하는 것이 아니라
피보나치 수를 계산할때 0과 1이 출력되는 횟수를 구하는 것이다.
0과 1이 출력되는 수 또한 n-1과 n-2에서 0과 1이 출력되는 횟수를 더한 것이다.

따라서 초기 n이 0과 1일 경우의 0과 1이 출력 되는 횟수를 저장해 놓고,
2부터 n까지 출력 횟수를 더해가면서 n일때 출력되는 횟수를 뽑았다.

다만 이건 다이나믹 프로그래밍(DP)를 이용한 방법이 아니다.
그래서 다른 방식을 해보자

>>> 코드

zero = [1, 0]
one = [0, 1]
for _ in range(int(input())):
    n = int(input())
    if n > len(zero)-1: # n이 저장된 출력횟수의 범위(len(zero)-1) 보다 클 때
        for i in range(n-len(zero)+1): # 그 이후의 범위부터 더해주기 
            zero.append(zero[-1]+zero[-2])
            one.append(one[-1]+one[-2])
    print(zero[n], one[n])

>> 해설
이전의 계산한 출력 횟수를 이후의 케이스에도 사용할 수 있도록 바꾸어 보았다.

조금 빨라지긴했다. 

>>>문제 링크

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

20240322 백준 파이썬 공부
15829번 Hashing

1. 문제
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

해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져있다. 
다들 비둘기 집의 원리에 대해서는 한 번쯤 들어봤을 것이다. 
그 원리에 의하면 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다. 
이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다. 
위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 
그러니까 조금 더 개선해보자.

어떻게 하면 순서가 달라졌을때 출력값도 달라지게 할 수 있을까? 
머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다. 
가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다. 
이를 수식으로 표현하면 아래와 같다.
 
H = sum_{i=0}^{l-1}{a_ir^i} mod M

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

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

2. 입력
첫 줄에는 문자열의 길이 L이 들어온다. 둘째 줄에는 영문 소문자로만 이루어진 문자열이 들어온다.
입력으로 주어지는 문자열은 모두 알파벳 소문자로만 구성되어 있다.

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

>>>코드

n = int(input()) # 문자열의 길이
m = input() # 문자열 입력 받기
r = 31 # 26보다 큰 소수
M = 1234567891 # 적당히 크면서 31(r)과 서로소인 수(나누어줄 수)
result = 0 # 해시 함수의 결과값
# 해시 함수 (자릿수까지 알 수 있는 경우)
for i in range(n):
    result += ((ord(m[i]) - 96) * (r**i))
print(result % M) # 출력

>>>해설
문제 이해를 잘 하면 코드 짜는 것은 쉬운 문제이다.
1) 문자열 길이 입력받고
2) 문자를 입력 받은 후
3) 문자에 숫자를 대입하여 소수인 31를 순서만큼 거듭제곱한 수와 곱하기
4) 3)을 문자 전체에 시행하여 다 더해주기
5) 다 더해준 값을 소수인 31과 서로소이면서 적당히 큰 수인  1234567891로 나누기
6) 해당 값 출력

>>>문제링크
https://www.acmicpc.net/problem/15829

20240125 백준 C언어 공부
2480번 주사위 세개

1. 문제
1에서부터 6까지의 눈을 가진 3개의 주사위를 던져서 다음과 같은 규칙에 따라 상금을 받는 게임이 있다.

1) 같은 눈이 3개가 나오면 10,000원+(같은 눈)×1,000원의 상금을 받게 된다.
2) 같은 눈이 2개만 나오는 경우에는 1,000원+(같은 눈)×100원의 상금을 받게 된다.
3) 모두 다른 눈이 나오는 경우에는 (그 중 가장 큰 눈)×100원의 상금을 받게 된다.

예를 들어, 3개의 눈 3, 3, 6이 주어지면 상금은 1,000+3×100으로 계산되어 1,300원을 받게 된다. 
또 3개의 눈이 2, 2, 2로 주어지면 10,000+2×1,000 으로 계산되어 12,000원을 받게 된다. 
3개의 눈이 6, 2, 5로 주어지면 그중 가장 큰 값이 6이므로 6×100으로 계산되어 600원을 상금으로 받게 된다.

3개 주사위의 나온 눈이 주어질 때, 상금을 계산하는 프로그램을 작성 하시오.

2. 입력
첫째 줄에 3개의 눈이 빈칸을 사이에 두고 각각 주어진다.

3. 출력
첫째 줄에 게임의 상금을 출력 한다.

>>>코드

# include <stdio.h>
int main(void){
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    if (a == b && b == c)
        printf("%d", 10000 + a*1000);
    else if (a == b)
        printf("%d", 1000 + a*100);
    else if (b == c)
        printf("%d", 1000 + b*100);
    else if (c == a)
        printf("%d", 1000 + c*100);
    else if (a > b && a > c)
        printf("%d", a*100);
    else if (b > a && b > c)
        printf("%d", b*100);
    else if (c > a && c > b)
        printf("%d", c*100);
    return 0;
}

>>>문제링크
https://www.acmicpc.net/problem/2480

20240122 백준 C언어 공부
14681번 사분면 고르기

1. 문제
흔한 수학 문제 중 하나는 주어진 점이 어느 사분면에 속하는지 알아내는 것이다. 
사분면은 아래 그림처럼 1부터 4까지 번호를 갖는다. "Quadrant n"은 "제n사분면"이라는 뜻이다.

<그림>

예를 들어, 좌표가 (12, 5)인 점 A는 x좌표와 y좌표가 모두 양수이므로 제1사분면에 속한다. 
점 B는 x좌표가 음수이고 y좌표가 양수이므로 제2사분면에 속한다.

점의 좌표를 입력받아 그 점이 어느 사분면에 속하는지 알아내는 프로그램을 작성하시오. 
단, x좌표와 y좌표는 모두 양수나 음수라고 가정한다.

2. 입력
첫 줄에는 정수 x가 주어진다. (−1000 ≤ x ≤ 1000; x ≠ 0) 
다음 줄에는 정수 y가 주어진다. (−1000 ≤ y ≤ 1000; y ≠ 0)

3. 출력
점 (x, y)의 사분면 번호(1, 2, 3, 4 중 하나)를 출력한다.

>>>코드

# include <stdio.h>
int main(void){
    int x, y;
    scanf("%d", &x);
    scanf("%d", &y);
    if (x>0 && y>0)
        printf("%d", 1);
    else if (x<0 && y>0)
        printf("%d", 2);
    else if (x<0 && y<0)
        printf("%d", 3);
    else if (x>0 && y<0)
        printf("%d", 4);
    return 0;
}

>>>문제 링크
https://www.acmicpc.net/problem/14681

20240121 백준 C언어 공부
2753번 윤년

1. 문제
연도가 주어졌을 때, 윤년이면 1, 아니면 0을 출력하는 프로그램을 작성하시오.
윤년은 연도가 4의 배수이면서, 100의 배수가 아닐 때 또는 400의 배수일 때이다.

예를 들어, 2012년은 4의 배수이면서 100의 배수가 아니라서 윤년이다. 
1900년은 100의 배수이고 400의 배수는 아니기 때문에 윤년이 아니다. 
하지만, 2000년은 400의 배수이기 때문에 윤년이다.

2. 입력
첫째 줄에 연도가 주어진다. 연도는 1보다 크거나 같고, 4000보다 작거나 같은 자연수이다.

3. 출력
첫째 줄에 윤년이면 1, 아니면 0을 출력한다.

>>>코드

# include <stdio.h>
int main(void){
    int year;
    scanf("%d", &year);
    printf("%d", year%4 == 0 && year% 100 != 0 || year%400 == 0);
}

>>>문제링크
https://www.acmicpc.net/problem/2753