공부블로그

TODAY TIL

안녕하세요! 😊 오늘은 숫자를 영어로 읽어서 사전순으로 정렬하는 재미있는 문제를 함께 풀어보겠습니다. 이 문제는 파이썬으로 간단하게 구현할 수 있으니, 따라오세요!

문제 설명 📖

1. 숫자를 숫자 단위로 영어로 읽는다.
   • 예: 79 → seven nine, 80 → eight zero
2. 영어로 읽은 숫자를 기준으로 사전순 정렬한다.
   • 예: 80 (eight zero) → 79 (seven nine)
3. 정렬한 숫자를 한 줄에 10개씩 출력한다.

입출력 예시 📝

입력

79 80

출력

80 79

또 다른 예시

입력

8 15

출력

8 11 12 13 15 14 10 9

문제 풀이 과정 💡

1단계: 숫자를 영어로 변환하기

숫자를 하나씩 쪼개서 영어로 읽어야 해요.
예를 들어:

• 79 → seven nine
• 80 → eight zero

이를 위해 각 자리 숫자를 영어로 변환하는 함수를 만듭니다.

2단계: 정렬 기준 만들기

숫자를 영어로 변환한 후, 영어 문자열 기준으로 정렬합니다.

3단계: 한 줄에 10개씩 출력하기

정렬된 숫자들을 10개씩 묶어서 출력하면 됩니다.

파이썬 코드 🐍

def number_to_words(num):
    # 숫자를 영어로 변환하는 함수
    digits = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"]
    return " ".join(digits[int(digit)] for digit in str(num))

def solve_number_problem(M, N):
    # M부터 N까지 숫자를 영어로 변환하여 정렬
    numbers = list(range(M, N + 1))
    sorted_numbers = sorted(numbers, key=number_to_words)
    
    # 결과를 한 줄에 10개씩 출력
    for i in range(0, len(sorted_numbers), 10):
        print(" ".join(map(str, sorted_numbers[i:i + 10])))

# 입력 받기
M, N = map(int, input().split())
solve_number_problem(M, N)

코드 설명 🛠️

함수 number_to_words

• 숫자 하나를 받아서 숫자 단위로 영어 문자열로 변환합니다.
• 예: 79 → seven nine, 80 → eight zero
•  

digits = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"]
return " ".join(digits[int(digit)] for digit in str(num))

함수 solve_number_problem

1. M부터 N까지 숫자를 리스트로 생성합니다.
   • 예: M=79, N=80 → [79, 80]
2. 숫자를 number_to_words 기준으로 정렬합니다.
   • 예: 79 → seven nine, 80 → eight zero
   • 정렬 결과: [80, 79]
3. 한 줄에 10개씩 출력합니다.
   • 예: print(" ".join(...))

예제 실행 결과 🎯

입력

8 15

출력

8 11 12 13 15 14 10 9

문제를 해결하면서 배운 점 📚

1. 숫자를 영어로 변환하기 위해 문자열 처리를 배웠어요.
2. sorted 함수로 정렬 기준을 자유롭게 설정하는 방법을 익혔어요.
3. 한 줄에 10개씩 출력하는 반복문 작성법도 알게 되었어요.

마무리 ✍️

이번 문제는 숫자를 영어로 읽는 독특한 방법과 정렬 기준 설정이 핵심이었습니다. 여러분도 파이썬으로 재미있게 구현해보세요! 😊

TODAY TIL

온라인 게임에서 세준이와 세비가 키운 군대가 대결을 펼친다면 어떻게 될까요? 이번 포스팅에서는 각 군대의 병사들이 전투를 벌여 최후의 승자를 가리는 시뮬레이션 문제를 풀어보려고 합니다. 문제를 간단히 설명하고, 이를 해결하기 위한 파이썬 코드를 함께 살펴볼게요!

문제 설명

세준이와 세비는 각각 군대를 키웠고, 이제 서로의 병사들로 전쟁을 하려고 합니다. 전쟁은 여러 번의 전투로 이루어지며, 매 전투에서 살아남은 병사들 중 가장 약한 병사가 죽게 됩니다. 이 과정을 한 명의 병사만 남을 때까지 반복하며, 최후에 살아남은 병사가 속한 팀이 승리하게 됩니다.

문제의 규칙은 다음과 같습니다:

• 입력: 첫 번째 줄에 테스트 케이스의 개수 T가 주어집니다. 각 테스트 케이스에서는 두 줄에 걸쳐서 세준이와 세비의 병사 수와 각 병사의 힘이 주어집니다.
• 출력: 각 테스트 케이스마다 승리한 팀을 출력합니다. 세준이가 이기면 'S', 세비가 이기면 'B', 둘 다 죽으면 'C'를 출력합니다.

병사의 힘은 정수로 주어지며, 이 값이 클수록 강한 병사를 의미합니다. 전투 중에는 두 팀의 병사 중 약한 병사들이 먼저 죽게 되고, 승자를 가릴 때까지 전투가 반복됩니다.

입력 예시

1
3 3
5 10 7
6 9 8

• 첫째 줄: 테스트 케이스의 수 (1)
• 둘째 줄: 세준이의 병사 수 (3명)과 세비의 병사 수 (3명)
• 셋째 줄: 세준이의 병사들의 힘 (5, 10, 7)
• 넷째 줄: 세비의 병사들의 힘 (6, 9, 8)

출력 예시

S

• 세준이가 승리한 경우 'S' 출력

파이썬 코드로 문제 풀이하기

