공부블로그

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

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

문제의 배경

입학 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 연산을 사용하는 만큼, 리스트 길이에 따라 작업 시간이 영향을 받을 수 있습니다.

마무리

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

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