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

이 문제는 주어진 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..