이제 이 문제를 해결하기 위한 파이썬 코드를 작성해볼게요. 아래 코드는 주어진 병사들의 힘을 비교하면서 각 팀의 병사들이 하나씩 전멸해가는 과정을 시뮬레이션해줍니다.

n = int(input())
for i in range(n):
    input()  # 테스트 케이스 번호나 팀 이름은 사용하지 않음
    a, b = map(int, input().split())
    s_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))
    
    # 병사들의 힘을 내림차순으로 정렬하여 가장 강한 병사가 앞에 오도록 함
    s_list.sort(reverse=True)
    b_list.sort(reverse=True)

    # 두 팀 중 한 팀의 병사가 전멸할 때까지 라운드를 진행함
    while s_list and b_list:
        # 세준이의 가장 강한 병사가 세비의 가장 강한 병사보다 강할 경우
        if s_list[0] >= b_list[0]:
            b_list.pop(0)  # 세비의 병사를 제거함
        else:
            s_list.pop(0)  # 세준이의 병사를 제거함

    # 결과 출력: 세준이가 이긴 경우 'S', 세비가 이긴 경우 'B', 둘 다 없는 경우 'C'
    if s_list:
        print('S')
    elif b_list:
        print('B')
    else:
        print('C')

코드 설명

1. 입력받기: 테스트 케이스의 개수를 입력받고, 각 케이스마다 병사들의 힘을 리스트로 입력받습니다.
2. 내림차순 정렬: 각 팀의 병사들을 내림차순으로 정렬해서 가장 강한 병사가 리스트 앞쪽에 오도록 합니다.
3. 전투 진행: while 반복문을 사용해 두 팀의 병사들이 남아있을 동안 전투를 계속합니다. 각 라운드마다 가장 강한 병사들끼리 비교하여 상대방을 제거합니다.
4. 승자 판별: 최종적으로 남은 병사가 있는 팀을 출력합니다. 세준이가 이기면 'S', 세비가 이기면 'B', 모두 없으면 'C'를 출력합니다.

예시를 통해 이해하기

입력 예시에서 세준이의 병사들은 [10, 7, 5]로 정렬되고, 세비의 병사들은 [9, 8, 6]으로 정렬됩니다. 가장 강한 병사들끼리 싸워서 이긴 팀의 병사가 남게 되고, 결국 세준이 팀의 병사들만 남기 때문에 'S'가 출력됩니다.

마무리

이렇게 세준이와 세비의 군대가 전투를 벌이는 시뮬레이션 문제를 해결해 보았습니다. 전투 시뮬레이션 문제를 통해 리스트의 정렬과 반복문을 활용해 문제를 해결하는 방법을 배울 수 있었어요. 각 전투마다 가장 강한 병사들끼리 비교하고, 하나씩 병사가 줄어들면서 최후의 승자를 가리는 방식으로 전투를 진행해요.

이번 포스팅이 도움이 되었길 바라며, 궁금한 점이나 이해가 안 되는 부분이 있다면 언제든지 댓글로 남겨주세요! 😊

TODAY TIL

파이썬으로 점수 순위 매기기 - 쉬운 풀이 가이드

안녕하세요, 이번 블로그 포스트에서는 파이썬을 이용해 점수 배열을 받아 선수들의 순위를 매기는 문제를 해결해보려고 합니다. 점수에 따라 메달을 부여하고 순위를 매기는 알고리즘 문제를 쉽게 이해할 수 있도록 차근차근 설명드릴게요. 이 포스트를 통해 여러분이 코드 작성 과정을 이해하고, 직접 문제를 풀어볼 수 있도록 돕겠습니다!

문제 설명

우리는 각 선수의 점수가 담긴 배열을 받습니다. 이 배열에는 각 선수의 점수가 고유하게 담겨 있으며, 높은 점수가 높은 순위를 의미합니다. 각 선수는 다음과 같은 순위에 따라 메달 또는 순위 번호를 부여받습니다.

• 1등: "Gold Medal"
• 2등: "Silver Medal"
• 3등: "Bronze Medal"
• 4등 이후: 해당 순위 숫자

예를 들어, 입력 배열이 [10, 3, 8, 9, 4]이라면 결과는 ['Gold Medal', '5', 'Bronze Medal', 'Silver Medal', '4']가 되어야 합니다.

해결 방법

이 문제를 해결하기 위해 다음과 같은 단계를 거칠 것입니다.

1. 점수 배열과 인덱스 묶기: 각 점수와 인덱스를 묶어 리스트로 만듭니다. 이렇게 하면 점수를 정렬한 후에도 각 점수가 원래 어디에 있었는지 알 수 있습니다.
2. 점수 정렬하기: 점수들을 높은 순서대로 정렬합니다. 정렬된 순서에서 1등, 2등, 3등을 각각 메달로 처리하고 나머지 순위를 숫자로 기록합니다.
3. 결과 배열 생성: 원래 배열에 맞는 순위를 기록한 결과 배열을 반환합니다.

코드 구현

이제 파이썬 코드로 이 문제를 해결하는 방법을 알아보겠습니다. 코드가 이해하기 쉽게 클래스 형태로 작성되어 있습니다.

