1. 문제 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 2. 풀이 해당 문제를 요약하자면 주어진 수열에서 연속된 부분수열의 합이 C를 만족하는 경우의 수를 찾으라는 내용이다. 가장 단편적인 방법으로는 brute-force로 해당 문제를 해결해도 될 것으로 보인다. 하지만 연속된 부분수열의 합을 매번 구해야 한다면 O(N²)의 시간복잡도가 발생할 것이다. 그렇다면 부분 수열의 합을 어떻게 하면 효율적으로 계산할 수 있을까를 먼저 해결해보자. 1.1 누적합 연속된 부분..

다양한 알고리즘 문제들을 풀이하는 방법들이 있는데 그 중 첫 번째는 역시 브루트 포스(Brute Force) 가 아닐까 싶다. 해킹 기법 중 가장 기본적인 공격 방식 중에 '무차별 대입 공격(brute-force attack)'이라는 것이 있는데, 이는 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 방식을 의미한다! 쉽게 생각하자면 아래 자전거 자물쇠를 살펴보면 된다. 이 자전거 자물쇠를 푸는 가장 쉬운 방법은 '0000' 부터 '9999'까지 하나씩 돌려보면 될 것이다. 브루트 포스(brute force) 알고리즘 역시 마찬가지다. 다른 말로 '무식하게 풀기'라고도 하는데, 특정한 문제에 발생 가능한 경우의 수를 일일이 나열하면서 답을 찾는 것이다. 최단 거리를 찾기 위해 노드 간의 경로들을 일일..