한번사는인생

안녕하세요!

오늘은 백준 문제 중에서 비교적 쉬운 문제로 꼽히는 **2675번 '문자열 반복'**을 풀어보겠습니다.

이 문제는 문자열을 주어진 횟수만큼 반복하여 출력하는 간단한 구현 문제입니다. 파이썬을 활용해 쉽게 접근할 수 있어요.

문제 설명

• 각 테스트 케이스마다 주어진 문자열의 각 문자를 반복하여 새로운 문자열을 만드는 것이 목표입니다.
• 입력으로는 몇 번 반복할 것인지와 문자열이 주어집니다.
• 예를 들어, 3번 반복할 때 문자열이 "ABC"라면 "AAABBBCCC"가 출력되어야 합니다.

입력 형식

1. 첫 번째 줄에는 테스트 케이스의 개수 T가 주어집니다.
2. 각 테스트 케이스는 반복 횟수 R과 문자열 S로 구성됩니다.

출력 형식

• 각 테스트 케이스마다 문자열 S의 각 문자를 R번 반복한 결과를 한 줄에 출력해야 합니다.

파이썬 코드 풀이

def repeat_string():
    t = int(input())
    for _ in range(t):
        r, s = input().split()
        r = int(r)
        result = ''.join([char * r for char in s])
        print(result)

if __name__ == "__main__":
    repeat_string()

코드 설명

1. t = int(input()) : 테스트 케이스의 개수를 입력받습니다.
2. for _ in range(t): : 입력된 테스트 케이스 수만큼 반복합니다.
3. r, s = input().split() : 반복 횟수 r과 문자열 s를 입력받아 각각 변수에 저장합니다.
4. r = int(r) : 반복 횟수를 정수형으로 변환합니다.
5. result = ''.join([char * r for char in s]) : 문자열의 각 문자를 r번 반복하고 이를 join() 함수를 사용해 하나의 문자열로 결합합니다.
6. print(result) : 최종적으로 반복된 문자열을 출력합니다.

감사합니다

문제 설명 요약

• 듣도 못한 사람의 명단이 N개, 보도 못한 사람의 명단이 M개 주어집니다.
• 이 두 명단에 모두 속하는 이름을 사전 순으로 출력하는 것이 목표입니다.

접근 방법

1. 데이터 저장: 듣도 못한 사람의 명단을 Set 자료구조에 저장하여 중복 처리를 간단하게 합니다. 파이썬의 Set은 해시 구조를 활용하여 원소의 탐색이 평균 O(1)에 가능하기 때문에 효율적입니다.
2. 교집합 연산: 보도 못한 사람의 명단도 입력받고, 이를 Set로 변환하여 두 집합 간의 교집합을 구합니다. 이 방법으로 두 명단에 중복된 이름을 쉽게 찾을 수 있습니다.
3. 결과 정렬 및 출력: 교집합으로 구한 이름들을 정렬하여 요구사항대로 출력합니다.

코드 구현

다음은 파이썬으로 구현한 코드입니다:

n, m = map(int, input().split())
heard = set()

# 듣도 못한 사람의 명단 입력
for _ in range(n):
    heard.add(input().strip())

# 보도 못한 사람의 명단 입력 및 교집합 계산
total = set()
for _ in range(m):
    name = input().strip()
    if name in heard:
        total.add(name)

# 결과 출력
result = sorted(total)
print(len(result))
for name in result:
    print(name)

주요 포인트

• Set 자료구조 사용: 중복된 데이터를 효율적으로 처리하기 위해 파이썬의 Set을 사용하였습니다. 이는 듣도 못한 명단에서 보도 못한 사람을 찾을 때 매우 효과적입니다.
• 시간 복잡도: 두 리스트의 길이를 각각 N, M이라 하면, 이 코드는 평균적으로 O(N + M)의 시간 복잡도를 가집니다. 이는 해시 테이블 기반의 Set 자료구조 덕분에 가능하며, 일반적인 리스트 탐색에 비해 훨씬 빠릅니다.

정리

이 문제는 두 집합 간의 교집합을 구하는 간단한 문제처럼 보이지만, Set을 활용한 효율적인 접근이 가능하다는 점에서 중요한 학습 포인트를 제공합니다. 특히, 해시 기반의 데이터 구조가 어떻게 효율성을 크게 향상시키는지를 직접 체험할 수 있습니다. 블로그에서는 이 문제를 통해 집합 연산의 유용성과 해시 구조의 효율성을 강조하는 방향으로 작성하면 좋을 것 같습니다.