class Solution:
    def findRelativeRanks(self, score):
        # 점수 배열과 각 인덱스를 묶어 (점수, 인덱스) 형태로 리스트 생성 후 내림차순 정렬
        sorted_score = sorted(enumerate(score), key=lambda x: x[1], reverse=True)

        # 결과 배열 초기화
        ranks = [""] * len(score)

        # 순위에 따라 메달 혹은 순위 번호를 할당
        for i, (idx, value) in enumerate(sorted_score):
            if i == 0:
                ranks[idx] = "Gold Medal"
            elif i == 1:
                ranks[idx] = "Silver Medal"
            elif i == 2:
                ranks[idx] = "Bronze Medal"
            else:
                ranks[idx] = str(i + 1)

        return ranks

# 예제 입력 테스트
solution = Solution()
score1 = [5, 4, 3, 2, 1]
print(solution.findRelativeRanks(score1))  # 출력: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

score2 = [10, 3, 8, 9, 4]
print(solution.findRelativeRanks(score2))  # 출력: ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

코드 설명

• 점수 정렬하기: enumerate(score)를 사용해 점수와 인덱스를 함께 묶은 후, 점수를 기준으로 내림차순 정렬했습니다. 이렇게 하면 각 점수가 원래 어느 위치에 있었는지 알 수 있게 됩니다.
• 결과 배열 생성: 정렬된 점수에 따라 순위를 매기고, 그에 맞는 메달 혹은 순위 숫자를 원래 인덱스 위치에 기록합니다.
• 메달 할당: 1, 2, 3등에 해당하는 선수에게 각각 "Gold Medal", "Silver Medal", "Bronze Medal"을 부여하고, 나머지는 순위 숫자를 할당합니다.

예제 테스트

• 입력: [5, 4, 3, 2, 1]
  • 출력: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
• 입력: [10, 3, 8, 9, 4]
  • 출력: ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]

마무리

이렇게 해서 점수 배열을 받아 선수들의 순위를 메달 및 숫자로 표현하는 방법을 알아보았습니다. 간단한 정렬과 반복문을 이용해 문제를 해결할 수 있었죠. 이 문제는 파이썬의 정렬 기능과 인덱스 활용을 배울 수 있는 좋은 예제입니다.

여러분도 비슷한 문제를 풀 때 이런 방식으로 접근해 보세요! 질문이나 궁금한 점이 있으면 언제든지 댓글로 남겨주세요.

안녕하세요! 오늘은 간단하면서도 재미있는 프로그래밍 문제를 함께 풀어보려고 합니다. 문제는 다음과 같습니다:

문제: 여러 학교의 한 해 동안 술 소비량 데이터가 주어졌을 때, 가장 많이 술을 마신 학교의 이름을 출력하라.

문제의 배경

입학 OT 때 누구보다도 열심히(?) 놀았던 당신은 자연스럽게 1학년 과대를 맡게 되었습니다. 조인트 엠티를 기획하던 중, 주변 학교 중에서 가장 술 소비가 많은 학교가 궁금해졌습니다. 각 학교의 술 소비량이 주어졌을 때, 가장 많이 술을 마신 학교를 찾는 프로그램을 만들어봅시다.

문제 설명

입력

1. 첫 줄에 테스트 케이스 수 T가 주어집니다.
2. 각 테스트 케이스의 첫 줄에는 학교의 수 N이 주어집니다.
3. 이어서 N줄에 걸쳐 각 학교 이름 S와 해당 학교의 술 소비량 L이 주어집니다.
   • 예: Yonsei 20000

출력

• 각 테스트 케이스마다 가장 술 소비량이 많은 학교 이름을 한 줄씩 출력합니다.

조건

• 학교의 수 N은 1 이상 100 이하.
• 소비량 L은 0 이상 10,000,000 이하.
• 같은 테스트 케이스 내에서 소비량이 동일한 학교는 없습니다.

풀이 접근

1. 입력 데이터를 처리하기
   첫 번째 줄에서 테스트 케이스 수 T를 입력받습니다.
   각 테스트 케이스는 학교의 수 N과 학교 이름 및 소비량 정보가 주어지므로 이를 반복문으로 처리합니다.
2. 가장 많이 마신 학교 찾기
   각 학교의 이름과 술 소비량을 비교하며 최대 소비량과 그에 해당하는 학교 이름을 기록합니다.
3. 결과 출력
   테스트 케이스마다 가장 많이 술을 마신 학교의 이름을 출력합니다.

코드 구현

# 테스트 케이스 수 입력
T = int(input("테스트 케이스 수를 입력하세요: "))

# 테스트 케이스 처리
for _ in range(T):
    # 학교의 수 입력
    N = int(input("학교의 수를 입력하세요: "))
    max_school = ""  # 술 소비량이 가장 많은 학교 이름 저장
    max_liquor = 0   # 최대 술 소비량 저장
    
    # N개의 학교 데이터 입력
    for _ in range(N):
        school, liquor = input("학교 이름과 술 소비량을 입력하세요: ").split()
        liquor = int(liquor)
        
        # 최대 소비량과 비교하여 업데이트
        if liquor > max_liquor:
            max_liquor = liquor
            max_school = school
    
    # 결과 출력
    print(max_school)

코드 설명

1. 테스트 케이스 수 입력

• 첫 줄에 테스트 케이스 수 T를 입력받습니다.
• T번 반복하면서 각각의 테스트 케이스를 처리합니다.

2. 학교 데이터 처리

• 각 테스트 케이스에서 학교의 수 N과 이름-소비량 데이터를 입력받습니다.
• 최대값 비교를 통해 가장 많이 술을 마신 학교와 그 소비량을 기록합니다.

3. 결과 출력

• 각 테스트 케이스마다 최대 소비량을 가진 학교의 이름을 출력합니다.

예제 실행

