한번사는인생

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 크기의 체스판을 반복해서 검사해야 하기 때문에 반복문을 어떻게 구조화할지, 그리고 각 부분 체스판에서 색상 변경을 어떻게 계산할지에 대한 논리적인 접근이 필요했습니다. 또한, 복잡한 문제도 단계별로 접근해 나가면 충분히 풀 수 있다는 자신감을 가지게 되었습니다.

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

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

백준 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)

문제 설명

1. 주어진 정수 N에 따라 아래와 같은 형태의 별(*)을 출력해야 합니다:
   • N=5 일 때:

         *
        ***
       *****
      *******
     *********
      *******
       *****
        ***
         *

      
2. 이 문제는 중앙을 기준으로 대칭적인 피라미드 모양을 출력하는 문제입니다.

문제 해결 전략

1. 첫 번째 피라미드 (위쪽 절반):
   • i-번째 줄에 출력되는 별의 개수는 2i−1
   • 공백의 개수는 N−i
2. 두 번째 피라미드 (아래쪽 절반):
   • ii-번째 줄(위 절반 이후)의 별의 개수는 2(N−i)−1
   • 공백의 개수는 i−N
3. 이를 반복문으로 처리하여 출력합니다.

코드 구현

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

# 위쪽 피라미드
for i in range(1, N + 1):
    print(" " * (N - i) + "*" * (2 * i - 1))

# 아래쪽 피라미드
for i in range(N - 1, 0, -1):
    print(" " * (N - i) + "*" * (2 * i - 1))

코드 설명

위쪽 피라미드:

• i-번째 줄에서:
  • " " * (N - i) → 왼쪽 공백 출력.
  • "*" * (2 * i - 1) → 별 출력.
• 예를 들어 N=5일 때:

    *
   ***
  *****
 *******
*********

아래쪽 피라미드:

• i-번째 줄에서:
  • " " * (N - i) → 왼쪽 공백 출력.
  • "*" * (2 * i - 1) → 별 출력.
• i를 N−1부터 1까지 감소시키면서 처리.
• 예를 들어 N=5일 때:

 *******
  *****
   ***
    *

출력:

• 두 반복문을 순차적으로 실행하여 최종 출력물을 완성합니다.

시간 복잡도

• 각 반복문은 O(N)으로 실행됩니다.
• 전체 시간 복잡도는 O(N)+O(N)=O(N)

자주 하는 실수

1. 공백과 별의 관계를 잘못 설정:
   • 공백의 개수는 N−i이고, 별의 개수는 2i−1임을 놓치면 출력 형식이 잘못됩니다.
2. 아래쪽 피라미드의 시작을 N으로 설정:
   • 아래쪽 피라미드는 N−1부터 시작해야 정상적으로 대칭 구조를 유지합니다.

백준 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. 이전 문자와 연속된 경우를 놓침:
   • 이전 문자와 연속된 경우는 문제없으므로 조건을 명확히 처리해야 합니다.

1

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

[ 테스트 코드 ]

x = input()

xList = list(x.upper())

print(xList)

# 주어진 리스트
letters = ['M', 'I', 'S', 'S', 'I', 'S', 'S', 'I', 'P', 'I']

# 빈 딕셔너리로 개수 세기
counts = {}

for letter in letters:
    counts[letter] = counts.get(letter, 0) + 1

# 중복된 값 추출
duplicates = {key: value for key, value in counts.items() if value > 1}

print(duplicates)  # 출력: {'I': 4, 'S': 4}


data = input().upper()

max_char = max(set(data), key=data.count)
max_count = data.count(max_char)

if sum(1 for char in set(data) if data.count(char) == max_count) > 1:
    print('?')
else:
    print(max_char)

여기서 중요했던 요점은 문자를 대문자로 변형하고 중복 값을 체크 하는 것이다.

[ 결과 코드 ]

data = input().upper()

max_char = max(set(data), key=data.count)
max_count = data.count(max_char)

if sum(1 for char in set(data) if data.count(char) == max_count) > 1:
    print('?')
else:
    print(max_char)

그리고 코드를 조금 더 간결하게 짤 방법을 찾았고

요점은

가장 많이 등장하는 문자를 찾고 해당 문자의 수를 체크한다.

그리고  많이 나오는 문자의 수가 여러 개인지 확인하는 것까지 코드로 완성하였다.