특정 구간의 합을 여러 번 구해야 하는 문제를 풀 때, 단순하게 for문을 사용해서 매번 합을 구하면 시간 초과가 발생할 수 있다. 이런 경우에는 누적합(Prefix Sum)을 활용해서 빠르게 구간합을 구하는 방법을 사용한다. 누적합누적합은 배열의 각 위치까지의 합을 미리 구해놓은 배열이다.누적합 배열을 사용하면 어떤 구간의 합도 O(1)의 시간복잡도를 가진다. 예를 들어 배열이 [5, 4, 3, 2, 1]일 때, 누적합 배열을 만들면 다음과 같다.(* 편한 계산을 위해 인덱스 0번은 비워두고 배열의 크기는 N+1로 한다.) 인덱스12345원본 배열54321누적합 배열59121415  구간합누적합 배열을 이용하면 i번째 수부터 j번째 수까지의 합은 다음 공식으로 구할 수 있다.구간합(i, j) = S[j..

Dynamic Programming(동적 계획법)DP(동적 계획법)는 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용해 효율적으로 값을 구하는 알고리즘 설계 기법이다. 즉, 큰 문제를 작은 문제로 나누어 푸는 알고리즘을 의미한다. DP 구현 방식은 4가지가 있다.메모이제이션(memoization) 방법: 모든 작은 문제들을 한 번만 계산해서 DP에 저장하며, 저장한 값을 재사용 하는 방법타뷸레이션(Tabulation) 방법: 작은 문제부터 순차적으로 계산하며 상위로 올라가는 방법탑 다운: 큰 문제에서 작은 하위 문제들을 확인해가며 진행하는 방법바텀 업: = 타뷸레이션 동적 계획법은 분할 정복과 비슷해보이지만 차이점이 있다.분할 정복의 경우 분할된 하위 문제가 동일하게 중복이 일어나지 ..

MVC 패턴 - 개요서블릿과 JSP의 한계서블릿으로 개발할 때는 뷰(View) 화면을 위한 HTML을 만드는 작업이 자바 코드에 섞여 지저분하고 복잡해진다. JSP를 사용하면 뷰를 생성하는 HTML 작업을 깔끔하게 가져가고, 동적으로 변경이 필요한 부분에만 자바코드를 적용할 수 있다. 하지만 JSP 코드 상위 부분의 절반은 비즈니스 로직이고, 나머지 하위 절반은 결과를 HTML로 보여주기 위한 뷰 영역이 된다. JSP에는 Java 코드, Repository 등 다양한 코드가 모두 노출되며 너무 많은 역할을 가져가게 된다.  하나의 서블릿이나 JSP로 비즈니스 로직과 뷰 렌더링을 모두 처리하게 되면 유지보수가 어려워진다. 제일 큰 문제점은 둘 사이에 변경의 라이프 사이클이 다르다는 점이다. 예를 들면 UI..

이 문제는 주어진 N개의 수를 오름차순으로 정렬해야 한다. 수의 개수(N)가 최대 10,000,000이지만, 주어진 값이 10,000 이하의 자연수로 한정적이라는 점에서 카운팅 정렬(Counting Sort)을 사용할 수 있다. 카운팅 정렬은 정수 데이터의 범위가 제한되어 있을 때 매우 효율적인 알고리즘이다.카운팅 정렬의 시간 복잡도는 O(N+K)이며 K는 값의 범위이다. 따라서 입력 크기가 크더라도 효율적으로 정리할 수 있다.  N = 10입력: 5, 2, 3, 1, 4, 2 ,3 ,5, 1, 7 카운트 배열 생성데이터의 범위가 1~10,000이므로 크기가 10,0001인 카운트 배열을 생성한다. 입력된 값의 등장 횟수를 카운트 배열에 저장한다. 카운팅 정렬에서는 값의 크기를 인덱스로 사용한다. 예를 ..

정렬된 배열에서 특정 값의 등장 횟수를 효율적으로 구하는 방법으로 이진탐색을 활용할 수 있다. 이진탐색은 정렬된 배열에서 원하는 값을 찾기 위해 검색 범위를 절반으로 줄여나가는 알고리즘이다. 배열에서 중간값을 선택하고, 검색 대상 값이 중간값보다 크거나 작은지에 따라 검색 범위를 좁혀나갈 수 있다. 반복적으로 범위를 줄이다보면 값을 찾거나 값이 존재하지 않음을 확인할 수 있다. 이진탐색의 시간복잡도는 O(logN)으로 매우 빠르다.  이진탐색은 정렬이 된 배열에서 사용해야 하므로 주어진 배열을 우선 정렬해야 한다.[6, 3, 2, 10, 10, -10, -10, 7, 3] -> [-10, -10, 2, 3, 3, 6, 10, 10, 10]찾고자 하는 값(target = 10)일 경우 10은 주어진 배열에..

알고리즘을 시작할 때 가장 먼저 접하게 되는 주제는 정렬(Sorting)이다.여러가지 정렬 알고리즘이 있지만 병합정렬은 시간 복잡도가 항상 O(nlogn)으로 안정적이고 효율적이며 성능도 좋다.병합정렬은 재귀적으로 배열을 계속 반으로 나누기 때문에 분할하는 단계는 배열의 크기 n에 대해 log₂n번 실행된다. 참고: 백준 문제를 사용해서 글을 작성했으나 병합정렬로 수 정렬하기2를 풀면 시간초과가 나오므로 해당 문제는 언어에 내장된 함수를 써야함. 수 정렬하기 2 답은 더보기 클릭.더보기import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.OutputStreamWrit..