입력 예제

2
3
Korea 10000
Yonsei 20000
Ewha 30000
2
SeoulTech 5000
KU 7000

출력 예제

Ewha
KU

실행 과정 설명

1. 첫 번째 테스트 케이스:
   • Korea: 10000, Yonsei: 20000, Ewha: 30000 데이터를 비교하여 Ewha가 가장 많이 소비했으므로 출력.
2. 두 번째 테스트 케이스:
   • SeoulTech: 5000, KU: 7000 데이터를 비교하여 KU가 가장 많이 소비했으므로 출력.

핵심 포인트

• 입력 데이터 처리: 여러 테스트 케이스를 하나씩 처리하는 반복문 사용.
• 최댓값 비교: 각 학교의 소비량을 비교하여 현재까지의 최댓값과 이름을 갱신.
• 문제 해결 능력 향상: 데이터를 순차적으로 처리하면서 최대값을 구하는 방식은 다양한 문제에서 활용 가능!

마무리

이 문제는 간단한 반복문과 조건문을 활용하여 데이터를 처리하는 능력을 기르는 데 매우 유용합니다. 여러분도 직접 코드를 작성하고 실행해 보세요! 😊

궁금한 점이나 피드백이 있다면 댓글로 남겨주세요!

TODAY TIL

🔍 문제 소개

이번 포스팅에서는 배열에서 K번째 수를 찾는 문제를 다룹니다. 이 문제는 정렬 알고리즘의 기초를 연습하기에 적합하며, 간단한 구현으로도 해결할 수 있는 문제입니다. 문제를 이해하고, 순서대로 해결 방법과 코드를 공유하겠습니다!

📝 문제 설명

문제

• 크기가 N인 배열 A가 주어집니다.
• 배열 A를 오름차순으로 정렬했을 때, 앞에서부터 K번째 수를 출력하세요.

입력 조건

1. 첫 번째 줄: 정수 N과 K
   • 1 ≤ N ≤ 5,000,000, 1 ≤ K ≤ N
2. 두 번째 줄: 배열 A의 원소들
   • -10⁹ ≤ Aᵢ ≤ 10⁹

출력 조건

• 배열을 정렬했을 때 앞에서부터 K번째 수를 출력합니다.

💡 풀이 방법

이 문제는 크게 3단계로 해결할 수 있습니다:

1. 배열 입력받기
2. 오름차순 정렬하기
3. K번째 수 추출하기

🛠️ 코드 구현

Python을 사용하여 문제를 해결하는 코드는 다음과 같습니다:

# 입력 받기
import sys
input = sys.stdin.read
data = input().split()

# N: 배열의 길이, K: 찾고자 하는 위치
N, K = int(data[0]), int(data[1])
A = list(map(int, data[2:]))

# 배열을 정렬
A.sort()

# K번째 수 출력 (1-based index이므로 K-1 사용)
print(A[K - 1])

🔎 코드 설명

1️⃣ 입력 받기

• Python의 sys.stdin.read를 사용해 입력 데이터를 한 번에 받습니다.
• 첫 번째 줄에서 N(배열 길이)과 K(찾고자 하는 위치)를 가져옵니다.
• 두 번째 줄에서 배열 A를 리스트로 변환합니다.

2️⃣ 배열 정렬

• 배열 A를 sort() 메서드를 사용해 오름차순 정렬합니다.
  Python의 sort()는 Timsort 알고리즘을 기반으로 작동하며, 시간 복잡도는 **O(N log N)**입니다.

3️⃣ K번째 수 추출

• 배열은 0부터 시작하는 0-based index입니다. 따라서 K번째 수를 찾으려면 A[K-1]을 사용합니다.

🧩 예제 풀이

예제 입력

5 2
4 1 3 2 5

풀이 과정

1. 배열의 길이 N = 5, K번째 위치 K = 2
   배열 A = [4, 1, 3, 2, 5]
2. 배열 정렬:

A.sort() → [1, 2, 3, 4, 5]

3. K번째 수 추출:

A[K-1] = A[1] = 2

4. 출력 결과:

2

⏱️ 시간 복잡도 분석

1. 배열 정렬: 정렬의 시간 복잡도는 O(N log N)
2. K번째 수 추출: 상수 시간 O(1)

따라서 전체 시간 복잡도는 **O(N log N)**입니다.

📌 추가 팁: 더 효율적인 방법은 없을까?

만약 배열이 매우 커서 메모리나 시간 효율이 중요하다면, Quickselect 알고리즘을 사용해 K번째 수를 찾을 수 있습니다. Quickselect는 평균적으로 **O(N)**의 시간 복잡도로 실행됩니다. 그러나 이 문제에서는 Python의 내장 정렬을 사용하는 것이 가장 간단하고 안정적인 방법입니다.

✅ 마무리

배열에서 K번째 수를 찾는 문제는 정렬 알고리즘과 리스트 활용법을 연습할 수 있는 좋은 문제입니다. 이번 포스팅에서는 Python의 기본 정렬 메서드인 sort()를 사용하여 문제를 간단히 해결했지만, 다른 알고리즘을 적용해보는 것도 추천합니다!

TODAY TIL

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 일정 기준 이상으로 만들고 싶어합니다. 이 문제를 해결하기 위해 Python에서 **우선순위 큐(Priority Queue)**를 사용하여 효율적으로 푸는 방법을 소개합니다.

문제 설명

Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 아래의 규칙을 사용해 음식을 섞습니다:

