Grusie 안드로이드 개발 기술 블로그

이번에 알아 볼 알고리즘은 구현이다. 구현 알고리즘이란? - 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 알고리즘 문제를 풀이할 때 구현은 매우 필요하다. 모든 문제를 구현이라고 생각 할 수 있으나, 그 중 구현이 어렵거나 구현에 초점을 맞추는 문제들이 있다. 즉, 풀이를 떠올리기는 쉽지만 소스코드로 옮기기 어려운 문제라고 생각하면 된다. 예시 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 알고리즘은 간단한데, 코드가 길어지는 문제 시뮬레이션 문제 완전 탐색 완전탐색 - 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 - 문제에서 제시한 알고리즘을 한 단계씩 차례대로..

알고리즘 첫 번째, 누적합의 이론을 공부하고 예제들을 풀어보려고 한다. 누적 합 : 일정 구간의 누적 합을 구하는 문제이다. 일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우 O(n^2)의 시간 복잡도를 갖기 때문에 입력의 범위가 클 때 사용할 수 없다. 하지만 Prefix sum 방식을 사용하면 O(N)으로 해결 할 수 있다. 누적합은 문제에서 수열이 주어지고 어떤 구간의 값의 합을 구해야 할 때 쓰일 수 있다. 예를 들어, 크기가 5인 arr배열에서 3번 index와 5번 index 구간의 구간합을 구한다고 가정하면, 누적합은 arr[0~b]까지의 누적합 - arr[0~a-1까지의 누적합]으로 표현 할 수 있다. b - a 구간의 누적합을 구하기 위해선 b..