1. 10830번 - 행렬제곱
- 행렬 곱셈
def solution(A, B):
answer = [[0 for _ in range(len(B[0]))] for _ in range(len(A))]
for i in range(len(A)):
for j in range(len(B[0])):
for k in range(len(A[0])):
answer[i][j] += (A[i][k] * B[k][j])
return answer- 재귀
재귀 필요한 곳마다 재귀함수 호출하지 말고, 같은 값 반복적으로 사용하는 경우엔 변수에 저장해서 사용해야 시간초과 안남!
- 다중조건 정렬
sorted(), .sort() 사용할 때, 조건을 여러개 걸고 싶을 때!
예를 들어,
(5, 40), (35, 25), (10, 20),(10, 25),(30, 50),(50, 60),(30, 25),(80, 100) 를 두번째 원소 기준 오름차순 정렬하고, 두번째 원소가 서로 같다면 그들의 첫번째 원소 기준 오름차순으로 정렬하는 문제가 있다.
list = [(5, 40), (35, 25), (10, 20),(10, 25),(30, 50),(50, 60),(30, 25),(80, 100)]
list.sort(key = lambda x : (x[1], x[0])) 위와 같이, 비교할 아이템의 요소가 복수 개일 경우, 튜플로 그 순서를 내보내주면 된다.
내림차순 정렬은 x[1], x[0] 중 내림차순 정렬 원하는 쪽에 마이너스 붙여주면 된다.
sorted() 도 똑같은 방법으로 한다.
2. 13334번 - 철로
- 라인 스위핑
정렬된 어떤 자료에서 시간 복잡도를 줄일 수 있도록 선을 한 번만 훑으면서 최종 결과를 찾는 방식, 우선순위 큐를 주로 사용
라인스위핑 문제 - 선 긋기
3. 파이썬 시간
알고리즘 문제를 풀 때, 항상 시간 제한과 메모리 제한을 체크해야한다.
시간 제한은 해당 문제를 푸는 알고리즘을 선택할 때 매우 중요하다.
import time
start_time = time.time()
sum = 0
for i in range(10000000):
sum += i
print(sum)
end_time = time.time()
print(end_time - start_time)위와 같이, 파이썬 time 모듈로 시간을 측정해본 결과, 파이썬은 천만번의 연산을 하는데에 약 1초가 걸린다. 그러니까 만약, 입력받는 변수 범위가 천만이라면 O(N)보다 복잡한 알고리즘을 짜면 시간 초과가 발생한다는 뜻이다.
정확한 것은 아니지만 대략적으로 O(N^2), O(N), O(logN) 등의 알고리즘 중 어떤 알고리즘을 사용할지 결정하는 데에는 도움이 된다.