1. 스코빌 지수가 가장 낮은 두 개의 음식을 선택합니다.
2. 이 두 음식을 섞어 새로운 음식의 스코빌 지수를 계산합니다: 섞은 음식의 스코빌 지수=가장 낮은 스코빌 지수+(두 번째로 낮은 스코빌 지수×2)\text{섞은 음식의 스코빌 지수} = \text{가장 낮은 스코빌 지수} + (\text{두 번째로 낮은 스코빌 지수} \times 2)섞은 음식의 스코빌 지수=가장 낮은 스코빌 지수+(두 번째로 낮은 스코빌 지수×2)
3. 모든 음식의 스코빌 지수가 K 이상이 될 때까지 위 과정을 반복합니다.

입력 조건:

• scoville: 각 음식의 스코빌 지수가 담긴 배열 (길이: 2 이상 1,000,000 이하).
• K: 목표 스코빌 지수 (0 이상 1,000,000,000 이하).

출력 조건:

• 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 반환합니다.
• 불가능한 경우 -1을 반환합니다.

문제 해결 접근법

이 문제는 최소값과 두 번째 최소값을 반복적으로 선택하는 작업이 필요하므로, **우선순위 큐(Priority Queue)**를 사용하는 것이 효율적입니다. Python에서는 heapq 모듈을 사용해 이를 간단히 구현할 수 있습니다.

풀이 과정

1. 힙으로 변환
   • heapq.heapify()를 사용해 입력 배열을 최소 힙으로 변환합니다.
   • 힙 구조를 사용하면 최소값을 빠르게 추출할 수 있습니다.
2. 반복 작업
   • 가장 작은 두 값을 추출하여 새로운 값을 계산합니다.
   • 계산된 값을 다시 힙에 삽입하고, 섞은 횟수를 증가시킵니다.
3. 종료 조건
   • 힙에서 가장 작은 값이 K 이상이면 작업을 종료하고 섞은 횟수를 반환합니다.
   • 힙에 하나의 값만 남았는데도 K 이상이 되지 않으면 불가능하므로 -1을 반환합니다.

Python 코드

import heapq

def solution(scoville, K):
    # 1. 배열을 최소 힙으로 변환
    heapq.heapify(scoville)
    mix_count = 0

    # 2. 반복적으로 가장 작은 두 값을 섞음
    while len(scoville) > 1:
        # 최소 두 개 값을 꺼내 섞기
        first = heapq.heappop(scoville)  # 가장 작은 값
        if first >= K:
            return mix_count  # 모든 값이 K 이상이므로 종료
        second = heapq.heappop(scoville)  # 두 번째로 작은 값
        new_scoville = first + (second * 2)
        heapq.heappush(scoville, new_scoville)  # 섞은 값 삽입
        mix_count += 1

    # 3. 힙에 하나만 남은 경우 확인
    if scoville[0] >= K:
        return mix_count
    else:
        return -1  # 모든 값을 K 이상으로 만들 수 없는 경우

예제 실행

입력

scoville = [1, 2, 3, 9, 10, 12]
K = 7

실행 과정

1. 초기 힙 구성: [1, 2, 3, 9, 10, 12]
2. 첫 번째 섞기:
   • 선택: 1, 2
   • 새 값: 1 + (2 * 2) = 5
   • 힙 상태: [3, 5, 9, 10, 12]
   • 섞은 횟수: 1
3. 두 번째 섞기:
   • 선택: 3, 5
   • 새 값: 3 + (5 * 2) = 13
   • 힙 상태: [9, 10, 12, 13]
   • 섞은 횟수: 2
4. 세 번째 섞기:
   • 선택: 9, 10
   • 새 값: 9 + (10 * 2) = 29
   • 힙 상태: [12, 13, 29]
   • 섞은 횟수: 3
5. 종료 조건 확인: 힙의 최솟값이 12로 K 이상이므로 종료.

출력

solution(scoville, K)  # 결과: 3

결과 및 시간 복잡도 분석

1. 결과: 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 최소 3번 섞어야 합니다.
2. 시간 복잡도:
   • 힙 연산(삽입, 삭제)의 시간 복잡도: O(log⁡N)O(\log N)O(logN)
   • 최대 N번 반복하므로 총 시간 복잡도: O(Nlog⁡N)O(N \log N)O(NlogN)

핵심 포인트 정리

• 힙 사용의 효율성: 최소값과 두 번째 최소값을 빠르게 추출하고 삽입.
• 종료 조건의 이해: 모든 값이 K 이상이 되는 순간 종료.
• 예외 처리: 모든 값을 K 이상으로 만들 수 없는 경우 -1 반환.

이 풀이를 통해 효율적인 문제 해결 방법과 Python에서 힙을 사용하는 기법을 배울 수 있었습니다. Leo의 매운맛 도전, 이제 여러분도 성공시켜 보세요! 🔥

TODAY TIL

다솜이는 사람의 마음을 읽는 기계를 이용해 국회의원 선거에서 자신을 찍지 않을 사람들을 매수하려고 합니다. 목표는 다른 후보들의 득표수를 초과하는 것입니다. 이 글에서는 다솜이가 최소 몇 명을 매수해야 당선될 수 있는지를 계산하는 방법을 설명합니다.

문제 설명

1. 입력 조건:
   • 후보 수 NNN이 주어집니다.
   • 각 후보의 득표수가 순서대로 입력됩니다.
   • 기호 1번 후보가 다솜이입니다.
2. 출력 조건:
   • 다솜이가 매수해야 하는 사람의 최소 수를 출력합니다.
