알고리즘 이분 탐색 누적 합 풀이 석순은 아래에서부터 종유석은 위에서부터 자란다. 이를 각각 bottom 벡터과 top 벡터로 나타낸다. 번갈아가면서 석순과 종유석의 길이가 입력되므로 차례대로 입력받은 값을 bottom 벡터 또는 top 벡터에 인덱스로 하여 1씩 더해준다. 실제로 석순의 길이가 3이라면 bottom[1], bottom[2], bottom[3]에 모두 1씩 더해주어야 하는데 이것을 이중 for문으로 다음과 같이 구현하면 시간 초과가 발생하므로 다른 방법을 사용하여야 한다. 시간 초과 코드 #include #include #include using namespace std; int main() { // freopen("input.txt", "rt", stdin); ios_base::sync..
알고리즘 누적 합 1차원 배열의 구간 합 계산 누적합을 이용 5 4 3 2 1이라는 수가 주어지면 1차원 vector v v[1]=5 v [2]=4+v [1]=5+4=9 v [3]=3+v [2]=3+9=12 v [4]=2+v [3]=2+12=14 v [5]=1+v [4]=1+14=15 즉 v[i]는 1번째에서 i번째까지의 수를 더한 값을 나타낸다. v[1] v[2] v[3] v[4] v[5] 5 9 12 14 15 따라서 i번째 수부터 j번째 수까지의 합은 v[i]-v[j-1]을 계산한 값이 된다. v[i] 1~i번째 수의 합 v[j-1] 1~j-1번째 수의 합 틀린 코드: 시간 초과 5 4 3 2 1을 배열에 그대로 저장하여 i번째부터 j번째 수 까지의 합을 구하는 과정을 반복문을 i부터 j까지 돌려 ..