매우 간단한 문제긴 한데 놓쳤던 부분이 있어서 시간 소요가 꽤 있었다. 기억을 위해 기록한다!
조합 공식
조합 공식은 위 그림과 같다. 조합은 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 없음)
팩토리얼을 구현하는 방법이 여러가지가 있으나 재귀함수 구현에 좀 시간이 걸렸다. 부끄럽다... 일단 재귀함수 ... 후 ... return문이 있어야 함수를 빠져나간다... 재귀 억지로라도 계속 손에 익히자 ㅠㅠ! 재귀로 팩토리얼을 구해도 되고 반복문으로 해도 된다.
그러고 나서 나눗셈을 해줘야 하는데 파이썬에서 '/' 과 '//' 연산자 차이를 이제야 다시 알았다.
'/' : 나눗셈 결과를 float형으로 반환
'//' : 나눗셈 결과를 int형으로 반환
그래서 /로 연산해준뒤 형변환하면 틀렸다고 나온다. 뭐 뒤의 자리를 까고 그러다가 그랬겠지..? 어차피 저 결과는 무조건 정수가 나올 수 밖에 없으니까 int형으로 리턴하는 '//' 연산자를 쓰는게 맞겠다.
코드는 다음과 같다.
n, m = map(int, input().split())
def recur_f(n):
if n == 1:
return 1
else:
return n * recur_f(n - 1)
def factorial(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
print(factorial(n) // ((factorial(m) * factorial(n - m))))
사실 로직 자체는 그냥 N과 M 문제와 똑같다. 다만 여기에서 이제 수열이 오름차순 정렬이 되어서 출력이 되어야 한다는 조건만 하나 붙어 있을 뿐! 그래서 sorted() 함수를 사용해서 정렬해준 뒤 그 결과가 answer에 없으면 넣어주는 코드를 추가했다.
아 그리고 숫자로 이루어진 리스트의 경우 바로 join해주면 int형이라 에러가 난다. 각각의 요소를 str으로 바꿔주는 map함수 잊지말고 적용해주자~!
코드는 다음과 같다.
n, m = map(int, input().split())
result = []
answer = []
def back():
if len(result) == m:
tmp = sorted(result)
if tmp not in answer:
answer.append(tmp)
return
for i in range(1, n + 1):
if i not in result:
result.append(i)
back()
result.pop()
back()
for i in answer:
print(" ".join(map(str, i)))
소수 판별 알고리즘 중 에라토스테네스의 체 방식을 알고 있어야 시간 초과가 안 나는 문제다. 물론 나는 에라토스테네스의 체 방식을 매번 입력받을 때마다 하고 반복문도 많이 써서 시간초과만 우다다 받았다 ^^
시간초과를 막는 중요한 포인트가 2개였다...
에라토스테네스의 체를 범위 내의 모든 숫자에 한해서 1번만 돌리기
최대한 반복문 줄이기
밉다 미워 시간초과
최대 입력 가능한 숫자 범위가 1000000이니까 그 안을 일단 다 소수를 판별해버린다! 가능한 소수를 미리 다 계산한 뒤 또 범위 내에서 새로운 리스트를 만들지 말고, 반복문 안에서 True, False값을 체크해서 보기만 해야 시간 초과가 안 난다.
시간초과가 이렇게 머리를 아프게 하는지 간만에 느껴본 문제...^^ 같은 골드바흐 문제는 꽤 금방 시간초과를 잡아서 기가 살아있었는데 1시간 내내 계속 시간 줄이다 보니까 기가 쪼그라들었다... 그래도 풀긴 푼거니까... 어디서 시간초과가 나는지 잘 살펴보는 능력도 정말 중요하구나, 또 느낀다.
파이썬 코드는 다음과 같다.
erato = [True] * 1000001
erato[0], erato[1] = False, False
for i in range(2, 1001):
if erato[i]:
for j in range(i + i, 1000001, i):
erato[j] = False
while True:
n = int(input())
wrongFlag = True
if n == 0:
break
for i in range(3, n):
if erato[i] == True:
if erato[n - i] == True:
wrongFlag = False
print(n, "=", i, "+", n - i)
break
if wrongFlag:
print("Goldbach's conjecture is wrong.")
눈물의 코드... (쓸 필요도 없었고 시간초과만 유발했던 녀석들이다)
# n 미만의 수 중 홀수인 소수 리스트 리턴
def getPrimeNums(n):
return [i for i in range(n) if erato[i] == True and i % 2 != 0]
def getGoldB(target, nums):
middleIdx = -1
for i in range(len(nums)):
if nums[i] > int(target / 2):
break
middleIdx = i
for i in range(middleIdx + 1):
for j in range(len(nums) - 1, middleIdx, -1):
if nums[i] + nums[j] < target:
break
if nums[i] + nums[j] == target:
return [nums[i], nums[j]]
return False
나름 시간 좀 줄여보겠다고 다른 골드바흐 문제에서 시간초과 잡아줬던, 중간값 구해서 어찌저찌 해봤는데 역시나 시간초과였다. 그냥 T/F 값 판단해서 바로바로 계산하는게 제일 빠르구만
이번 기회에 파이썬에서 사용 가능한 최대공약수(gcd), 최소공배수(lcm) 구하는 방법을 다 정리해보았다.
가장 베이직한 방법
최대공약수 : 숫자 x,y 중 더 작은 숫자부터 1까지 -1 해가며 x%i == 0 and y%i == 0인 숫자 찾기
최소공배수 : 숫자 x,y 중 더 큰 숫자부터 (x*y)까지 +1 해가며 i%x == 0 and i%y == 0인 숫자 찾기
유클리드 호제법
x,y의 gcd는 y와 r의 gcd와 같다. ( x%y = r)
즉 계속해서 x의 자리에 y값을 대입하고, y에는 x%y 값인 r을 대입하면 x%y == 0 인 순간의 y값이 바로 gcd이다.
최소공배수는 x*y를 위에서 구한 gcd로 나눠주면 된다.
라이브러리 활용
이게 사실 제일 편하다..^^ 파이썬의 math 라이브러리는 인자를 심지어 여러개 받을 수 있는 최대공약수, 최소공배수를 구해주는 함수를 제공한다.
math 라이브러리를 import 해주고 math.gcd( 인자, 인자, ... ) math.lcm( 인자, 인자 ,... ) 해주면 된다.
코드는 다음과 같다.
n, m = map(int, input().split())
# 가장 베이직한 방법
def getGCD_basic(x, y):
for i in range(min(x, y), 0, -1):
if x % i == 0 and y % i == 0:
return i
def getLCM_basic(x, y):
for i in range(max(x, y), (x * y) + 1):
if i % x == 0 and i % y == 0:
return i
# 유클리드 호제법
def getGCD_euclid(x, y):
while y:
x, y = y, x % y
return x
def getLCM_euclid(x, y):
return (x * y) // getGCD_euclid(x, y)
# 파이썬 라이브러리 활용
import math
print(math.gcd(n, m))
print(math.lcm(n, m))
유클리드 호제법은 정말... 정말 오랜만에 다시 들여다봤다...^^ 수학을 열심히 했던 학생이었는데 이렇게까지 싸그리 까먹을 수 있다니 슬프다. 안 좋은 일이나 빨리 까먹지 이런 수학적 지식만 홀라당 다 까먹어 버렸다.
N과 M문제는 자다가도 풀 수 있어야 한다고 해서 순열로 풀었다가 눈물 좍좍 흘리면서 백트래킹을 뿌셨다.
백트래킹은 불필요한 경우를 탐색하지 않는다. 즉 특정 조건에서는 탐색을 그만하고 뒤로 되돌아가는(back) 성질을 가지고 있다. 따라서 DFS로 무작정 들이박으면 시간초과가 나는 상황에 유용하게 쓰이겠다.
숫자 1~N까지 중복 없는 M개의 요소를 가진 수열을 구하는 문제이다.
따라서 1) 수열의 길이가 M을 넘으면 안됨 2) 배열 내에 중복 X 두 가지 조건을 만족하는 숫자 뽑기를 진행하면 된다.
ex. N = 4, M = 3
첫번째 숫자로 1,2,3,4 중 가장 작은 숫자인 1을 선택한다. -> for 문으로 순차 증가
두번째 숫자로 2,3,4 중 가장 작은 숫자인 2를 선택한다. -> 선택 과정에서 배열 안에 존재하는지 체크하여 중복 제거
세번째 숫자로 3,4 중 가장 작은 숫자인 3을 선택한다.
수열의 길이가 M(3)이 되었으므로 다시 단계 3로 돌아간다. -> 재귀 탈출
세번째 숫자로 4를 고른다.
수열의 길이가 M(3)이 되었으므로 단계 2로 돌아간다.
두번째 숫자로 다음 작은 숫자인 3를 선택한다.
세번째 숫자로 2,3,4 중 2를 선택한다. -> 추후 여기에서 다시 숫자를 고를 때 3은 이미 배열안에 존재하므로 X
... 반복
즉 위의 과정을 코드로 구현하면 다음과 같다.
n, m = map(int, input().split())
result = []
def backTracking():
# 수열의 길이가 m이면 출력해주고 전단계로 돌아가기 (재귀 탈출)
if len(result) == m:
print(" ".join(map(str, result))) # "구분자".join(리스트)
return
# 1 ~ n 까지 체크
for i in range(1, n + 1):
# 중복 체크
if i not in result:
result.append(i)
backTracking()
# return 문으로 돌아온 경우 실행되는 부분
result.pop() # n=4, m=3일때 1,2,3이 들어온 경우 3을 없앰으로써 전단계로 돌아감
backTracking()
백트래킹 어렵다. 재귀라서 더 어렵게 느끼는 것 같기도 하고...! 익숙해질때까지 킵고잉이다 정말
출력 관련해서 문자열 다룰 때 자주 쓰이는 함수 join도 짚고 가보자.
"구분자".join(리스트) 형태로 사용하며 join 함수는 매개변수로 들어온 리스트에 있는 요소 하나 하나를 합쳐서 하나의 문자열로 바꿔 반환하는 함수이다. "구분자"를 값과 값 사이에 넣어서 하나의 문자열로 합쳐준다!
파이썬이 문자열 다룰 때 깡패인 언어인 만큼 join함수에도 익숙해지자. 자주 써야된다~!
수학 -> 자료구조 -> 재귀 -> DP -> 그래프(DFS/BFS) -> 최단경로 -> 이분탐색 -> 분할정복 -> 그리디 -> 완전탐색, 시뮬레이션, 구현(가능하면 이걸 많이 푸는 게 좋다. 구현력이 늘고 풀 수 있는 문제가 많아진다) -> 문자열 -> 투 포인터, 슬라이딩 윈도우 -> 백트래킹 1주씩
DP로 접근했는데 애초에 재귀를 보면서 분명 같은 경우를 살펴볼 일이 없어야 하는데... 같은 경우를 체크한다...ㅠㅠㅠ
실패한 소스코드
import copy
frodo = [0 for _ in range(11)]
answer = []
max_gap = 0
def cmpScore(frodo, apeach):
score_f = 0
score_ap = 0
for i in range(11):
if frodo[i] > apeach[i]:
score_f += 10-i
elif frodo[i] <= apeach[i] and apeach[i] != 0:
score_ap += 10-i
else:
continue
return score_f - score_ap
def isFrodoWinner(frodo, apeach):
score_f = 0
score_ap = 0
for i in range(11):
if frodo[i] > apeach[i]:
score_f += 10-i
elif frodo[i] <= apeach[i] and apeach[i] != 0:
score_ap += 10-i
# k점에 아무도 못 맞힌 경우
else:
continue
if score_f > score_ap:
return True
else:
return False
def shoot(score, n, info):
global max_gap
# 해당 점수 맞히는 경우
frodo[10-score] = info[10-score] + 1
if sum(frodo) == n:
# print(frodo, isFrodoWinner(frodo, info))
if isFrodoWinner(frodo, info):
if len(answer) == 0:
answer.append(copy.deepcopy(frodo))
max_gap = cmpScore(frodo, info)
else:
if max_gap < cmpScore(frodo, info):
answer.clear()
answer.append(copy.deepcopy(frodo))
max_gap = cmpScore(frodo, info)
elif max_gap == cmpScore(frodo, info):
answer.append(copy.deepcopy(frodo))
return
elif sum(frodo) > n:
frodo[10-score] = 0
if score - 1 < 0:
return
else:
shoot(score-1, n, info)
else:
if score - 1 < 0:
return
else:
shoot(score-1, n, info)
# 해당 점수 안맞히고 넘어가는 경우
frodo[10-score] = 0
if score - 1 < 0:
return
else:
shoot(score-1, n, info)
def solution(n, info):
shoot(10, n, info)
if len(answer) == 0:
answer.append([-1])
else:
answer.sort(key=lambda x:(-x[10], -x[9], -x[8], -x[7], -x[6], -x[5], -x[4], -x[3], -x[2], -x[1], -x[0]))
print(answer)
return answer[0]
올바른 접근
완전 탐색으로 접근
0점부터 10점까지 모든 점수를 획득할지 말지만 결정하면 되므로 모든 경우의 수는 2^11 로 충분히 살펴볼 수 있다. 2시간 넘게 DP로 끙끙 앓았더니 슬프다. 운동하고 와서 다른 사람 코드 좀 보고... 카카오 코테 보기 전날 한번 더 완탐 문제들 풀어볼 때 다시 봐야겠다. 아직 문제 유형을 파악하는데 서툴구만 흑
BFS 접근
1. 10점부터 0점까지 화살 쏨
현재 몇점인지 : score ( 0 -> 10점과녁)
현재 라이언 과녁 상황 : lion [0 for _ in range(11)]
2. 어피치를 이기려면
1) 어피치보다 +1발
2) 해당 점수 포기
* 주의할 점은 그냥 '=' 연산자 써서는 X. copy() 메소드로 깊은 복사 해주자.
( 2차원 이상의 배열을 깊은 복사 해주려면 copy 라이브러리의 deepcopy() 메소드 써야한다. 리스트의 copy() 메소드는 1차원까지만 깊은 복사 지원 )
3. 조건 체크
1) 화살을 n발보다 더 쏜 경우 ( sum(lion) > n ) : 패스
2) 0점까지 갔는데 다 못 쏜 경우 ( score == 10 ): 마지막 과녁에 다 쏘기
3) 다 쏜 경우 ( sum(lion) == n ) : 점수 계산. 최대 점수차 갱신해가면서 최대 점수차를 내는 경우만 따로 배열로 저장하기
4. shoot() 함수를 실행한뒤 최종 조건 체크
1) 리턴값이 빈 배열인 경우 : [-1] 리턴
2) 리턴값 배열의 길이가 1인 경우 : 해당 배열 리턴
3) 그 외의 경우 : 가장 낮은 점수를 많이 맞힌 경우 리턴.
* score을 통해 가장 높은 점수부터 쏘기 시작했으므로 배열의 가장 마지막 요소가 해당됨.
python 코드
from collections import deque
def shoot(n, info):
q = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])])
result = [] # 가능한 시나리오 모두 저장
max_gap = 0 # 최대 점수차
while q:
score, lion = q.popleft()
# 화살 다 쐈으니 점수 계산
if sum(lion) == n:
score_ap, score_l = 0, 0
for i in range(11):
if not (info[i] == 0 and lion[i] == 0):
if info[i] >= lion[i]:
score_ap += 10 - i
else:
score_l += 10 - i
if score_ap < score_l:
gap = score_l - score_ap
if max_gap > gap:
continue
if max_gap < gap:
max_gap = gap
result.clear()
result.append(lion)
# 화살을 n발보다 더 쏜 경우
elif sum(lion) > n:
continue
# 마지막 과녁까지 간 경우, 화살 마지막 과녁에 다 쏘기
elif score == 10:
tmp = lion.copy()
tmp[score] = n - sum(tmp)
q.append((-1, tmp))
# 슛슛슛
else:
# 어피치보다 1발 더
shoot_lion = lion.copy()
shoot_lion[score] = info[score] + 1
q.append((score + 1, shoot_lion))
# 해당 점수 포기, 패스
giveup_lion = lion.copy()
giveup_lion[score] = 0
q.append((score + 1, giveup_lion))
return result
def solution(n, info):
answer = []
all_cases = shoot(n, info)
if len(all_cases) == 0:
answer.append(-1)
elif len(all_cases) == 1:
answer = all_cases[0]
else:
answer = all_cases[-1]
return answer
