TIL 코딩공장

백준 CPP 공부 2025.05.14
10845번 큐 (실버 4)

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

명령은 총 여섯 가지이다.

- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

2. 입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 
둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 
문제에 나와있지 않은 명령이 주어지는 경우는 없다.

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

4. 문제 풀이
#include <queue>에서 지원하는 pop이 해당 값을 반환하지 않는다는 점만 유의하자.

>>코드

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main(){
    queue<int> Q;
    
    int n;
    cin  >> n;
    
    for (int i = 0; i < n; i++){
        string opr;
        cin >> opr;
        
        if (opr == "push"){
            int num;
            cin >> num;
            Q.push(num);
        }
        else if (opr == "pop"){
            if (Q.empty()) cout << -1 << endl;
            else {
                cout << Q.front() << endl;
                Q.pop();
            }
        }
        else if (opr == "size"){
            cout << Q.size() << endl;
        }
        else if (opr == "empty"){
            cout << Q.empty() << endl;
        }
        else if (opr == "front"){
            if (Q.empty()) cout << -1 << endl;
            else cout << Q.front() << endl;
        }
        else if (opr == "back"){
            if (Q.empty()) cout << -1 << endl;
            else cout << Q.back() << endl;
        }
    }
}

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

백준 CPP 공부 2025.03.14
2798번 블랙잭 (브론즈 2)

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

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

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 
그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 
그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 
블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

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

2. 입력
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 
둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

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

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

4. 코드

#include <iostream>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    
    int card[n];
    for (int i = 0; i<n; i++){
        cin >> card[i];
    }
    
    int result = 0;
    int sum;
    for (int i = 0; i<n-2; i++){
        for (int j = i+1; j<n-1; j++){
            for (int k = j+1; k<n; k++){
                sum = card[i] + card[j] + card[k];
                if (result < sum && sum <= m) result = sum;
            }
        }
    }
    cout << result << endl;
    return 0;
}

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

백준 파이썬 공부 2024.12.08
28701번 세제곱의 합 (브론즈 5)

1. 문제
은하는 수업 때 1부터 N까지 수의 합과 1부터 N까지 수의 세제곱의 합과 
관련된 다음 공식을 배웠습니다.

 - (1 + 2 + ... + N)^2 = 1^3 + 2^3 + ... + N^3

믿을 수 없었던 은하는 직접 코딩을 해서 검증해 보기로 했습니다. 
1부터 N까지 수의 합과 그 수를 제곱한 수, 
또 1부터 N까지 수의 세제곱의 합을 차례대로 출력하세요.

2. 입력
첫 줄에 문제의 정수 N이 주어집니다. 
(5 <= N <= 100)

3. 출력
세 줄을 출력하세요.

- 첫 줄에는 1부터 N까지 수의 합 1+2+...+N을 출력하세요.
- 둘째 줄에는 1부터 N까지 수의 합을 제곱한 수 (1+2+...+N)^2을 출력하세요.
- 셋째 줄에는 1부터 N까지 수의 세제곱의 합 1^3+2^3+...+N^3을 출력하세요.

4. 코드

n = int(input())
# 합의 제곱
ans1 = 0
for i in range(n+1):
    ans1 += i
print(ans1)
print(ans1 ** 2)

# 세제곱들의 합
ans2 = 0
for i in range(n+1):
    ans2 += i ** 3
print(ans2)

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

백준 파이썬 공부 2024.11.14
1389번 케빈 베이컨의 6단계 법칙 (실버 1)

1) 문제
케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 
케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 
천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 
최백준과 김선영은 같이 Startlink를 창업했다. 
김선영과 김도현은 같은 학교 동아리 소속이다. 
김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 
즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 
케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 
따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 
따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 
따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 
4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 
5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

2) 입력
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 
둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 
친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. 
A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 
친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 
또, 모든 사람은 친구 관계로 연결되어져 있다. 
사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.

3) 출력
첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 
그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

4) 코드 풀이
BFS 방식(너비 우선 탐색)을 이용하여 풀이한다.