이제 블로그에 이 문제를 소개할 때 어떤 추가적인 내용이나 스타일을 고려하고 싶으신가요? 예를 들어, 개인적인 경험이나 이 문제를 통해 배운 점 등을 추가하면 더 흥미로운 포스팅이 될 것 같습니다.

문제 소개

백준 1436번 문제는 '숌' 감독이 좋아하는 숫자인 '666'이 포함된 영화 제목을 찾는 문제입니다. 간단히 말해, '666'이 연속적으로 포함된 숫자들을 찾는 것이 목표입니다. 예를 들어, 첫 번째 영화 제목은 666, 두 번째 영화 제목은 1666, 세 번째는 2666입니다. 이렇게 '666'이 들어가는 숫자를 순서대로 나열해 찾는 과정이 필요합니다.

문제 접근 방법

이 문제를 해결하기 위해서는 숫자를 하나씩 증가시키며 '666'이 포함되는지를 확인해야 합니다. 단순히 1부터 시작해 조건에 맞는 숫자를 찾을 때까지 반복하면 해결할 수 있죠. 이 과정에서 중요한 점은 어떤 데이터 구조나 알고리즘의 사용보다는, 반복문을 어떻게 효율적으로 작성하는가에 있습니다.

제가 사용한 접근 방법은 다음과 같습니다:

1. 숫자 증가시키기: 시작은 666부터 합니다. 숫자를 하나씩 증가시키면서 '666'이 포함되는지를 체크합니다.
2. '666' 포함 여부 확인: 파이썬에서는 문자열의 부분 문자열을 손쉽게 확인할 수 있기 때문에, 이를 이용해 조건을 만족하는 숫자를 찾습니다.
3. N번째로 찾기: 문제에서 주어진 N번째 제목을 찾기 위해, 조건을 만족할 때마다 카운트를 증가시키고, 원하는 값에 도달하면 출력합니다.

코드 구현

n = int(input())
count = 0
num = 666

while True:
    if '666' in str(num):
        count += 1
        if count == n:
            print(num)
            break
    num += 1

이 코드의 핵심은 while 루프를 사용해 모든 숫자를 순차적으로 검사하는 것입니다. if '666' in str(num) 구문을 통해 현재 숫자가 '666'을 포함하고 있는지 여부를 확인할 수 있습니다. 조건을 만족할 때마다 카운트를 증가시키고, N번째 숫자에 도달하면 결과를 출력하는 방식입니다.

문제 해결 후 느낀 점

이 문제는 알고리즘의 복잡함보다는 기본적인 반복과 조건 확인을 얼마나 정확하게 구현할 수 있는지를 테스트하는 문제입니다. 코드를 작성하면서 '단순 반복문'이 얼마나 강력한 도구인지를 다시금 느꼈습니다. 또한, 문자열 조작이 문제 해결에 얼마나 유용한지를 깨닫게 되었죠.

1

문제 분석과 접근 방법

문제를 처음 읽었을 때, 8x8 크기의 체스판을 만들기 위해 여러 위치에서 시작하여 체스판을 다시 칠해야 한다는 점에서 복잡해 보였습니다. 문제의 핵심은 큰 체스판에서 8x8의 부분 체스판을 잘라내고, 그 부분이 흑백 패턴을 유지하도록 칠해야 한다는 것이었습니다. 이를 위해 여러 가지 경우를 고려해 보아야 했습니다.

접근 방법을 정리해 보았습니다:

1. 전체 체스판에서 8x8의 부분 체스판을 모두 탐색합니다
2. 체스판의 크기는 N x M이기 때문에 (N-7) x (M-7)의 위치에서 8x8 체스판을 시작할 수 있습니다. 각 위치에서 8x8의 부분 체스판을 슬라이딩 윈도우처럼 잘라내어 검토합니다
3. 각 8x8 체스판에 대해 두 가지 경우의 수를 확인합니다
4. 체스판의 첫 번째 칸이 흰색인 경우와 검은색인 경우를 각각 고려해야 합니다. 따라서 두 개의 체스판 패턴 (WBWB... 혹은 BWBW...)을 모두 비교하여 최소로 칠해야 할 칸의 개수를 계산합니다
5. 모든 경우의 수에서 최소값을 찾습니다
6. 각 8x8 체스판마다 두 가지 패턴을 비교한 뒤, 그 중에서 최소로 칠해야 하는 칸의 수를 기록하고, 전체 탐색이 끝난 후 가장 작은 값을 찾습니다

