알고리즘 문제 풀이에 접근하는 방법

문제 접근 방법에 대해서

 

알고리즘에서 10의 8승 (10^8)이란?

일반적으로 연산을 10^8번하면 1초 정도로 생각합니다.

이것만으로 코테문제의 알고리즘을 추론할 수 있습니다.

 

시간 복잡도의 중요성

1부터 n까지 더하는 알고리즘이 있다고 가정하겠습니다.

1 + 2 + 3 + ... + n = ?

코드로 구현 한다면 forloop를 돌며 1부터 n까지 더하면 됩니다.

def sum(n):
	answer = 0
	for i in range(n+1):
		answer += i
	return answer

하지만 n이 크다면 ?

1 + 2 + 3 + ... + 10^8 = ?

위 코드는 n이 클 경우에는 시간이 매우 오래걸리기 때문에 수학적 공식을 구해서 계산해야 합니다.

def sum(n):
	return n * (n + 1) / 2

💡 사용된 수학 공식은 자연수 거듭제곱의 합(시그마 공식)을 사용했습니다.
자연수 거듭제곱의 합을 구할 수 있는 공식이며 이미지를 참고 하세요

---

빅-오(Big-O)표기법

빅-오 표기법은 각 알고리즘이 입력 n에 따라 가장 많은 연산을 할 경우 어느정도의 시간이 걸리는지 추정하는 방식입니다. O(n) 의 표기법을 따르며 복잡도를 나타낼때 사용합니다.

시간 복잡도

시간 복잡도는 알고리즘의 루프의 개수로 구할 수 있습니다

def loopTwice:
	answer = 1
	for i in range(n+1):
		for j in range(n+1):
			answer += i * j
	return answer

위와 같은 2중 루프는 O(n^2) 입니다

---

입력 제한과 Big-O 표기법

코딩 테스트에는 입력 제한이 존재 합니다. 입력 제한을 보고 이 문제에서 원하는 빅-오 표기법(노테이션)을 추정할 수 있습니다

n의 케이스를 대상으로 예시를 표현해 보겠습니다.

n≤20 일 경우는 웬만한 구현이 통과됩니다.

O(n!), O(2^n) 등이 이에 해당하며

브루트 포스, 전탐색이 있습니다.(빡구현?)

💡 브루트 포스 알고리즘
최적화 없이 모든 경우의 수를 세는 기법

n≤100이면 적당한 삼중 루프가 통과됩니다.

O(n^3) 이 해당하며

플로이드-와샬 알고리즘이 있습니다.

💡 플로이드-와샬 알고리즘
그래프에서 모든 점들 간의 최단 거리를 구하는 알고리즘

n≤1000이면 적당한 이중 루프가 통과됩니다.

O(2^n) 이 해당하며

벨만 포드 알고리즘이 있습니다.

💡 벨만 포드 알고리즘
거리에 음수가 있는 그래프에서 한 점과 나머지 점들의 최단 거리를 구하는 알고리즘

n≤10000이면… 머리를 써야 합니다.

O(n), O(nlogn)이 해당하며

동적 프로그래밍, 이분 탐색, 다익스트라 알고리즘, 유니언 파인드, 세그먼트 트리, 투 포인터 등 이 있습니다.

💡 동적 프로그래밍
큰 문제를 작은 문제로 쪼개고, 작은 문제의 답을 메모하여 문제를 푸는 기법

💡 이분 탐색
탐색 범위를 절반씩 줄여 가며 해답을 찾는 기법

💡 다익스트라 알고리즘
거리가 모두 양수인 그래프에서 한 지점과 다른 모든 지점까지의 최단 거리를 찾는 알고리즘

💡 유니언 파인드
원소들을 서로 겹치지 않는 집합에 묶고 병합하는 알고리즘과 자료구조

💡 세그먼트 트리
구간별 합이나 곱을 효과적으로 저장하는 트리 자료구조

💡 투 포인터
1차원 배열에서 두 인덱스를 저장하여 O(n)으로 계산하는 기법

n≤10^8 보다 크거나 같다면 수학적 기믹이 필요하다.

O(logn)이 해당하며

유클리드의 호제법이 있습니다.

💡 유클리드의 호제법
두 자연수를 서로 나누어 최대공약수를 빠르게 구하는 기법

!! 결론 !!

위 처럼 문제를 풀기전에 입력제한을 먼저 보고 n이 최악의 경우 최대 몇 까지 증가하는지 이해하고 이에 맞는 알고리즘을 끼워 맞추어 생각해야 합니다. 즉, 문제가 요구하는 시간복잡도를 미리 계산할 수 있습니다.

 

 

이 글은 유투브 저세상개발자 님의 영상을 보고 작성한 글입니다. 원본 영상