[Section02] Python 알고리즘 문제풀이 01~05
Q1. K번째 약수 : N의 약수들 중 K번째로 작은 수 출력
입력 : N(1<=N<=10000) K(1<=K<=N)
출력 : K번째 수
[내가 쓴 코드]
n, k = map(int, input().split()) #n과 k를 입력받음
a = list() #약수를 담을 list 생성
#약수 구하기
for i in range(1, n) : #1 ~ n-1 반복
if n % i == 0 : #n의 약수 구하기
a.append(i) #약수라면 list에 추가
a.append(n) #마지막으로 n을 추가
#k번째 약수 출력하기
if k <= len(a) : #k번째 약수를 구할 수 있다면
print(a[k-1]) #k번째 약수 출력
else : #k가 약수의 개수보다 큰 수라면
print(-1) #-1 출력
[풀이 코드]
n, k = map(int, input().split())
cnt = 0 #카운트변수 생성
#약수를 구하면서 k번째 약수를 출력
for i in range(1, n+1) #1 ~ n 반복
if n % i == 0 : #약수라면
cnt += 1 #카운팅
if cnt == k : #k번째 약수 발견 시
print(i) #출력 후 break
break
else : #for-else문 k번째 약수를 찾지 못하고 반복 종료시 -1 출력
print(-1)약수를 구하면서 k번째 약수를 동시에 찾기 때문에 굳이 모든 약수를 구하지 않아도 됨
답을 출력할 때 for문을 사용하지 않고 for-else로 한번에 해결
for-else : for문이 break없이 정상 종료 되었을 경우 else 실행
Q2. K번째 수 : N개의 숫자로 이루어진 숫자열에서 s ~ e까지의 수를 오름차순 정렬했을 때 k번째 수
입력 :
T(test case)
N, s, e, k
N개의 숫자
출력 : #{T} k번째 수
[내가 쓴 코드]
t = int(input()) #test case 입력
for i in range(t) : #test case만큼 반복
n, s, e, k = map(int, input().split()) #n, s, e, k 입력받기
a = list(map(int, input().split())) #숫자열 리스트로 입력받기
result = a[s-1 : e] #result list에 s~e만큼 슬라이스
result.sort() #오름차순 정렬
print("#{0} {1}" .format(i+1, result[k-1])) #print
[풀이 코드]
T = int(input())
for t in range(T) :
n, s, e, k = map(int, input().split())
a = list(map(int, input().split()))
a = a[s-1:e] #새로운 list를 생성할 필요가 없음 기존 리스트에 자른 부분 저장
a.sort()
print("#%d %d" %(t + 1, a[k-1]))새로운 result list 생성 없이 그냥 원래 list 사용, print option 이외의 내용은 같음
Q3. K번째 큰 수 : N개의 숫자에서 3가지 더한 조합을 내림차순 정렬했을 때 K번째 수
입력 :
N(3<=N<=100) K(1<=K<=50)
N개의 숫자
출력 : K번째 수
[내가 쓴 코드]
n, k = map(int, input().split())
card = list(map(int, input().split()))
card.sort(reverse=True) #내림차순 정렬
result = list() #3가지 수를 더한 값을 저장할 list
for x in range(n) :
for y in range(x + 1, n) : #x+1~n
for z in range(y + 1, n) : #y+1~n
result.append(card[x] + card[y] + card[z]) #값 더하기
print(result[k - 1]) #k번째 수 출력
[풀이 코드]
n, k = map(int, input().split())
a = list(map(int, input().split()))
res = set() #중복 값을 허용하지 않는 자료형 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) #list로 변환
res.sort(reverse=True) #내람차순 정렬
print(res[k - 1]) #k번째 수 출력중복 값을 제거하지 않아서 내 풀이에는 오류 발생함
이외의 내용은 동일
set() : 중복 값을 허용하지 않는 자료형, sort 불가
+ 최소값 찾기
arr = [5, 3, 7, 9, 2, 5, 2, 6]
arrMin = float('inf') #python내 가장 큰 값 == 무한대
#arrMin = arr[0] #첫번째 요소를 min으로 지정하고
#for i in range(1, len(arr)) : #for문에서 두번째 요소부터 값을 비교하여도 됨
for i in range(len(arr)) :
if arr[i] < arrMin :
arrMin = arr[i]
print(arrMin)
#for x in arr : #리스트 요소 자체에 접근하여 비교해도 됨
# if x < arrMin :
# arrMin = x
#print(arrMin)
Q4. 대표값 : N개의 점수의 평균을 구하고 평균에 가장 가까운 점수의 학생 번호를 출력(단, 해당 학생이 여러명일 경우 높은 점수인 학생의 번호를 출력 이 또한 여러명일 경우 앞 번호를 출력)
입력 :
N(5<=N<=100)
N개의 숫자
출력 :
평균 학생번호
[내가 쓴 코드]
n = int(input())
a = list(map(int, input().split()))
mean = round(sum(a)/n) #평균 구하고 반올림
min = float('inf') #무한대 값
for i in range(n) : #n번 반복
if abs(a[i] - mean) < abs(min) : #점수-평균의 절대값이 min보다 작으면
min = a[i] - mean #min에 점수-평균으로 업데이트
index = i #index는 i
elif abs(a[i] - mean) == abs(min) : #점수-평균의 절대값이 min과 동일하면(ex, [-1]과 [1]
if a[i] - mean > min : #해당 점수가 높은 점수라면
min = a[i] - mean #min 업데이트
index = i #index 업데이트
print(mean, index + 1)
[풀이 코드]
n = int(input())
a = list(map(int, input().split()))
ave = sum(a)/n + 0.5 #round대신 +0.5후 int로 변환하는 형식으로 반올림
ave = int(ave)
min = 2147000000 #python내에서 가장 큰 값 지정
for index, x in enumerate(a) : #enumerate를 사용하여 index와 요소에 접근
tmp = abs(x - ave) #점수-평균의 절대값을 저장한 변수 생성
if tmp < min : #평균과 더 가까운 점수를 찾으면
min = tmp #min 업데이트
score = x #점수 저장
res = index + 1 #index 저장
elif tmp == min : #차이가 동일하고
if x > score : #점수가 더 크다면
score = x #점수와 index 업데이트
res = index + 1
print(ave, res)
나는 절대값 비교 후 그 차이가 양수인지 음수인지를 확인했다면 풀이는 점수를 저장해서 점수를 비교함
Python에서 round() : round_half_even(half 지점일 경우 짝수 쪽으로 감, ex) 4.5 => 4, 5.5 => 6
일반적으로는 round_half_up(5이상 업)방식을 사용
Q5. 정다면체 : 정N면체와 정M면체인 두개의 주사위를 던져서 나올 수 있는 눈의 합 중 가장 확률이 높은 수 출력(단, 여러개면 오름차순으로 출력)
입력 : N M (4, 6, 8, 12, 20 중 하나)
출력 : 가장 확률이 높은 수
[내가 쓴 코드]
n, m = map(int, input().split())
result_list = list() #1+1 ~ n+m을 담을 리스트
counts = dict() #같은 result가 몇번 나오는지 count 하기위한 dictionary 변수 생성
for x in range(1, n + 1) : #1~n
for y in range(1, m + 1) : #1~m
result_list.append(x + y) #x+y의 값을 result list에 넣음
for result in result_list : #result list의 요소를 하나씩 빼서
if result in counts : #counts dict에 key 값으로 있는지 확인
counts[result] = counts[result] + 1 #있으면 count + 1
else : #없으면
counts[result] = 1 #count = 1
#dictionary value(count)를 기준으로 내림차순 sort, key를 기준으로 하려면 lambda item : item[0]
sorted_dict = sorted(counts.items(), key = lambda item : item[1], reverse = True)
max = sorted_dict[0][1] #max에 가장 첫번째 값 == 많이 등장한 값을 저장
for i in range(len(sorted_dict)) : #dict 길이만큼 반복
if max == sorted_dict[i][1] : #같은 count 값을 가진 요소가 있는지 확인
print(sorted_dict[i][0], end=' ') #같으면 print
print()
[풀이 코드]
n, m = map(int, input().split())
cnt = [0] * (n + m + 3) #index 자체를 n+m의 값으로 사용하기 위해 n+m길이 만큼의 list 생성(+3은 왜 해?)
max = -2147000000 #python내에서 가장 작은 값을 max에 저장
for i in range(1, n + 1) : #1~n
for j in range(1, m + 1) : #1~m
cnt[i + j] += 1 #더한 값인 index의 요소를 +1
for i in range(n + m + 1) : #최대값인 n+m만큼 반복
if cnt[i] > max : #cnt[i]의 카운트 값이 max보다 크다면 max에 해당 카운트 값 저장
max = cnt[i]
for i in range(n + m + 1) : #최대값인 n+m만큼 반복(+1은 왜?)
if cnt[i] == max : #같은 count 값을 가진 요소가 존재한다면
print(i, end = ' ') #print
print()나는 더한 값이 몇번 나오는가에 대해 카운트를 하기 위해서 dictionary를 사용하였음
풀이에서는 index 자체를 key로 사용함
sort 와 sorted
list.sort() : list형의 함수, 원본의 값 수정, 반환 값 없음
sorted(list) : 내장함수, 정렬된 값을 반환
sorted_dict = sorted(counts.items(), key = lambda item : item[1], reverse = True)
counts.item()
→ dictionary counts의 모든 아이템을 가져옴(key, value)
key = lambda item : item[1]
→ key 매개변수를 사용하여 정렬의 기준을 설정함
→ item(key, valu)를 입력 받아서 item[1](value)를 반환함
→ 결론적으로 아이템의 두번째 요소(value)에 대한 기준으로 정렬
*강의 : 파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)