썸네일 출처: The Binding of Isaac

복잡도

Big-O 표기법: 가장 빠르게 증가하는 항(가장 영향력이 큰 부분)만을 고려

시간 복잡도

• N개의 데이터 -> 모든 데이터를 하나씩 확인 -> $O(N)$
• N개의 데이터 -> 2중 반복문 -> $O(N^2)$

최악의 경우의 시간 복잡도를 우선적으로 고려해야 하는데, 일반적인 코테 환경에서는 $O(N^3)$이 넘어가면 사용하기 어렵다.

공간 복잡도

int 자료형 기준, 길이가 100만인 리스트(배열)가 사용하는 메모리가 4MB. 코테에서는 보통 128~512MB 정도로 제한하므로, 1000만 단위부터는 무언가 잘못되었을 것.

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법

기준에 따라 좋은 것을 선택하므로, 문제에서 '가장 큰 순서대로' 또는 '가장 작은 순서대로'와 같은 기준을 은연중에 제시해준다. 이러한 기준이 바탕이 되는 아이디어가 떠오른다면 그리디 알고리즘으로 접근을 시도해볼 것.

• 큰 값이나 작은 값부터 차례로 소거해 나가기(거스름돈)
• 선택지 중에 더 좋은 것만 우선적으로 선택해 나가기(1이 될 때까지)
• 그리디 같은데 그리디로 해결이 안 된다면, 다이나믹 프로그래밍이나 그래프 알고리즘 고려

큰 수의 법칙

• 다양한 수로 이루어진 배열에서 M번 더하여 가장 큰 수를 만드는 문제
• 단, 특정 인덱스의 값을 연속해서 K번 초과하여 더할 수는 없음

0. 가장 큰 값을 K번, 두 번째로 큰 값을 1번 더하는 과정을 반복
1. 가장 큰 값과 두 번째로 큰 값 찾기
2. M을 기준으로, 더해야 하는 횟수 찾기
3. 더하기

배열에서 두 가지 값만 사용하는게 그리디 포인트. 가장 큰 값을 순서대로 반복해서 더할 수도 있고, 처음부터 M을 기준으로 더해야 하는 횟수를 구해서 더할 수도 있다. 후자의 경우, 같은 패턴이 반복되는 특징을 파악.

숫자 카드 게임

• N $\times$ M 형태의 배열
• 각 행마다 가장 작은 값을 선택할 때, 최종적으로 가장 높은 숫자를 얻는 문제

1. 각 행마다 가장 작은 값을 찾고, 지금까지의 최대값과 비교
2. 더 큰 값으로 업데이트

가장 작은 값을 찾고 비교해서 최대값만 남기는게 그리디 포인트. 단순하게 한 줄씩 입력받아 최소값을 찾는 과정을 반복하면서, 기준값과 비교해서 최종 답안 탐색.

1이 될 때까지

• 주어진 수 N이 1이 될 때까지 (1) N에서 1을 빼거나, (2) N을 K로 나누기
• 그 과정에서 필요한 최소 횟수를 구하는 문제

0. 나누는게 무조건 더하는거보다 숫자가 크게 감소하기 때문에 가능하면 나누기
1. N이 K로 나누어 떨어질 수 있도록 만들고 나누기 -> 반복
2. N이 K보다 작아서 나눌 수 없게 되면 1이 될 때까지 빼기

나누기를 우선적으로 선택하는게 그리디 포인트. 단순하게 나누어 떨어지는지 비교하는걸 반복하면서 1을 뺄 수도 있지만, 원하는 수를 설정하고 그 차이만큼 한 번에 빼버려서 계산을 압축할 수 있다. N이 K보다 작아서 빼는 과정에서도 마찬가지. 1과 현재의 N의 차이만큼 한 번에 빼버리면 계산 횟수가 줄어든다.