[복습] 파이썬 배우기 50~100

Leejaegun·2025년 10월 11일

코딩테스트 시리즈

목록 보기

45/49

1.24시

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

✅ 최종 코드

time = []
for _ in range(2):
    h, m, s = map(int, input().split(":"))
    time.append([h, m, s])

# (1) 시각을 초 단위로 변환
start = time[0][0]*3600 + time[0][1]*60 + time[0][2]
end   = time[1][0]*3600 + time[1][1]*60 + time[1][2]

# (2) 다음날로 넘어가는 경우 (예: 23:50:00 → 00:10:00)
if end < start:
    end += 24 * 3600

# (3) 두 시각의 차이 계산
diff = end - start

# (4) 초 단위를 다시 시/분/초로 분해
_h = diff // 3600
_m = (diff % 3600) // 60
_s = diff % 60

# (5) 두 자리로 맞춰서 출력
print(f"{_h:02d}:{_m:02d}:{_s:02d}")

✅ 전체 로직 요약

이 문제는 현재 시각과 임무 시작 시각이 주어졌을 때,
임무 시작까지 남은 시간 차이를 계산하는 문제입니다.

① 시간을 초 단위로 변환하기

시(h), 분(m), 초(s)는 각각 다음과 같이 초로 환산할 수 있습니다:

[
\text{total seconds} = h \times 3600 + m \times 60 + s
]

start = time[0][0]*3600 + time[0][1]*60 + time[0][2]
end   = time[1][0]*3600 + time[1][1]*60 + time[1][2]

이렇게 하면 두 시각을 단순 정수(초 단위)로 비교할 수 있습니다.

② 다음날로 넘어가는 경우 처리

만약 종료 시각이 시작 시각보다 작다면(예: 23:59:59 → 00:10:00),
이는 다음날로 넘어간 경우입니다.
따라서 24시간(= 24×3600초)을 더해줍니다.

if end < start:
    end += 24*3600

③ 시간 차이(초 단위) 계산 후 다시 시/분/초로 분해

두 시각의 차이를 구한 뒤(diff = end - start),
이를 다시 시/분/초 단위로 환산합니다.

_h = diff // 3600                   # 총 시(hour)
_m = (diff % 3600) // 60            # 남은 분(minute)
_s = diff % 60                      # 남은 초(second)

이 계산의 원리는 다음과 같습니다:

diff // 3600 → 전체 초 중에서 몇 시간이 되는지
(diff % 3600) // 60 → 남은 초에서 몇 분이 되는지
diff % 60 → 남은 초

④ 출력 형식 맞추기 (`{:02d}`)

{:02d}는 정수를 최소 두 자리로 출력하되, 한 자리일 경우 왼쪽에 0을 채워줍니다.

print(f"{_h:02d}:{_m:02d}:{_s:02d}")

예시:

입력	출력
`12:30:30`, `14:10:10`	`01:39:40`
`23:50:00`, `00:10:00`	`00:20:00`

📘 정리 요약

단계	내용	코드 핵심
(1)	시각을 초 단위로 변환	`total = h3600 + m60 + s`
(2)	다음날로 넘어가면 24시간 추가	`if end < start: end += 24*3600`
(3)	시간 차이 계산	`_h = diff//3600`, `_m = (diff%3600)//60`, `_s = diff%60`
(4)	두 자리 0채움 출력	`f"{_h:02d}:{_m:02d}:{_s:02d}"`

2. 피보나치

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

✅ 기본 재귀 피보나치

def fibo(n: int) -> int:
    if n == 1 or n == 2:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

정의 그대로 구현한 직관적인 방식
하지만 fibo(n-1)과 fibo(n-2)가 중복 호출되어 비효율적
시간 복잡도: O(2^n) → 매우 느림 (n > 30이면 사실상 불가능)

⚙️ 개선: 메모이제이션 (Memoization)

memo = {1: 1, 2: 1}

def fibo(n: int) -> int:
    if n in memo:                   # 이미 계산된 값이면 그대로 반환
        return memo[n]
    memo[n] = fibo(n-1) + fibo(n-2) # 계산 결과 저장
    return memo[n]