이 문제를 풀기 위해서는 전체 체스판을 순회하며 작은 체스판을 하나하나 검사하는, 일종의 브루트 포스 방식이 필요했습니다. 브루트 포스가 효율적인 이유는 문제에서 제공하는 N과 M의 크기가 비교적 작아 모든 경우의 수를 시도해도 시간 내에 해결이 가능하기 때문입니다.

2

구현 시 생각해본 점들

문제를 구현하면서 몇 가지 고려해야 할 점들이 있었습니다

1. 체스판의 규칙성 유지 체스판은 규칙적으로 흑과 백이 교차하는 형태를 가져야 하기 때문에, 이 규칙을 그대로 적용하여 비교를 간단히 만들 수 있었습니다. 이를 위해 두 가지 가능한 체스판의 초기 상태를 문자열 배열로 미리 준비해 두었고, 각 부분 체스판을 탐색할 때마다 미리 준비된 패턴과 비교하는 방식으로 접근했습니다
2. 브루트 포스의 타당성 처음에는 브루트 포스 방식으로 모든 8x8 부분 체스판을 검사하는 것이 비효율적일까 걱정했지만, 문제의 제한 조건이 크지 않기 때문에 모든 경우를 탐색해도 충분히 시간 내에 풀 수 있다는 점을 깨달았습니다. 때로는 효율성보다 명료한 풀이가 더 중요한 경우가 있음을 다시 느꼈습니다
3. 최소 변경 횟수 계산 각 부분 체스판에서 변경해야 하는 칸의 수를 계산할 때, 첫 번째 칸의 색상에 따라 두 가지 경우를 나눠 각각 계산했습니다. 이를 통해 두 가지 패턴을 모두 고려하여 더 적은 변경 횟수를 선택할 수 있었습니다. 이 과정에서 코드의 가독성을 위해 함수를 나눠서 작성한 것이 도움이 되었습니다

3

코드 구현

N, M = map(int, input().split())
board = [input() for _ in range(N)]

# 체스판 패턴 미리 정의
pattern1 = ["WBWBWBWB", "BWBWBWBW"] * 4
pattern2 = ["BWBWBWBW", "WBWBWBWB"] * 4

def count_paint(x, y, pattern):
    count = 0
    for i in range(8):
        for j in range(8):
            if board[x + i][y + j] != pattern[i][j]:
                count += 1
    return count

min_paint = float('inf')

# 8x8 체스판 탐색
for i in range(N - 7):
    for j in range(M - 7):
        paint1 = count_paint(i, j, pattern1)
        paint2 = count_paint(i, j, pattern2)
        min_paint = min(min_paint, paint1, paint2)

print(min_paint)

4

문제 해결 후 느낀 점

이 문제를 해결하면서 작은 부분 문제로 나누어 전체 문제를 해결하는 방법의 중요성을 다시금 느꼈습니다. 8x8 크기의 체스판을 반복해서 검사해야 하기 때문에 반복문을 어떻게 구조화할지, 그리고 각 부분 체스판에서 색상 변경을 어떻게 계산할지에 대한 논리적인 접근이 필요했습니다. 또한, 복잡한 문제도 단계별로 접근해 나가면 충분히 풀 수 있다는 자신감을 가지게 되었습니다.

이 문제는 특히 브루트 포스의 중요성을 다시 한 번 되새길 수 있는 좋은 기회였어요. 때로는 가장 단순한 방식이 가장 효과적인 해결책이 될 수 있음을 기억하게 되었습니다. 또한, 체스판처럼 시각적이고 규칙적인 패턴을 가진 문제를 다룰 때에는 시각적으로 그려보거나, 패턴을 코드로 표현하는 연습이 큰 도움이 되겠다는 생각도 들었습니다.

문제를 해결하면서 생긴 작은 시행착오들이 앞으로의 문제 해결에 좋은 밑거름이 되기를 기대합니다. 앞으로도 이러한 경험을 바탕으로 더 많은 문제들을 해결해 나가고 싶습니다.

1

문제 설명

입력으로 주어진 코드의 시간 복잡도를 판별하고, 코드의 수행 횟수와 최고차항의 차수를 출력하는 문제이다.

입력

