공부블로그

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

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

문제의 배경

입학 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)

결론

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

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

TODAY TIL

안녕하세요! 여러분이 코딩 테스트에서 마주할 수 있는 흥미로운 문제를 소개합니다. 이 문제는 주어진 N×N  크기의 표에서 N번째로 큰 수를 찾아내는 것입니다. 표의 숫자들은 각자의 위에 있는 숫자보다 크도록 구성되어 있습니다. 예를 들어, N=5N = 5N=5일 때 다음과 같은 표가 있을 수 있습니다

12  7   9  15  5
13  8  11  19  6
21 10  26  31 16
48 14  28  35 25
52 20  32  41 49

이 표에서 다섯 번째로 큰 수를 찾아야 합니다.

입력 설명

• 첫 번째 줄에는 정수 NNN이 주어집니다 (1≤N≤1,5001 \leq N \leq 1,5001≤N≤1,500).
• 그 다음 NNN개의 줄에는 각 줄마다 NNN개의 정수가 주어집니다.
• 숫자들은 −109-10^9−109 이상 10910^9109 이하의 범위를 가지며, 모두 다릅니다.

출력 설명

• 프로그램은 NNN번째로 큰 수를 출력해야 합니다.

해결 전략

이 문제는 단순히 표를 정렬하여 NNN번째로 큰 수를 찾는 방식으로는 효율적이지 않습니다. NNN의 최대값이 1,500이므로 표에 있는 요소의 수는 최대 2,250,000개가 됩니다. 이 큰 데이터를 다룰 때 메모리와 시간 복잡도를 고려해야 합니다.

최적의 해결책은 다음과 같습니다:

1. 최소 힙(min-heap)을 사용하여 NNN개의 가장 큰 수를 유지합니다.
2. 한 줄씩 입력을 받아 즉시 처리하여 메모리 사용을 줄입니다.

코드 설명

이제 문제를 해결하는 코드를 단계별로 설명하겠습니다.

import sys
import heapq

# 입력을 빠르게 받기 위해 sys.stdin을 사용
input = sys.stdin

# N을 입력받음
N = int(input.readline().strip())
min_heap = []  # 최소 힙을 저장할 리스트

# N개의 행에 대해 각 숫자를 읽어들임
for _ in range(N):
    row = map(int, input.readline().split())  # 한 줄의 숫자를 공백 기준으로 분리하여 처리
    for num in row:
        # 힙의 크기가 N보다 작은 경우 숫자를 추가
        if len(min_heap) < N:
            heapq.heappush(min_heap, num)
        else:
            # N개의 숫자가 이미 힙에 있으면, 새로운 숫자가 최소값보다 큰 경우 교체
            if num > min_heap[0]:
                heapq.heappushpop(min_heap, num)

# 힙의 최솟값이 N번째로 큰 수가 됨
print(min_heap[0])

코드 설명 (더 자세히)

• heapq 모듈은 Python에서 힙 자료구조를 다룰 수 있는 모듈입니다. 이 문제에서는 최소 힙을 사용해 NNN개의 가장 큰 수를 유지합니다.
• sys.stdin.readline(): 표의 크기가 크기 때문에, 입력을 빠르게 받기 위해 input() 대신 sys.stdin.readline()을 사용했습니다. 이는 큰 입력을 더 효율적으로 처리합니다.
• 히프 유지: 힙에 NNN개의 요소만 유지하여 메모리를 절약합니다. 새로운 숫자가 힙의 최솟값보다 클 경우에만 추가하고 기존 최소값을 제거합니다.

예제 실행

입력 예시

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

이 경우, 다섯 번째로 큰 수는 35입니다. 프로그램은 이 값을 올바르게 출력합니다.

시간 및 공간 복잡도 분석

• 시간 복잡도: O(N2log⁡N)O(N^2 \log N)O(N2logN). 각 숫자마다 힙 연산이 O(log⁡N)O(\log N)O(logN)이고 총 N2N^2N2개의 숫자를 처리합니다.
• 공간 복잡도: O(N)O(N)O(N). 힙의 크기는 항상 NNN으로 유지되므로 메모리 사용량이 제한적입니다.

결론

이 접근법은 메모리와 시간 효율성을 모두 고려하여 NNN번째로 큰 수를 찾는 데 적합합니다. 만약 여러분이 비슷한 문제나 더 좋은 최적화 방법을 알고 있다면 댓글로 알려주세요!

이제 이 코드와 설명을 통해 여러분도 이 문제를 해결할 수 있기를 바랍니다. 코딩 테스트나 실무 프로젝트에서도 도움이 되길 바랍니다!