이미 계산한 값을 memo(dictionary)에 저장
중복 호출 제거 → 한 번 계산한 값은 다시 안 구함
n in memo는 key(=n) 존재 여부 검사
시간 복잡도: O(n)
공간 복잡도: O(n) (계산된 값 저장용)

📘 요약 비교

방식	중복 호출	시간 복잡도	비고
기본 재귀	많음	O(2ⁿ)	느림
메모이제이션	없음	O(n)	빠름

즉,
“시간복잡도를 신경 안 쓰면 기본 재귀로,
하지만 실제 문제에서는 반드시 메모이제이션으로.”

내 학점을 구해줘
https://www.acmicpc.net/problem/10984

from collections import defaultdict
import sys

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    grade = defaultdict(list)          # key: 학점(int), value: 평점들(list)
    for _ in range(N):
        a_str, b_str = input().split()
        a = int(float(a_str))          # "3"도 "3.0"도 안전하게 처리
        b = float(b_str)               # 평점은 실수
        grade[a].append(b)

    credit = 0                         # 총 학점(분모)
    weighted_sum = 0.0                 # Σ(학점 × 평점) (분자)
    for k, v_list in grade.items():
        credit += k * len(v_list)      # 같은 학점 과목 수만큼 가중
        weighted_sum += k * sum(v_list)

    avg = weighted_sum / credit if credit else 0.0
    print(f"{credit} {avg:.1f}")

🧩 이번 문제에서 배운 핵심 정리

(1) 입력 속도 최적화

sys.stdin.readline() 을 쓰면 input()보다 훨씬 빠르다.
백준처럼 입력이 많을 때는 반드시 아래처럼 쓰는 것이 관례다.
```
import sys
input = sys.stdin.readline
```

(2) 딕셔너리에 같은 key 여러 value 넣기

grade[key] = value 는 기존 key를 덮어쓴다.
같은 key에 여러 값을 저장하려면 리스트에 append 해야 한다.
따라서 defaultdict(list) 구조를 써야 안전하다.
```
from collections import defaultdict
grade = defaultdict(list)
grade[a].append(b)
```
이렇게 하면 같은 key가 여러 번 들어와도 value가 리스트에 누적된다.

(3) 학점평균(GPA)은 가중평균

단순 평균이 아니라 “학점 × 평점”의 합 ÷ 학점 총합으로 계산한다.
```
avg = (Σ(학점 × 평점)) / (Σ학점)
```
→ 학점이 높을수록 평균에 더 큰 영향력을 가진다.
GPA 공식:

$\text{GPA}=\frac{\sum (\text{학점}\times \text{평점})}{\sum \text{학점}}$
같은 학점이 여러 번 나오면 그만큼 가중치가 여러 번 적용되어야 한다.
그래서 credit += k * len(v_list), weighted_sum += k * sum(v_list).

(4) 출력 포맷 제어 (:.1f)

:.1f는 소수점 이하 1자리까지 표시.
예:
```
print(f"{avg:.1f}")  # → 3.7
```
→ .2f면 둘째 자리, .0f면 정수까지만 표시.

빠른 입력(sys), 중복 key 처리(defaultdict),
가중평균(GPA), 출력 형식(f-string 포맷)
이 네 가지가 이번 문제의 핵심 학습 포인트입니다.

3.도미노

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

from itertools import combinations_with_replacement
import sys
input = sys.stdin.readline
N = int(input())
nums = [i for i in range(N+1)]
combs = combinations_with_replacement(nums,2)
total = 0
for comb in combs:
    a,b = comb
    total += (a+b)
print(total)

(1) `itertools` vs `collections`

itertools는 반복 가능한(iterable) 객체를 효율적으로 조합, 순열, 카테시안 곱 등을 만들 때 사용하는 모듈입니다.

주요 함수:
- combinations(iterable, r) — 순서를 고려하지 않고 r개 조합 (중복 X)
- combinations_with_replacement(iterable, r) — 순서를 고려하지 않고 r개 조합 (중복 O)
- permutations(iterable, r) — 순서를 고려하는 r개 순열
- product(iter1, iter2, ...) — 데카르트 곱 (모든 조합)

예시:

from itertools import combinations, combinations_with_replacement, permutations, product

collections는 자료구조 관련 도구들이 들어있는 모듈입니다.