입력은 두 줄로 이루어져 있습니다.
첫 번째 줄에 주어지는 정수 n (1 ≤ n ≤ 500,000)
두 번째 줄에 주어진 정수 f(n)

출력

두 줄에 걸쳐 답을 출력합니다.
첫 번째 줄에는 알고리즘의 수행 횟수를 출력합니다.
두 번째 줄에는 알고리즘의 시간 복잡도의 최고차항의 차수를 출력합니다.

풀이

문제는 주어진 f(n)이 **시간 복잡도가 O(1)**임을 설명합니다. 따라서 입력 값 n과는 무관하게, 알고리즘의 수행 횟수는 항상 1입니다. 최고차항의 차수 역시 0입니다.

맨 처음에는 알고리즘 문제 중 가장 쉬운 문제인 것 같아 진짜 가볍게 생각했다.

n = int(input())
m = int(input())

print(1)
print(0)

처음 입력 받고 최고 차항까지 받아야 하는 줄 알았다.

그러나 제출하고 나니 바로 런타임 에러

잠시 고민을 했다가 

n = input()

print(1)
print(0)

고정 값인 것 같길래 최고차항을 받아올 필요는 없다고 생각했다.

핵심 논리

입력된 n 값이 알고리즘 수행 횟수에 영향을 주지 않으므로, 알고리즘의 수행 횟수는 언제나 1입니다.
시간 복잡도가 O(1)이므로 차수는 0입니다.

백준 2869번: 달팽이는 올라가고 싶다

문제 설명
달팽이가 낮에는 올라가고, 밤에는 미끄러지며 나무 꼭대기에 도달하는 데 걸리는 일수를 계산하는 문제입니다.

문제 조건

• 낮에는 A만큼 올라가고, 밤에는 BB만큼 미끄러집니다.
• 나무의 높이는 V입니다.
• 마지막 날에는 꼭대기에 도달하면 미끄러지지 않습니다.

핵심 포인트

1. 수식 활용:
   • 반복문 없이 간단히 계산식으로 해결 가능.
2. 올림 연산:
   • 나눗셈 결과를 올림하여 최소 일수를 정확히 계산.

결과 코드

import math

a, b, v = map(int, input().split())

# a, b, v = 2, 1, 5

result = (v - b) / (a - b)

result = math.ceil(result)

print(result)

백준 1316번 문제: 그룹 단어 체커

문제 설명

1. 그룹 단어란, 단어에 포함된 문자들이 각각 연속해서 나타나는 경우를 말합니다.
   • 예: happy, new, year는 그룹 단어.
   • 예: abc, aab는 그룹 단어.
   • 예: aabbcc, abca는 그룹 단어가 아님 (abca에서 a가 떨어져 다시 등장).
2. 입력으로 주어진 단어들이 그룹 단어인지 판단하고, 그룹 단어의 개수를 출력합니다.

문제 해결 전략

1. 문자 등장 순서 추적:
   • 단어를 한 글자씩 순회하며, 이미 등장한 문자와 현재 문자가 연속적인지 확인합니다.
   • 이전 문자와 같으면 계속 진행.
   • 이전 문자와 다르지만 이미 등장했던 문자라면 그룹 단어가 아님.
2. 각 단어를 독립적으로 처리:
   • 주어진 단어마다 독립적으로 판단.
   • 결과적으로 그룹 단어인 단어의 개수를 세면 됩니다.

코드 구현

def is_group_word(word):
    seen = set()  # 등장한 문자를 저장할 집합
    prev_char = None  # 이전 문자를 저장

    for char in word:
        if char != prev_char:  # 이전 문자와 다를 때
            if char in seen:  # 이미 등장했던 문자면 그룹 단어 아님
                return False
            seen.add(char)  # 새로운 문자를 추가
        prev_char = char  # 이전 문자를 갱신

    return True  # 모든 문자가 조건을 만족하면 그룹 단어

# 입력 처리
n = int(input())  # 단어 개수
count = 0

for _ in range(n):
    word = input()
    if is_group_word(word):  # 그룹 단어라면 카운트 증가
        count += 1

print(count)

코드 설명

1. is_group_word 함수:
   • seen 집합:
     • 등장했던 문자를 저장합니다.
   • prev_char 변수:
     • 현재 문자와 이전 문자가 연속인지 판단하는 데 사용합니다.
   • 문자 순회 중:
     • 이전 문자와 다르고, 이미 등장한 문자라면 그룹 단어가 아님.
     • 새로운 문자는 seen 집합에 추가합니다.
