<aside> ✅ 금주의 키워드
정수론
배열
문자열
재귀함수
정렬
완전탐색
시간복잡도 </aside>
15596번 정수 N개의 합
이 문제는 말그대로 정수 N개의 합을 출력하는 것이다.
나는 처음 문제의 답을 아래와 같이 작성하였다.
def solve(a):
ans = 0
for i in a:
ans += i
return ans
다른 팀원들과 동작 시간을 비교하였는데 다른팀원들에 비해 3배정도 오래걸렸다.
그래서 코드를 비교해보니 나는 합을 직접 구했는데 팀원들은 sum() 내장 함수를 이용하였다.
내장 함수사용이 직접계산하는 것보다 빠른 경우가 많았다.
그리고 생각지도 못한 내장 함수들과 라이브러리가 많았다.
처음엔 수식으로 어떻게든 풀려고 붙잡았는데 이제는 내장 함수들에 쓸만한게 있는지 찾아보는것 같다.
9020번 골드바흐의 추측
처음 문제를 읽었을때는 주어진 수보다 작은 소수들을 찾고 주어진 수와 작은 소수의 차이도 소수인지 확인하여 둘다 소수인 경우 새로운 리스트에 정보를 입력한 후 출력하려 하였다.
testcase = int(input())
answer_list = []
test_list = []
##문제 입력받음
for i in range(testcase):
test_list.append(int(input()))
##소수인지 판별하는 함수
def check_prime_num(x):
for i in range(2,x):
if(x%i == 0):
return False
else:
continue
return True
##주어진 수보다 작은 수들에 대해 자기자신과 페어가 소수인지 확인하여 답안리스트에 추가
for test in test_list:
prime_nums_list = []
prime_small_nums_list=[]
for i in range(2,test):
if (check_prime_num(i) & check_prime_num(test-i)):
if(i <= (test - i)):
prime_nums_list.append(i)
else:
continue
answer_list.append(max(prime_nums_list))
## 답안 출력
for i in range(testcase):
print("{} {}".format(answer_list[i],(test_list[i]-answer_list[i])))
이 경우 시간초과가 발생했다. 이전까지 시간 초과나 메모리 초과를 본적이 없어서 당황했다.
동작속도가 더 빠르다는 pypy3로 제출해도 마찬가지였다.
그래서 시간을 줄일 방법을 고민하다 주어진 수이하의 정수를 모두 확인할 필요가 없다고 생각해서 반복 범위를 반으로 줄였다. 그리고 정답리스트를 만들지 않고 바로 출력하게끔 했다.
처음에는 입력이 끝나고 일괄적으로 출력해야 한다고 생각했는데 다시 생각해보니 입력과 동시에 출력해도 무관했다. 그 결과 시간이 줄어 정답이 되었다.
import sys
testcase = int(sys.stdin.readline())
test_list = []
for i in range(testcase):
test_list.append(int(sys.stdin.readline()))
def check_prime_num(x):
for i in range(2,x):
if(x%i == 0):
return False
return True
for test in test_list:
half_test = test//2 ## 중간까지만 확인
while half_test:
if (check_prime_num(half_test) & check_prime_num(test-half_test)):
print("{} {}".format(half_test, test-half_test)) ## 바로출력
break
else:
half_test -= 1
그런데 다른 팀원의 코드를 보니 소수 확인 함수에서 검색 범위가 달랐다.
나와 달리 x의 제곱근까지만 탐색하였다. 이유를 들어보니 나누는 값이 커지면 몫은 작아지므로 제곱근까지만 찾으면 된다는 것이었다. 구글링을 더 해보니 '에라토스테네스의 체'도 있었다.
반복범위에 따라 시간이 많이 차이난다는 것을 깨달았던 문제였다.
위 내용은 아래 블로그를 참고하였습니다.
10989번 수 정렬하기 3
처음 문제를 봤을 때는 단순한 문제라고 생각했다. 주어진 입력값의 횟수를 카운트 해서 횟수만큼 출력하면 되는거 아닌가? 라고 생각 했는데 시간초과 였다.
import sys
times = int(sys.stdin.readline())
arr = []
arr_info = []
for i in range(times):
num = int(sys.stdin.readline())
if(num not in arr):
arr.append(num)
num_info = [1,num]
arr_info.append(num_info)
else:
for j in range(len(arr_info)):
if(arr_info[j][1]==num):
arr_info[j][0] += 1
arr_info[j] = [arr_info[j][0],arr_info[j][1]]
arr_info.sort(key=lambda x :x[1])
for word in arr_info:
for i in range(word[0]):
print(word[1])
그래서 책을 찾아보니 heap 정렬이 빠르다 해서 코드를 긁어와 봤는데 역시 시간초과 였다.
다른 정렬법을 찾아보게 되었고 도수정렬에 대해 공부하여 코드로 구현해 보았다.
import sys
times = int(sys.stdin.readline())
given_array = []
counting_array = []
print_array=[]
for i in range(times):
num = int(sys.stdin.readline())
given_array.append(num)
counting_array = [0] * (max(given_array)+1)
print_array = [0] * len(given_array)
for i in given_array:
counting_array[i] += 1
for i in range(1,len(counting_array)):
counting_array[i] += counting_array[i-1]
for i in given_array:
print_array[counting_array[i]-1] = i
counting_array[i] -= 1
for i in range(times):
sys.stdout.write(str(print_array[i])+"\\n")
결과는 메모리 초과였다. 문제를 보면 주어지는 수의 개수는 최대 10,000,000개이다.
주어지는 수를 모두 리스트에 삽입하면 요소가 10,000,000개인 리스트가 생성되어 메모리가 부족하였다.
아무리 생각해도 답이 안나와서 답을 구글링하였는데 답안을 보니 매우 충격적이었다.
import sys
times = int(sys.stdin.readline())
counting_array = [0] * 10001
for i in range(times):
counting_array[int(sys.stdin.readline())] += 1
for i in range(10001):
if(counting_array[i] != 0):
for j in range(counting_array[i]):
print(i)
나는 도수 표를 직접 만들었는데 주어지는 수의 최대값(10000)이 정해져있어 만들 필요가 없었다. 만약 5가 입력되면 counting_array의 5번 인덱스의 값을 1증가하여 카운트 한다. 출력시에는 인덱스 값(5)을 value만큼 출력하는 것이다.
이 해답을 보면서 주어진 조건을 잘 파악하고 이를 바탕으로 자료의 크기를 정하면 더 효율적인 프로그래밍을 할 수 있을것이라 생각했다.
위 내용은 아래 블로그를 참고하였습니다.
1181번 단어정렬
문제는 간단했다. 문자열을 입력받고 중복된 문자열의 길이가 짧은것 부터 출력하되 길이가 같을 경우 알파벳 순으로 출력하기였다.
그래서 나는 주어진 문자열이 정답리스트에 있으면 continue, 없으면 추가했다. 정답리스트를 이용해 (길이,문자열)을 포함한 리스트를 만들어 key를 이용해 정렬했다.
times = int(input())
words_list = []
words_info_list = []
for i in range(times):
word = input()
if(word not in words_list): #문자열이 리스트에 없을때만 입력
words_list.append(word)
word_info = (len(word),word) #문자열 길이를 포함한 튜플들이 포함된 리스트
words_info_list.append(word_info)
else:
continue
words_info_list.sort(key=lambda x :(x[0],x[1])) #주어진 조건에 따라 정렬
for word in words_info_list:
print(word[1])
다른 팀원의 코드를 보니 set()라이브러리를 이용하였다. iterable 자료형들에 대해 중복된 값들을 하나로 바꿔주는 것이었다. 이 라이브러리를 이용하면 반복문을 따로 입력할 필요가 없었다. 이런 다양한 자료형과 라이브러리를 잘 사용하면 코드를 간결하게 짤 수 있겠다고 생각했다.
위 내용은 아래 페이지를 참고하였습니다.
1914번 하노이의 탑
구글에 재귀함수를 검색하면 팩토리얼 다음으로 많이 나오는 문제인것 같다.
처음에 다른 풀이들과 교재를 봐도 이해가 가지 않아서 유튜브 강의들을 보게되었다.
식으로만 볼때는 이해가 안되었는데 영상으로 움직이는 것을 보니 이해가 되었다.
함수를 설계하는 방식은 점화식과 매우 유사했다.
점화식에서 가장 중요한것은 바로 전의 함수와 현재 함수의 관계, 그리고 시작값이다.
시작값 및 종료조건이 제대로 설정되지 않으면 recursion Error가 발생했다.
다른 알고리즘에서 재귀함수는 매우 많이 쓰인다고 한다. 앞으로도 재귀함수와 관련된 문제들을 많이 풀어봐야 할것 같다.
10971번 외판원 순회 2
처음 이 문제를 보았을때 매우 막막해서 노트에 여러 경우를 따져가며 해결 방법을 생각했다.
N-Queen 문제를 풀며 활용했던 방문 개념을 활용하여 코드를 작성해봤다.
import sys
num_city = int(sys.stdin.readline())
cost_list = [list(map(int,sys.stdin.readline().split())) for i in range(num_city)]
chk = [False] * num_city
pos = [0]*(num_city)
cal_cost_list = [0] * 1000000001
def totalcost(a,b):
combination_cost_list = [b[a[i]][a[i+1]] for i in range(num_city-1)]
combination_cost_list += [b[a[-1]][a[0]]]
return sum(combination_cost_list)
def set(i,n):
for j in range(n):
if not chk[j] and cost_list[i][j] > 0:
pos[i] = j
if i == n-1:
cal_cost_list[totalcost(pos,cost_list)] = 1
else:
chk[j] = True
set(i+1,n)
chk[j] = False
set(0,num_city)
for i in range(1,1000000001):
if cal_cost_list[i] == 1:
print(i)
break
위 경우, cal_cost_list의 용량이 너무 커서 메모리 초과가 발생했다. 최대값을 빨리 찾기위한 나름의 방법이었다.(도수정렬 때 사용한 방법과 유사하다.)
set안에서 최소값을 계산하기 어려워 생각해 낸 방법인데 그러기엔 메모리가 부족했다.
함수에 넣지 않아도 끌어다 쓸수 있는 변수가 필요했고 검색결과, 전역변수라는 개념이 있었다.
import sys
from collections import deque
num_city = int(sys.stdin.readline())
cost_list = [list(map(int,sys.stdin.readline().split())) for i in range(num_city)]
chk = [False] * num_city
pos = [0]*(num_city)
#전역변수 선언
global ans
ans = 10000000000
def set(i,n):
global ans
for j in range(n):
if not chk[j] > 0:
pos[i] = j
if i == n-1:
q = deque()
for i in range(num_city-1):
if cost_list[pos[i]][pos[i+1]] != 0 and i < num_city -2:
q.append(cost_list[pos[i]][pos[i+1]])
elif cost_list[pos[i]][pos[i+1]] != 0 and i == num_city -2 and cost_list[pos[-1]][pos[0]] != 0:
q.append(cost_list[pos[i]][pos[i+1]])
q.append(cost_list[pos[-1]][pos[0]])
ans = min(ans,(sum(q))) ##최소값을 대입(출력할 값)
else:
break
else:
chk[j] = True
set(i+1,n)
chk[j] = False
set(0,num_city)
print(ans)
나는 순열을 이용하여 풀기위해 순열을 직접 코드로 구현했는데 itertools라는 라이브러리 안에 permutation 함수가 있었다.
위 라이브러리 안에는 combination등 유용한 함수들이 많았다. 직접 구현하는 것보다 시간복잡도가 적어 유용하다고 한다.
또한, 순열도 모두 할 필요없고 절반만 해도 된다고 한다.
예를 들면 0 → 1→ 2 → 3 → 0 과 3 → 0 → 1 → 2 → 3 에 소요되는 비용은 일치하는 것이다.
이 개념을 이용하면 반복의 횟수를 줄일 수 있다고 한다.
위 내용은 아래 문서를 참고하였습니다.
itertools - Functions creating iterators for efficient looping - Python 3.10.0 documentation
느낀점 및 더 보아야 할것