다나리

동적 계획법 (Dynamic Programming) 한 번 계산한 문제는 다시 계산하지 않게 하는 방식으로, 같은 계산을 여러 번 하는 상황을 개선하여 효율을 높이는 알고리즘이다. 이 때, 한 번 계산한 문제의 답을 저장해두는 메모이제이션(Memoization) 기법이 사용된다. Top-Down 방식은 재귀, Bottom-Up방식은 반복문을 사용한다. 동적 계획법 사용 조건 동일한 작은 문제들이 반복하여 나타나야 한다. 동일한 문제는 항상 답이 동일해야 한다. 동적계획법을 이용하는 백준 문제 (피보나치 함수) 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net import java.io.BufferedRead..

합병 정렬 (Merge Sort) 분할 정복 알고리즘 (Divide & Conquer) 이다. 주어진 배열을 원소 하나하나로 쪼갠다. 쪼갠 원소들을 정렬하면서 다시 합친다. 퀵 정렬 (Quick Sort) 분할 정복 알고리즘 (Divide & Conquer) 이다. 임의의 원소로 pivot을 정한다. pivot을 기준으로 pivot보다 작은 수끼리, pivot보다 큰 수끼리 새로운 배열을 만든다. 새로운 배열에서 다시 pivot을 정하고 같은 과정을 반복한다. 힙 정렬 (Heap Sort) 힙 자료구조를 사용한다. 오름차순으로 정렬할 땐 최소 힙 트리, 내림차순으로 정렬할 땐 최대 힙 트리를 사용한다. 오름차순으로 정렬하는 경우, 완전 이진 트리 형태의 최소 힙을 만든다. 삭제연산을 수행한다 -> 최댓값..

버블 정렬 (Bubble Sort) 인접한 두 요소를 비교하여 왼쪽 요소가 오른쪽 요소보다 크면 서로 바꾼다. 배열의 끝까지 비교하면 마지막 요소는 그 위치가 최종적으로 정렬된 요소이다. 다시 처음으로 돌아와서 두 요소끼리 비교하며 자리를 바꾼다. 배열의 크기가 N이라면, (N-1) + (N-2) + ... + 1 = N * (N-1) / 2번 비교를 수행한다. 시간복잡도: O(N^2) 자바 코드 import java.util.Scanner; public class BubbleSort { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int n = scn.nextInt(); int[] arr = new int[..

탐색 알고리즘 원하는 값을 검색하기 위한 알고리즘이다. 선형 탐색 알고리즘 (Linear Search Algorithm) 탐색 알고리즘 중 가장 간단한 알고리즘이다. 처음부터 원하는 값이 나올 때까지 하나하나 살펴보는 방법이다. 최악의 경우는 원하는 값이 가장 마지막에 있을 경우이며 O(n) 의 시간복잡도를 갖는다. ... 이진 탐색 알고리즘 (Binary Search Algorithm) 배열의 중앙에 있는 값을 목표한 값과 비교하여 중앙값의 왼쪽 구간 또는 오른쪽 구간을 검색 범위로 정한다. 정렬된 리스트에서 사용한다. 최악의 경우 시간복잡도는 O(logN)이다. 해시 탐색 알고리즘 (Hash Search Algorithm) 해시함수를 이용하여 계산된 해시값을 인덱스로 사용하는 방법이다. 데이터와 in..