2. 단어 입력 및 판별:
   • 주어진 n개의 단어를 하나씩 판별.
   • 그룹 단어라면 count를 증가시킵니다.
3. 결과 출력:
   • 그룹 단어의 총 개수를 출력합니다.

입출력 예시

입력:

3
happy
new
year

출력:

3

입력:

4
aba
abab
abcabc
a

출력:

1

풀이 과정:

1. aba: a → b → a (떨어진 a가 다시 등장 → 그룹 단어 아님).
2. abab: a → b → a (떨어진 a가 다시 등장 → 그룹 단어 아님).
3. abcabc: a → b → c → 다시 a 등장 (그룹 단어 아님).
4. a: 한 글자이므로 그룹 단어.

시간 복잡도

• 단어 개수: n
• 단어의 평균 길이: m
• 각 단어를 순회하므로 전체 시간 복잡도는 O(n⋅m)

자주 하는 실수

1. 이미 등장한 문자를 확인하지 않음:
   • 떨어진 문자가 다시 등장할 경우를 확인하지 않으면 틀린 결과가 나옵니다.
2. 이전 문자와 연속된 경우를 놓침:
   • 이전 문자와 연속된 경우는 문제없으므로 조건을 명확히 처리해야 합니다.

백준 1193번 문제: 분수찾기

문제 설명

1. 양의 정수를 순서대로 분수에 배치하여 다음과 같은 규칙을 따릅니다:
   • 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → 1/3 → ...
2. 주어진 정수 X에 대해, X번째에 해당하는 분수를 구해야 합니다.

문제 해결 전략

1. 규칙 분석:
   • 분수는 대각선 그룹으로 나뉩니다.
   • 그룹 1: 1/1 (1개)
   • 그룹 2: 1/2,2/1 (2개)
   • 그룹 3: 3/1,2/2,1/3 (3개)
   • 그룹 n: n개의 분수로 이루어짐.
2. 그룹 번호 찾기:
   • X번째 분수는 어느 대각선 그룹에 속하는지 알아야 합니다.
   • 그룹 n까지의 합은 삼각수: sum=1+2+3+⋯+n=n(n+1) / 2
   • X가 포함되는 그룹 n은 n(n+1) / 2 ≥ X일 때 찾을 수 있습니다.
3. 해당 그룹에서의 위치 계산:
   • 그룹 n의 시작 번호는 (n−1)n / 2 + 1
   • X는 그룹의 시작 번호로부터 몇 번째에 위치하는지 계산합니다.
4. 분수 방향:
   • 그룹 번호가 홀수: 분자분자 감소, 분모분모 증가.
   • 그룹 번호가 짝수: 분자분자 증가, 분모분모 감소.

코드 구현

X = int(input())  # 입력값 X

# 그룹 번호 찾기
group = 1
while X > group * (group + 1) // 2:
    group += 1

# 해당 그룹에서의 위치
start_of_group = (group - 1) * group // 2 + 1
position_in_group = X - start_of_group

# 분수 계산
if group % 2 == 0:  # 짝수 그룹
    numerator = 1 + position_in_group
    denominator = group - position_in_group
else:  # 홀수 그룹
    numerator = group - position_in_group
    denominator = 1 + position_in_group

print(f"{numerator}/{denominator}")

코드 설명

1. 그룹 번호 찾기:
   • 그룹 번호는 n(n+1) / 2 ≥ X 조건을 만족할 때까지 증가시킵니다.
2. 그룹 시작 번호:
   • 그룹 nn의 시작 번호는 (n−1)n / 2 +1 로 계산합니다.
3. 그룹 내 위치:
   • X가 그룹에서 몇 번째인지 계산:

     position_in_group = X - start_of_group

4. 분수 계산:
   • 짝수 그룹이면 분자분자가 증가하고 분모분모가 감소.
   • 홀수 그룹이면 분자분자가 감소하고 분모분모가 증가.

입출력 예시

입력:

14

출력:

2/4

풀이 과정:

1. X = 14 → 그룹 5에 속함 (5(5+1) / 2 = 15)
2. 그룹 5의 시작 번호: (5−1)5 / 2 + 1 = 11
3. 그룹 내 위치: 14 − 11 = 3
4. 그룹 5는 홀수 그룹 → 분자 = 5−3=2, 분모=1+3=4