자주 쓰는 클래스:
- Counter: 빈도수 계산
- defaultdict: 기본값을 자동으로 생성하는 dict
- deque: 양방향 큐

예시:

from collections import Counter
c = Counter(['a', 'b', 'a', 'c', 'b', 'a'])
print(c.most_common(1))  # [('a', 3)]

Counter.most_common(0)은 인자 n이 "상위 n개"를 뜻하므로, most_common(1)처럼 써야 함.
most_common(0)은 빈 리스트를 반환함.

(2) `sys.stdin.readline` 사용 이유

input()은 Python 내부적으로 I/O 버퍼 처리를 거치기 때문에 대량의 입력을 다룰 때 매우 느립니다.
특히 백준이나 프로그래머스 같이 반복적으로 입력받는 환경에서는 시간초과가 날 수 있습니다.

해결 방법:

import sys
input = sys.stdin.readline

이렇게 하면 C 레벨에서 한 번에 입력 버퍼를 처리하므로 속도가 수십 배 빨라집니다.
단, 이 경우 \n이 포함되어 들어오므로 rstrip()으로 개행 제거하는 것이 좋습니다.

예시:

N = int(input().rstrip())

(정리)

itertools → 반복 조합용 (combinations, permutations, product 등)
collections → 자료구조용 (Counter, defaultdict, deque 등)
sys.stdin.readline → 빠른 입력 (특히 반복문에서 필수)
input()보다 훨씬 빠름, 대신 rstrip() 필요

즉,
itertools는 조합/순열
collections는 자료구조
sys.stdin.readline은 빠른 입력 처리

이 세 가지 구분만 명확히 잡으면 코테 기본 입출력 세팅은 완벽합니다.

4. 소수

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

import sys
input = sys.stdin.readline
M = int(input())
N = int(input())
ans = []
def is_prime(n:int) -> bool:
    if n < 2:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

for i in range(M,N+1):
    if is_prime(i):
        ans.append(i)

if ans:
    print(sum(ans))
    print(min(ans))
else:
    print(-1)

(1) `is_prime()` 작성 시 핵심 고려사항

1 이하의 수는 소수가 아님
→ if n < 2: return False
(0과 1을 제외해야 함)
제곱근까지만 탐색할 때는 정수 변환 필요
n**0.5는 실수(float)이므로
range(2, int(n**0.5) + 1) 형태로 int()로 형변환해야 함.
그렇지 않으면 TypeError: 'float' object cannot be interpreted as an integer 발생함.

(2) 리스트 합계 계산 시 주의점

ans가 [3, 5, 7, 11]처럼 숫자 리스트라면
sum(ans) 만으로 전체 합을 구할 수 있음.
sum(i) for i in ans는 잘못된 문법 (제너레이터로 동작).
즉, sum(ans) 하나면 충분하다.
sum(sum(i) for i in ans)는 ans가 “리스트 안에 리스트가 있는” 구조일 때만 사용.

✅ 정리 문장

(1) is_prime을 만들 때는

n < 2인 경우도 고려해야 하고,
제곱근 탐색 시 range(2, int(n**0.5) + 1)처럼 int()로 정수 변환해야 한다.

(2) ans가 숫자 리스트라면 sum(ans)만 쓰면 된다.
sum(i) for i in ans처럼 쓸 필요가 없으며, 이는 오히려 오류를 유발한다.

5. sort, sorted

딱 “원본을 바꾸느냐, 새 걸 만드느냐” 이 차이입니다.

🔹 핵심 요약

구분	`list.sort()`	`sorted(iterable)`
리턴값	`None` (제자리 정렬)	정렬된 새 리스트 반환
원본 변화	O (바뀜)	X (안 바뀜)
사용 대상	리스트만 가능	모든 iterable (문자열, 튜플, 집합 등)
문법	`리스트.sort()`	`sorted(이터러블)`

🔹 예시 1 — 차이 확인

nums = [3, 1, 2]

# 1) sort()
nums.sort()
print(nums)  # [1, 2, 3]
# 원본이 바뀜

# 2) sorted()
nums = [3, 1, 2]
print(sorted(nums))  # [1, 2, 3]
print(nums)          # [3, 1, 2]
# 원본은 그대로