- n+1 길이의 이중리스트 arr 생성
- 입력받은 관계의 인덱스에 해당하는 리스트에 서로의 관계 저장
- 관계의 경로 길이를 계산할 n+1 크기의 visit 리스트 생성 및 -1로 초기화
- 덱을 생성하여, 시작지점의 리스트 값을 0으로 설정
- visit 리스트에서 -1인 사람까지의 경로 확인 및 길이 계산
- 하나씩 popleft하면서, 해당 노드 인덱스의 관계(arr)로 다음 노드를 확인
- 해당 노드의 visit 리스트 값이 -1이면(해당 노드에 접근한적이 없으면) 
그전 노드 경로까지의 케빈 베이컨의 값 +`1 & 다음 노드 덱에 추가
- visit 리스트 값의 총합 == 해당 사람(노드)의 케빈 베이컨의 값
- 케빈 베이컨의 값들 중 최소값을 가진 사람 반환

5) 코드

from collections import deque

n, m = map(int, input().split())
friend = [[] for _ in range(n+1)]

# 관계 입력받기
for i in range(m):
    a, b = map(int, input().split())
    # 관계 friend 리스트에 저장
    friend[a].append(b)
    friend[b].append(a)

# 경로 찾기 함수
def BFS(start):
    # 기본 설정1. 해당 start 노드로부터의 관계 길이 저장할 리스트 visit
    visit = [-1] * (n+1)
    # 현재 위치한 노드를 저장할 deque
    queue = deque()
    # 시작 노드 설정
    queue.append(start)
    # 시작 노드 0으로 초기화
    visit[start] = 0
    
    # 모든 노드를 돌 때까지 (덱이 빌 때까지)
    while queue:
        # 현재 노드 popleft
        node = queue.popleft()
        # 현재 노드와 관계가 있는 다음 노드 확인
        for next_node in friend[node]:
            # 만약 한번도 가지 않은 노드라면 현재 노드까지의 관계 길이 +1
            if visit[next_node] == -1:
                visit[next_node] = visit[node] + 1
                queue.append(next_node)
    # 케빈 베이컨의 수 계산 (인덱스 0의 값이 -1이므로 + 1)
    kevin = sum(visit) + 1
    return kevin
                
# 각 사람의 케빈 베이컨의 수 계산 및 비교 시작
min = float("INF")
ans = 0
for person in range(1, n+1):
    if BFS(person) < min:
        min = BFS(person)
        ans = person
# 출력
print(ans)

6) 문제링크
https://www.acmicpc.net/problem/1389

2024/11/04 백준 파이썬 공부
9095번 1, 2, 3 더하기

1) 문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 
합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

2) 입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 
각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. 
n은 양수이며 11보다 작다.

3) 출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

4) 코드

T = int(input())
num = [0, 1, 2, 4]

for i in range(T):
    n = int(input())
    
    for j in range(3, n):
        if j >= len(num)-1:
            num.append(num[j-2] + num[j-1] + num[j])
    
    print(num[n])

5) 문제 해설
1의 표현법: 1 >> 1개
2의 표현법: 1+1, 2 >> 2개
3의 표현법: 1+1+1, 1+2, 2+1, 3 >> 4개
4의 표현법: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 1+3, 3+1, 2+2 >> 7개
...

>> 점화식
num[n] = num[n-1] + num[n-2] + num[n-3]

따라서, 1, 2, 3의 표현하는 방법의 수를 저장해 놓고, 갱신을 하면서, 해당 수의 표현 방법 수를 계산한다.


6) 문제링크
https://www.acmicpc.net/problem/9095

20240203 백준 C언어 공부
27866번 문자와 문자열

1. 문제
단어 S와 정수 i가 주어졌을 때, S의 i번째 글자를 출력하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 영어 소문자와 대문자로만 이루어진 단어 S가 주어진다. 단어의 길이는 최대 1,000이다.
둘째 줄에 정수 i가 주어진다. (1 <= i <= |S|)

3. 출력
 S의 i번째 글자를 출력한다.

>>>코드

#include <stdio.h>
int main(void){
    char w[1000];
    int n;
    scanf("%s", w);
    scanf("%d", &n);
    printf("%c", w[n-1]);
    return 0;
}

>>> 문제 설명
- char 문자열[문자열 길이]; >> 문자열 선언
- scanf(%s, 문자열); >> 문자열 입력받기

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

20240326 백준 파이썬 공부
28278번 스택 2

1. 문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.

1) 1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
2) 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
3) 3: 스택에 들어있는 정수의 개수를 출력한다.
4) 4: 스택이 비어있으면 1, 아니면 0을 출력한다.
5) 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.

2. 입력
첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.
출력을 요구하는 명령은 하나 이상 주어진다.

3. 출력
출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.

>>>코드

import sys # sys.stdin.readline 사용 안하면 시간초과 나옴
stack = [] # 스택
for _ in range(int(input())):
    command = list(map(int, sys.stdin.readline().split()))
    if command[0] == 1: # 1 x의 경우
        stack.append(command[1])
    elif command[0] == 2: # 2의 경우
        if len(stack) == 0:
            print(-1)
        else:
            print(stack[-1])
            stack.pop()
    elif command[0] == 3: # 3의 경우
        print(len(stack))
    elif command[0] == 4: # 4의 경우
        if len(stack) == 0:
            print(1)
        else:
            print(0)
    elif command[0] == 5: # 5의 경우
        if len(stack) == 0:
            print(-1)
        else:
            print(stack[-1])

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

20240129 백준 C언어 공부
15552번 빠른 A+B

1. 문제
본격적으로 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의 기타 여러 가지 팁을 볼 수 있다.

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

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

>>>코드

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

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