3. 제약 조건:
   • 후보 수 NNN: 최대 50
   • 각 후보의 득표수: 최대 100
4. 예제 입력/출력

입력:

3
5
7
7

출력:

2

해결 방법

문제를 해결하기 위해 다음과 같은 단계로 접근합니다:

1. 입력 데이터를 읽기:
   • 후보 수와 각 후보의 득표수를 리스트로 저장합니다.
   • 다솜이의 득표수는 따로 저장하고, 나머지 후보들의 득표수를 관리합니다.
2. 매수 작업 반복:
   • 다른 후보들의 득표수를 내림차순으로 정렬합니다.
   • 가장 많은 득표수를 가진 후보를 매수하여 다솜이의 득표수를 증가시킵니다.
   • 다솜이의 득표수가 다른 모든 후보보다 많아질 때까지 이 작업을 반복합니다.
3. 매수 횟수 계산:
   • 매수 횟수를 카운트하면서, 다솜이의 득표수가 다른 후보들보다 많아질 때 결과를 출력합니다.

Python 코드

# 입력받기
N = int(input())  # 후보 수
votes = [int(input()) for _ in range(N)]  # 각 후보의 득표수

# 초기 설정
dasom_votes = votes[0]  # 다솜이의 득표수
other_votes = votes[1:]  # 다른 후보들의 득표수
bribes = 0  # 매수한 사람 수

# 매수 작업
while other_votes and max(other_votes) >= dasom_votes:
    # 가장 많은 득표수를 가진 후보의 표를 매수
    max_index = other_votes.index(max(other_votes))  # 최대값의 인덱스 찾기
    other_votes[max_index] -= 1  # 표 매수 (1 감소)
    dasom_votes += 1  # 다솜이의 표 증가
    bribes += 1  # 매수 횟수 증가

# 결과 출력
print(bribes)

코드 설명

1. 입력 처리:
   • 후보 수 NNN과 각 후보의 득표수를 입력받아 리스트로 저장합니다.
   • 다솜이의 득표수는 dasom_votes에, 나머지 후보들의 득표수는 other_votes 리스트로 관리합니다.
2. 매수 작업:
   • while 루프를 통해 다솜이의 득표수가 다른 후보들의 최대 득표수를 초과할 때까지 반복합니다.
   • 가장 많은 득표수를 가진 후보의 표를 하나 매수하고, 다솜이의 득표수를 증가시킵니다.
3. 결과 출력:
   • 매수 횟수는 bribes 변수에 저장되며, 반복이 끝나면 최솟값이 출력됩니다.

예제 실행

입력

3
5
7
7

출력

2

추가 설명

이 코드의 핵심은 다솜이의 득표수가 다른 후보들보다 많아질 때까지 반복적으로 매수하는 것입니다. 가장 득표수가 많은 후보를 우선 매수하는 전략을 사용하여 최솟값을 계산합니다.

최적화 고려사항

• 후보 수 NNN이 최대 50이므로, 매수 작업의 복잡도는 적절한 수준입니다.
• max\text{max}max 연산을 사용하는 만큼, 리스트 길이에 따라 작업 시간이 영향을 받을 수 있습니다.

마무리

이 문제는 그리디 알고리즘을 활용하여 반복적으로 최대값을 줄이는 전략을 사용합니다. 매수 전략을 효율적으로 구현하여 다솜이가 국회의원에 당선되도록 만드는 과정을 함께 배웠습니다.

코드와 예제 실행 결과를 참고하여 자신만의 해결 방법을 구현해 보세요! 😊

TODAY TIL

안녕하세요 오늘은 grid라는 2차원 배열에서 각 행의 최대 값을 제거하고, 그 값들 중 가장 큰 값을 누적하여 최종 결과를 반환하는 문제를 다루어 보겠습니다. 문제를 단계별로 설명하고, Python 코드와 풀이 과정을 함께 살펴보겠습니다.

문제 설명

주어진 grid는 다음과 같은 2차원 리스트입니다:

grid = [
    [3, 1, 2],
    [5, 4, 6],
    [9, 8, 7]
]

이제 각 반복 단계마다 각 행의 최대 값을 제거한 후, 그 값들 중 가장 큰 값을 누적해 나가는 과정을 반복해야 합니다. grid의 모든 행이 비어 있을 때까지 이 작업을 수행한 후 누적된 값을 반환합니다.

풀이 순서

1. answer라는 변수를 초기화하여 결과를 저장합니다.
2. grid[0]이 비어있지 않을 동안 반복문을 실행합니다.
3. 각 행(row)에서 max() 함수를 사용해 가장 큰 값을 찾습니다.
4. 찾은 값을 max_vals 리스트에 추가하고, 해당 값을 해당 행에서 제거합니다.
5. max_vals 리스트에서 가장 큰 값을 찾아 answer에 더합니다.
6. 모든 행이 비어있으면 반복문을 종료하고, 최종 answer를 반환합니다.

코드 설명

다음은 문제를 해결하기 위한 Python 코드입니다

class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        answer = 0  # 결과를 저장할 변수 초기화
        # grid[0]이 비어있지 않을 동안 반복
        while grid[0]:
            max_vals = []  # 각 행에서 찾은 최대 값을 저장할 리스트
            for row in grid:
                max_val = max(row)  # 각 행에서 최대 값을 찾음
                max_vals.append(max_val)  # 최대 값을 리스트에 추가
                row.remove(max_val)  # 행에서 최대 값을 제거
            answer += max(max_vals)  # 최대 값들 중에서 가장 큰 값을 answer에 더함
        return answer  # 최종 결과 반환

