728x90
반응형
파이썬 알고리즘 문제풀이 입문 3장 정리
1. K번째 약수
자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 구하는 문제예요.
n,k = map(int, input().split())
cnt = 0
for i in range(1, n+1):
if n%i == 0: # 여기가 n%0이 아니라 n%i여야 해요!
cnt+=1
if cnt == k:
print(i)
break
else: # python은 for-else라는 구문이 있어요
print(-1)
🔍 중요 포인트:
- 파이썬의 for-else 구문을 잘 활용하면 깔끔하게 처리할 수 있어요.
2. K번째 수
N개의 숫자열에서 s번째부터 e번째까지를 오름차순 정렬한 후, k번째 수를 구하는 문제입니다.
T = int(input())
for t in range(T):
n, s, e, k = map(int, input().split())
a = list(map(int, input().split()))
b = a[s-1:e] # 인덱스는 번째보다 -1만큼 작아요
b.sort() # 오름차순 정렬
print(b[k-1])
💡 핵심:
- 인덱스는 0부터 시작하니까 "번째"와 1씩 차이가 나요.
- 슬라이싱할 때 [s-1:e]로 해야 정확해요!
3. K번째 큰 수
1~100 사이의 자연수가 적힌 카드 N장에서 서로 다른 카드 3장을 뽑아 합한 값들 중 K번째로 큰 수를 구하는 문제예요.
n, k = map(int, input().split())
a = list(map(int, input().split()))
res = set() # 중복을 제거해줘요
for i in range(n):
for j in range(i+1, n):
for m in range(j+1, n):
res.add(a[i] + a[j] + a[m]) # 여기도 수정 필요!
res = list(res)
res.sort(reverse=True) # Reverse가 아니라 reverse예요!
print(res[k-1])
🛠️ 수정사항:
- res.add(a[i], a[j], a[m]) → res.add(a[i] + a[j] + a[m])
- Reverse=True → reverse=True (대소문자 주의!)
4. 대표값
N명의 수학 점수에서 평균을 구하고, 평균에 가장 가까운 점수를 가진 학생을 찾는 문제예요.
n = int(input()) # 여기도 수정!
a = list(map(int, input().split()))
min_diff = 2147000000 # float('inf')를 써도 돼요
ave = round(sum(a)/n)
for idx, x in enumerate(a):
tmp = abs(x - ave)
if tmp < min_diff:
min_diff = tmp
score = x
res = idx + 1
elif tmp == min_diff:
if x > score:
score = x
res = idx + 1
print(ave, res)
⚠️ 주의사항:
- 입력받는 부분에서 n,k가 아니라 n만 받아야 해요!
- 조건이 복잡하니까 차근차근 따져보세요.
5. 정다면체
정 N면체, 정 M면체 주사위를 던져서 나오는 합 중 가장 확률이 높은 값을 구하는 문제예요.
n, m = map(int, input().split())
cnt = [0] * (n + m + 3) # 충분한 크기로 배열 생성
max_cnt = 0
for i in range(1, n+1):
for j in range(1, m+1): # 여기가 n이 아니라 m이어야 해요!
cnt[i+j] += 1
for i in range(n + m + 1):
if cnt[i] > max_cnt:
max_cnt = cnt[i]
for i in range(n + m + 1):
if cnt[i] == max_cnt:
print(i, end=' ')
🎲 핵심: 두 번째 반복문에서 range(1, n+1)이 아니라 range(1, m+1)이어야 해요!
6. 자릿수의 합
N개의 자연수 중에서 각 자릿수 합이 최대인 자연수를 구하는 문제입니다.
n = int(input()) # 수정 필요
a = list(map(int, input().split()))
def digit_sum(x):
sum_val = 0
while x > 0:
sum_val += x % 10
x = x // 10
return sum_val
max_sum = 0
for x in a:
tot = digit_sum(x)
if tot > max_sum:
max_sum = tot
res = x
print(res)
😎 더 쉬운 방법:
def digit_sum(x):
return sum(int(i) for i in str(x))
문자열로 변환해서 각 문자를 다시 정수로 바꾸는 방법이 더 직관적이에요!
7. 소수 (에라토스테네스 체)
1부터 N까지의 소수 개수를 구하는 문제예요.
n = int(input())
ch = [0] * (n + 1)
cnt = 0
for i in range(2, n + 1):
if ch[i] == 0:
cnt += 1
for j in range(i, n + 1, i):
ch[j] = 1
print(cnt)
🚀 에라토스테네스 체: 소수를 찾는 가장 효율적인 알고리즘 중 하나예요!
8. 뒤집은 소수
각 수를 뒤집어서 소수인지 판별하는 문제입니다.
n = int(input())
a = list(map(int, input().split()))
def reverse(x):
res = 0
while x > 0:
t = x % 10
res = res * 10 + t
x = x // 10
return res
def isPrime(x):
if x == 1:
return False
for i in range(2, x//2 + 1):
if x % i == 0:
return False
else:
return True
for x in a:
tmp = reverse(x)
if isPrime(tmp):
print(tmp, end=' ')
💫 포인트:
- 숫자 뒤집기와 소수 판별 함수를 따로 만들어서 모듈화했어요.
- 1은 소수가 아니라는 것도 잊지 마세요!
9. 주사위 게임
세 개의 주사위를 던져서 상금을 계산하는 문제예요.
n = int(input())
res = 0
for i in range(n):
tmp = input().split()
tmp.sort()
a, b, c = map(int, tmp)
if a == b and b == c:
money = 10000 + a * 1000
elif a == b or a == c:
money = 1000 + a * 100
elif b == c:
money = 1000 + b * 100
else:
money = c * 100
if money > res:
res = money
print(res)
🎯 팁: 미리 정렬해두면 조건 처리가 훨씬 간단해져요!
10. 점수 계산 (OX 문제)
연속으로 맞힌 문제에 대해 가산점을 주는 시스템의 총 점수를 계산하는 문제입니다.
n = int(input())
a = list(map(int, input().split()))
total = 0
cnt = 0
for x in a:
if x == 1:
cnt += 1
total += cnt
else:
cnt = 0
print(total)
🏆 핵심: 연속 카운트를 유지하면서 누적합을 계산하는 방식이에요!
728x90
반응형