개발이글스

구간 합 구간 합은 합 배열을 이용해서 시간복잡도를 더 줄이기 위해 사용하는 특수 목적의 알고리즘이다. (코테에서 사용빈도가 높다..) 1.구간 합의 핵심이론 : 구간 합 알고리즘을 활용하려면 합 배열을 구해야한다. 2. 합 배열 S 정의 S[i] = A[0] + A[1] + A[2] + A[3] + ... + A[i-1] + A[i] //A[0] 부터 A[i] 까지의 합 합 배열은 기존의 배열을 전처리한 배열이라고 생각하면 된다. 이렇게 합배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) 에서 O(1) 로 감소한다. (우리는 시간복잡도를 항상 고려해야하기 때문에 시간복잡도가 감소하는쪽으로 계속 생각해야한다!! 명심하자.) 3. 합 배열 S를 만드는 공식 S[i] = S..

1. BackTracking 이란? BackTracking은 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한조건에 위배되는지(유망하지 않은지) 판단하고, 그러한 경우 해당 노드를 제외하고 다음단계로 나아가는 방식이다. 여기서 중요한점은 특정상태(노드)를 제외한다는 것이다. BackTracking은 현재 노드에서 다음 노드로 나아갈 수 있는 모든 경우를 찾되, 그중 유망하지 않다면 현재에서 더이상 나아가지 않고 이전의 노드로 돌아가 다음노드를 검사한다. 여기서 더이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기라고도 한다. 즉, 이 방법을 통해 우리는 모든 경우의 수를 체크하지 않고 필요한 것만 체크하여 전체 풀이 시간을 단축 할 수 있게..