🔹 예시 2 — 반환값 차이

nums = [5, 3, 1]
a = nums.sort()
b = sorted(nums)

print(a)  # None
print(b)  # [1, 3, 5]

👉 sort()는 결과를 반환하지 않는다.
👉 sorted()는 새 리스트를 반환한다.

🔹 예시 3 — key와 reverse 공통 옵션

둘 다 같은 인자를 쓸 수 있음.

nums = [3, 10, 2, 5]

nums.sort(key=lambda x: x % 3, reverse=True)
# key: 정렬 기준, reverse: 역순

# sorted도 똑같이 가능
new_nums = sorted(nums, key=lambda x: x % 3, reverse=True)

✅ 기억법

sort()는 제자리에서 정렬하고, sorted()는 새로 만들어낸다.

좀 비유하자면

sort() = 방 청소 → 같은 방 깨끗하게 만듦
sorted() = 복사해서 새 집 만들어 정리함 (원래 집 그대로)

💡 한 줄 정리

sort()는 원본 수정,
sorted()는 새 리스트 생성.
둘 다 key, reverse 사용 가능.

6. 점수계산

import sys
input = sys.stdin.readline

N = int(input())
store = []
store = list(map(int,input().split()))

total = 0
streak = 0
for i in store:

    if i ==1:
        streak += 1
        total +=streak
    else:
        streak = 0

print(total)

✅ 배운점 정리

(1) 가변적인 입력을 한 줄로 받을 때

입력 개수가 고정되어 있지 않고 한 줄에 공백으로 구분되어 있을 때는
list(map(int, input().split())) 형태로 한 번에 리스트로 받을 수 있다.
예를 들어
```
store = list(map(int, input().split()))
```
이렇게 하면 1 0 1 1 0 → [1, 0, 1, 1, 0] 형태로 저장된다.
이때는 굳이 for _ in range(N): 반복문으로 받을 필요가 없다.

(2) 연속 정답에 따른 가산점 계산 로직

연속된 1이 있을 때마다 보너스 점수를 더하려면 다음 두 변수가 필요하다.
1. streak (연속 카운트 변수) → 1이 연속될 때마다 +1, 0 나오면 0으로 초기화
2. total (누적 점수 변수) → 매번 streak 값을 더함

핵심 구조:

streak = 0
total = 0
for x in store:
    if x == 1:
        streak += 1
        total += streak
    else:
        streak = 0

🧩 요약 문장

공백으로 나뉜 여러 개의 입력값은 list(map(int, input().split())) 으로 한 번에 처리한다.
“연속 가산점” 문제는
- 연속 횟수를 세는 변수(streak)와
- 전체 점수를 누적하는 변수(total) 두 개만 정의하면 깔끔하게 해결된다.

7. 완전제곱수

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

M = int(input())
N = int(input())
ans = []
for i in range(M,N+1):
    if int(i**0.5) == i**0.5:
        ans.append(i)

if ans:
    print(sum(ans))
    print(min(ans))
else:
    print(-1)

#print(f"{sum(ans)} \n {min(ans)}")

핵심 로직

i**0.5로 제곱근을 구한다.
제곱근이 정수인 경우(int(i**0.5) == i**0.5)만 리스트에 추가한다.
리스트가 비었으면 -1, 아니면 합계와 최솟값 출력.

정리 포인트

int() 형변환을 통해 부동소수 오차를 제거해야 한다.
제곱근 비교 시 실수 연산의 정확도 문제를 방지한다.
range(M, N+1)로 구간을 닫아서 마지막 수 포함.

8. 생일

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

T = int(input())
infos = []
for _ in range(T):
    name, day, month, year =input().split()
    infos.append([int(year),int(month),int(day),name])

#year 는 오름차순 나머지 month,day는 내림차순
infos.sort(key=lambda x:(x[0],x[1],x[2]))
print(infos[-1][3])
print(infos[0][3])

배운점
(1) 한번에 map(int, input().split())하는 것보다
형이 다르면 따로 해주는게 좋다는 걸 느낌
(2) .sort는 제자리, sorted()는 새리스트 만듦
그리고 key = lambda 라는 임시 함수를 통해서 오름차순, 내림차순으로 만들 수 있음
핵심 로직

