Algorithm
문제 이해 포도주가 1~N개 있을 때, 3개의 포도주를 연속해서 마시지 않는 가운데 가장 많이 마실 수 있는 포도주의 양을 구하는 것. 문제 풀이 n번째의 잔을 마시는 경우의 수와 ( ~~~ + n / ~~~ + n-2 + n) n번째의 잔을 마시지 않을 때의 경우의 수를 계산해서 ( ~~~~ + n-2 + n-1 ) 그 중에서 가장 큰 값을 찾는 식. 주의사항 Top-down 식으로 풀 때, recur 메소드의 if 구문식을 세울 때에는 dp[0]의 값도 0으로 제시해주어야 한다. 그렇기 않을 경우 dp[0] = 에도 arrays.fill 메소드로 인해 -1이 채워져있기 때문에 dp[2], dp[1]을 계산하는 recur(2), recur(1)을 건너뛴 채 dp[0]을 계산하는 recur 함수가 돌아서..
문제 이해 N 이라는 자릿수가 주어졌을 때, 가장 앞자리 수부터 ~ N 까지의 수가 오름차순으로 이루어져 있어야 한다. 문제 풀이 N 이 2 이상일 때, k = 9의 경우는 항상 1. 99, 999, 999... N 이 2 이상일 때, k < 8 의 값은 dp[N-1][k] + dp[N-1][K+1, K+2.... 8]; 주의사항 첫 시작 수는 0부터 시작한다. 0으로 시작하는 수의 n=2 값의 경우 00, 01, 02, 03, 04... 는 n=1 값의 1, 2, 3, 4.. 와는 다르다. 끝자리가 9가 되면 더이상의 오름차순은 불가능해진다. 111, 222, 333, 22223 과 같은 중복수가 가능해진다. 결과 bottom-up top-down
4개의 메뉴를 담은 ArrayList 를 가격을 기준으로 정렬을 했다. 그런데 아메리카노와 카페모카의 가격이 같다. 그 경우 어떻게 정렬이 이루어질까? 어떤 정렬 알고리즘을 사용하느냐에 따라 결과값이 달라지게 된다. 안정 정렬(Stable sort) 안정 정렬은 1차적인 정렬이 이루어진 상태에서, 중복된 값이 있을 경우, 입력순서와 동일하게 정렬이 이루어지는 정렬 알고리즘의 특성 중 하나이다. 이러한 안정 정렬의 특성을 지닌 정렬 알고리즘에는 버블 정렬, 삽입정렬, 병합 정렬이 있다. 불안정 정렬(Unstable sort) 불안정 정렬은 안정 정렬의 반댓말로, 중복된 값이 입력 순서와 동일하지 않게 정렬되는 알고리즘을 의미한다. 선택 정렬, 퀵 정렬, 계수 정렬 등이 이에 해당한다.
func 이라는 메소드 안에 func 이라는 동일한 메소드를 입력할 수 있다. 하지만 특정 조치를 취하지 않을 경우, 이 케이스는 무한 루프에 빠져 에러가 발생할 것이다. public class Recursion { public static void main(String[] args) { int k = 4; func(k); } public static void func(int k) { if (k "hello..." => func(k-1=3) = 3 != 0 => "hello..." ==> func( (k-1)-1 = 2) = 2 != 0 => "hello..." ===> func( ((k-1)-1)-1 = 1) = 1 != 0 => "hello..." ====> func( (((k-1)-1)-1)-1 =..
시간 복잡도(time comlpexity) 실행 시간은 실행 환경에 따라 달라진다(하드웨어 / 운영체제 / 언어 / 컴파일러 등) 따라서 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트한다. 점근적 분석 점근적 표기법이란, 데이터의 개수 n->무한대 일 때, 수행시간이 증가하는 growth rate 로 시간 복잡도를 표현하는 기법이다. 이러한 점근적 분석의 표기법에는 총 3가지가 있다. 1) 빅오 O- 표기법 : upper bound를 표기하는 표기법(대부분 이 방법을 사용한다.) 2) : Ω-표기법 : lower bound를 표현 3) Θ-표기법 : upper bound와 lower bound 를 동시에 표현
1. 선형검색 (Linear Search) 가장 기초적인 검색방법이라 볼 수 있다. 배열의 index 상자들을 0부터 하나하나 열어보면서 내가 찾고자 하는 '7' 이라는 데이터가 있는지를 확인하는 것이다. 이 경우 최악의 시나리오는 배열의 가장 마지막에 '7'의 데이터가 있거나 혹은 이 배열 안엔 '7' 이라는 데이터가 없을 때. 이처럼 배열, 그리고 input 사이즈의 크기가 N이라고 했을 때 선형검색은 N번 만큼의 과정, 스텝이 필요로 해지게 된다. 이를 BigO 라는 표현으로 쓸 때 선형검색의 시간복잡도 = O(N) 이라고 표현한다. 2. 이진검색 (Binary Search) 이진검색의 기본 조건은 정렬(Sorting)이다. 정렬되어있지 않은 데이터구조, 배열에는 이진검색을 사용할 수 없다. 따라서..