단계별 예제

입력 예제

grid가 다음과 같다고 가정합니다:

grid = [
    [3, 1, 2],
    [5, 4, 6],
    [9, 8, 7]
]

실행 단계 설명

1. 첫 번째 반복:
   • 각 행에서 최대 값을 찾습니다: [3, 6, 9]
   • 가장 큰 값은 9이며, answer는 9가 됩니다.
   • 업데이트된 grid:
      

grid = [
    [1, 2],
    [4, 5],
    [8, 7]
]

두 번째 반복:

• 각 행에서 최대 값을 찾습니다: [2, 5, 8]
• 가장 큰 값은 8이며, answer는 9 + 8 = 17이 됩니다.
• 업데이트된 grid:
   

grid = [
    [1],
    [4],
    [7]
]

세 번째 반복:

• 각 행에서 최대 값을 찾습니다: [1, 4, 7]
• 가장 큰 값은 7이며, answer는 17 + 7 = 24가 됩니다.
• 업데이트된 grid는 비어 있습니다:
   

grid = [
    [],
    [],
    []
]

최종 결과

모든 행이 비어 있으므로 반복을 종료하고, answer는 24입니다.

시간 복잡도 분석

• 각 행에서 최대 값을 찾는 작업은 O(n)O(n)O(n)이며, 이를 mmm개의 행에 대해 수행하므로 시간 복잡도는 O(m×n)O(m \times n)O(m×n)입니다.
• m은 행의 수, n은 열의 수입니다.

결론

이 문제는 반복문과 리스트 연산을 활용해 각 행의 최대 값을 계속 제거하면서 누적 합을 구하는 문제입니다. 문제의 핵심은 각 반복마다 각 행의 최대 값을 효율적으로 찾고 제거하는 것입니다.

이 코드와 풀이가 여러분의 이해에 도움이 되었기를 바랍니다. 궁금한 점이나 다른 해석이 있다면 댓글로 남겨주세요!

TODAY TIL

안녕하세요! 오늘은 선물 더미에서 가장 많은 선물을 가져가고 남은 선물을 계산하는 문제를 풀어보겠습니다. 이 문제는 선물 더미 중 가장 큰 값을 선택하고, 해당 더미에서 ⌊제곱근⌋만 남기고 나머지를 가져가는 과정을 k초 동안 반복한 후 남은 선물의 총합을 구하는 문제입니다.

문제 설명

문제

주어진 정수 배열 gifts는 다양한 더미에 있는 선물의 개수를 나타냅니다. 매초마다 가장 많은 선물이 있는 더미를 선택하여 ⌊제곱근⌋만 남겨두고 나머지를 가져갑니다. k초 동안 이 작업을 반복하고 최종적으로 남은 모든 선물의 총합을 반환합니다.

예시

입력

gifts = [25, 64, 9, 4, 100]
k = 4

출력

29

설명

• 첫 번째 초: 100을 선택하여 ⌊√100⌋ = 10을 남김 → [25, 64, 9, 4, 10]
• 두 번째 초: 64를 선택하여 ⌊√64⌋ = 8을 남김 → [25, 8, 9, 4, 10]
• 세 번째 초: 25를 선택하여 ⌊√25⌋ = 5를 남김 → [5, 8, 9, 4, 10]
• 네 번째 초: 10을 선택하여 ⌊√10⌋ = 3을 남김 → [5, 8, 9, 4, 3]
• 최종 남은 선물의 총합: 29

문제 풀이

접근 방법

• gifts 배열을 최대 힙(max heap)으로 변환하여 가장 큰 값을 효율적으로 가져옵니다.
• k번 동안 가장 큰 값의 선물을 가져가고 남은 ⌊제곱근⌋ 값을 다시 힙에 넣습니다.
• heapq 모듈을 활용해 효율적으로 최대값을 찾고, ⌊제곱근⌋을 계산하여 힙을 업데이트합니다.

코드 구현

다음은 문제를 해결하기 위한 Python 코드입니다.

import heapq
import math

def remaining_gifts(gifts, k):
    # 최대 힙으로 변환하기 위해 음수로 저장
    max_heap = [-gift for gift in gifts]
    heapq.heapify(max_heap)
    
    for _ in range(k):
        # 가장 큰 값 꺼내기
        max_gift = -heapq.heappop(max_heap)
        # 제곱근을 구해 남은 선물 수 계산
        remaining_gift = math.floor(math.sqrt(max_gift))
        # 남은 선물 다시 힙에 삽입
        heapq.heappush(max_heap, -remaining_gift)
    
    # 남은 선물의 총합 구하기
    return -sum(max_heap)

# 예시 실행
print(remaining_gifts([25, 64, 9, 4, 100], 4))  # 출력: 29
print(remaining_gifts([1, 1, 1, 1], 4))  # 출력: 4

코드 설명

1. gifts 배열을 최대 힙으로 변환합니다. Python의 heapq는 최소 힙만 지원하므로 음수로 값을 넣어 최대 힙처럼 사용합니다.
2. k번 반복하며, 가장 큰 값을 꺼내 ⌊제곱근⌋을 계산한 후 다시 힙에 넣습니다.
3. 모든 작업이 끝난 후 힙에 남은 값들을 합산하여 반환합니다.

시간 복잡도