이름, 생년월일 입력받아 [year, month, day, name] 형태로 저장.
infos.sort(key=lambda x: (x[0], x[1], x[2])) 로 오름차순 정렬.
→ 첫 요소부터 차례로 비교하므로 (year, month, day) 기준 정렬.
가장 늙은 사람은 infos[0], 가장 어린 사람은 infos[-1].

정리 포인트

서로 다른 자료형(str, int)을 섞어 입력받을 때는 map(int, …) 대신 직접 형변환하는 게 안전하다.
list.sort()는 제자리 정렬(in-place), sorted()는 새 리스트 반환.
lambda 표현식으로 다중 기준 정렬이 가능하다.

9. 최소공배수와 최대공약수

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

10.지능형기차

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

import sys
input = sys.stdin.readline
max_people = 0
total = 0
for _ in range(4):
    n1,n2 = map(int,input().split())
    total += (n2-n1)
    max_people = max(max_people, total)

print(max_people)

배운점
(1) max_people 의 변수를 정하고
total이랑 비교

그러니까 쉬운데... 이걸 생각하기가 쉽지 않았다 (멍청..)

Leejaegun

Lee_AA

이전 포스트

[복습] 백준_파이썬배우기(1~50)

다음 포스트

[복습] 파이썬 배우기 50~100

코딩테스트 시리즈

1.24시

✅ 최종 코드

✅ 전체 로직 요약

① 시간을 초 단위로 변환하기

② 다음날로 넘어가는 경우 처리

③ 시간 차이(초 단위) 계산 후 다시 시/분/초로 분해

④ 출력 형식 맞추기 (`{:02d}`)

📘 정리 요약

2. 피보나치

✅ 기본 재귀 피보나치

⚙️ 개선: 메모이제이션 (Memoization)

📘 요약 비교

3.도미노

(1) `itertools` vs `collections`

(2) `sys.stdin.readline` 사용 이유

(정리)

4. 소수

(1) `is_prime()` 작성 시 핵심 고려사항

(2) 리스트 합계 계산 시 주의점

✅ 정리 문장

5. sort, sorted

🔹 핵심 요약

🔹 예시 1 — 차이 확인

🔹 예시 2 — 반환값 차이

🔹 예시 3 — key와 reverse 공통 옵션

✅ 기억법

💡 한 줄 정리

6. 점수계산

✅ 배운점 정리

🧩 요약 문장

7. 완전제곱수

8. 생일

9. 최소공배수와 최대공약수

10.지능형기차

[복습] 백준_파이썬배우기(1~50)

[복습] 알고리즘 기초 1/2 200-자료구조1

0개의 댓글

[복습] 파이썬 배우기 50~100

코딩테스트 시리즈

1.24시

✅ 최종 코드

✅ 전체 로직 요약

① 시간을 초 단위로 변환하기

② 다음날로 넘어가는 경우 처리

③ 시간 차이(초 단위) 계산 후 다시 시/분/초로 분해

④ 출력 형식 맞추기 ({:02d})

📘 정리 요약

2. 피보나치

✅ 기본 재귀 피보나치

⚙️ 개선: 메모이제이션 (Memoization)

📘 요약 비교

3.도미노

(1) itertools vs collections

(2) sys.stdin.readline 사용 이유

(정리)

4. 소수

(1) is_prime() 작성 시 핵심 고려사항

(2) 리스트 합계 계산 시 주의점

✅ 정리 문장

5. sort, sorted

🔹 핵심 요약

🔹 예시 1 — 차이 확인

🔹 예시 2 — 반환값 차이

🔹 예시 3 — key와 reverse 공통 옵션

✅ 기억법

💡 한 줄 정리

6. 점수계산

✅ 배운점 정리

🧩 요약 문장

7. 완전제곱수

8. 생일

9. 최소공배수와 최대공약수

10.지능형기차

[복습] 백준_파이썬배우기(1~50)

[복습] 알고리즘 기초 1/2 200-자료구조1

0개의 댓글

④ 출력 형식 맞추기 (`{:02d}`)

(1) `itertools` vs `collections`

(2) `sys.stdin.readline` 사용 이유

(1) `is_prime()` 작성 시 핵심 고려사항