[백준] 여러가지 문제풀이 방법 모음

★유클리드 호제법 : 최대공약수 구하기

증명하는 방법 한번만 검색해서 보고 바로 쓰면 된다.

a,b 가 있을 때 (a>b)

a 를 b 로 나눈 나머지와 b 와의 최대공약수는 a, b 의 최대공약수와 일치한다.

(a, b 의 최대공약수 = b, a%b 의 최대공약수) 이를 뒤에 것이 0이 아닐 때 까지 반복하면 된다.

(12, 4) -> (4, 0) -> 최대공약수 4

(12, 5) -> (5, 2) -> (2, 1) -> (1, 0) -> 최대공약수 1

 

★소수

1. 테스트케이스 마다 소수를 구할 수도 있지만 미리 배열에 소수를 구해놓을 수 있다.

2. 이때 각 숫자가 소수인지 판단하는 것이 아니라 "배수" 를 사용한다.

( arr[i] 가 소수라면 -> i 의 배수 arr 은 모두 소수 X )

 

★이분탐색

순차적 배열이 하나 있다. [10, 15, 22, 30, 66]

이 배열 안에 어떠한 수가 우리가 원하는 정답이다.

이를 찾기 위해서 0 부터 66 까지 쭉 찾으면 찾을 수 있긴 하다.

이때 left = 0, right = 66 으로 두고 이분탐색을 해주면 된다.

*이분탐색에서 결국 우리가 얻는 답은 left or right 이다.

 

★결정탐색

어떤 최적의 결과를 얻기 위해 임의로 값을 결정한다.

그 결정한 값으로 결과를 얻을 수 있는지 없는지 확인한 후 결정한 값을 바꾼다.

즉 이분탐색을 하는 것이 결정탐색을 포함한 것이라고 보면 될 것 같다.

 

★누적합

반복적으로 배열 arr[N] 을 한바퀴 돌아야 할 때

미리 arr[N] 배열의 누적합 배열을 구해놓는 것이다. sum[N]

N번 * 여러번 => N번 + 여러번 으로 시간복잡도를 줄일 수 있다.