• 힙을 사용하는 삽입 및 삭제의 시간 복잡도는 O(log n)이며, 이를 k번 반복하므로 전체 시간 복잡도는 O(k log n)입니다.

결론

이 코드는 주어진 문제 조건을 충족하면서 효율적으로 풀 수 있는 방법을 제시합니다. heapq와 math 모듈을 적절히 사용하여 최대값을 찾고 갱신하는 과정을 손쉽게 구현할 수 있습니다.

이 글이 여러분의 문제 해결에 도움이 되었기를 바랍니다. 질문이나 추가적인 설명이 필요하면 댓글로 남겨주세요!

TODAY TIL

안녕하세요, 오늘은 재미있는 코딩 문제를 함께 풀어보겠습니다. 이 문제는 센티라는 캐릭터가 마법의 뿅망치를 사용하여 자신보다 키가 큰 거인들을 줄여야 하는 상황입니다. 어떤 전략을 세우고 어떻게 코드를 구현했는지 차근차근 설명하겠습니다.

문제 설명

센티는 여행 중 거인의 나라에 도착했습니다. 그곳에는 자신보다 키가 크거나 같은 거인들이 많았는데, 센티는 이들을 마법의 뿅망치를 이용해 키를 줄이려 합니다. 마법의 뿅망치에 맞으면 키는 ⌊현재 키 / 2⌋로 줄어듭니다. 단, 키가 1이면 더 이상 줄어들지 않습니다. 이 마법의 뿅망치는 사용 횟수 제한이 있습니다.

목표: 센티가 마법의 뿅망치를 전략적으로 사용해 모든 거인이 센티보다 키가 작아지게 할 수 있는지를 판단하고, 그 과정에서 최소 사용 횟수를 출력합니다.

입력 형식

• 첫 번째 줄에 거인의 수 N, 센티의 키 HcentiH_{\text{centi}}Hcenti​, 마법의 뿅망치 사용 제한 T가 주어집니다.
• 두 번째 줄부터 N개의 줄에 각 거인의 키가 주어집니다.

출력 형식

• 마법의 뿅망치를 사용하여 모든 거인의 키가 HcentiH_{\text{centi}}Hcenti​보다 작다면 "YES"와 사용한 횟수를 출력합니다.
• 그렇지 않다면 "NO"와 뿅망치 사용 후 가장 큰 거인의 키를 출력합니다.

문제 풀이 접근법

1. 최대 힙을 이용한 거인 선택:
   • 거인들 중 가장 키가 큰 거인을 빠르게 선택하기 위해 최대 힙을 사용합니다.
   • Python의 heapq 모듈은 기본적으로 최소 힙이므로, 음수로 변환하여 최대 힙처럼 사용합니다.
2. 마법의 뿅망치 사용 전략:
   • 가장 키가 큰 거인을 때리고 줄어든 키를 다시 최대 힙에 넣습니다.
   • 키가 1인 경우는 줄일 수 없으므로 무시합니다.
   • 제한된 사용 횟수 T를 초과하지 않도록 합니다.
3. 결과 판단:
   • 마법의 뿅망치를 사용한 후, 모든 거인의 키가 HcentiH_{\text{centi}}Hcenti​보다 작으면 성공이고, 그렇지 않다면 실패입니다.

코드 구현

import heapq

# 입력 처리
N, H_centi, T = map(int, input().split())
giants = []

for _ in range(N):
    height = int(input())
    heapq.heappush(giants, -height)  # 최대 힙을 위해 음수로 저장

# 마법의 뿅망치 사용 횟수 카운트
use_count = 0

# 뿅망치 사용
while use_count < T and -giants[0] >= H_centi:
    tallest = -heapq.heappop(giants)
    
    if tallest == 1:
        # 키가 1이면 더 이상 줄어들 수 없음
        heapq.heappush(giants, -tallest)
        break
    
    # 뿅망치를 사용하여 키 줄이기
    new_height = tallest // 2
    heapq.heappush(giants, -new_height)
    use_count += 1

# 결과 확인
if -giants[0] < H_centi:
    print("YES")
    print(use_count)
else:
    print("NO")
    print(-giants[0])

코드 설명

1. 입력 처리:
   • 첫 번째 줄에서 거인의 수, 센티의 키, 마법의 뿅망치 사용 제한을 읽어옵니다.
   • 각 거인의 키를 음수로 변환하여 최대 힙에 저장합니다.
2. 반복문:
   • 최대 TTT번의 반복 동안 가장 키가 큰 거인을 선택하여 키를 절반으로 줄입니다.
   • 줄어든 키는 다시 힙에 삽입하여 다음 최댓값을 구할 수 있도록 합니다.
   • 키가 1인 거인은 더 이상 줄일 수 없으므로 바로 종료합니다.
3. 출력:
   • 모든 거인의 키가 센티보다 작아졌다면 YES와 사용 횟수를 출력합니다.
   • 그렇지 않다면 NO와 가장 큰 거인의 키를 출력합니다.

시간 및 공간 복잡도

• 시간 복잡도: O((T+N)log⁡N)O((T + N) \log N)O((T+N)logN)
• 공간 복잡도: O(N)O(N)O(N)

결론

이 문제는 우선순위 큐를 이용하여 가장 큰 값을 효율적으로 처리하는 방법과 제한된 자원을 최적화하여 사용하는 전략을 익히는 데 유용합니다. 블로그 포스팅을 통해 이와 같은 문제의 해결 방법을 체계적으로 학습해 보세요!

이제 여러분도 센티와 함께 거인의 나라를 정복해 보세요! 😊