Web Programming/알고리즘

[알고리즘] 구간 합, 누적 합

코드보다는 알고리즘 접근 방법에 대해 정리합니다! 1. 누적 합이란? 배열에서 0번째 인덱스부터 N번째 인덱스까지 탐색을 진행하면서 누적해서 값을 더한 결과를 말합니다. array[1,3,5,6,7,9,13]가 있으면 1부터 13까지 순차적으로 탐색하면서 값을 더한 것을 말하는데, 다만 값을 단순하게 더하는 것이 아닌 누적해서 더한다는 것이 포인트입니다. 1+, (1+3), (1+3+5), (1+3+5+6), ... 이런식으로 더해 나가야하는 거죠! 코드로 단순하게 구현해 보면 아래와 같은 모습이 됩니다. for(int i = 0; i

[알고리즘] 투 포인트(Two Point)

코드보다는 알고리즘 접근 방법에 대해 정리합니다! keypoint. 리스트에 순차적으로 접근해야할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘 순차적, 일방향으로 되어있는 선형적인 구조에서 사용 1. 투 포인트란? 리스트에 순차적으로 접근해야할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘입니다. 구간을 설정하는 시작점과 끝점을 지정하는 방법이라고 생각하면 되는데, 순차적, 일방향으로 되어있는 선형적인 구조에서 사용할 수 있는 방법입니다! 예를 들어, 특정한 합을 가지는 부분 연속 수열을 찾는 문제가 있다고 합니다. 양의 정수로만 구성된 리스트[1,2,3,2,5]가 있을 때, 부분적으로 선택한 정수들의 합이 m(5)가 되는 수열의 개수를 출력해야 할때 위 투 포인트 알고리즘을 사용할 수 있습..

[알고리즘] 소수판별, 에라토스테네스의체

코드보다는 알고리즘 접근 방법에 대해 정리합니다! keypoint. 자연수는 가운데 약수를 기준으로 각 등식이 대칭적인 형태를 보인다 제곱근이란 어떤 수를 두번 곱하여나오는 수에 대해, 그 수가 나오도록 두번 곱하는 수 소수에 2를 곱할 경우 그 수는 소수가 아니게 된다 1. 소수란? 2보다 큰 자연수 중 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지않는 자연수를 말한다. 보통 1부터 N까지의 모든 소수를 출력해야 하는 문제가 나올 수가 있습니다. 2. 소수 판별 방법 1) X를 2부터 X-1까지의 모든 수로 나누어 보기 예를 들어, 16이라는 수가 있다면 16을 2로 나누고, 3으로 나누고, 4로 나누고, ... 15까지 나누어 보는 방법입니다. 이때 나머지가 0일 경우에는 소수가 아니게 되어서,..