용's

가장 먼저 Pivot을 배열에서 하나 선택해서 Pivot을 기준으로 왼쪽에는 Pivot보다 작은 수가, 오른쪽에는 Pivot보다 큰 수가 정렬되도록 한다. 이를 위해 배열의 인덱스 0을 가르키는 Low(또는 Left)를 시작으로 인덱스를 하나씩 증가시키며 Pivot보다 큰 수를 찾는다. Left가 찾고 난 뒤, Right가 배열의 끝에서 점점 감소하며 Pivot보다 작은 수를 찾는다. 그러면 현재 Left는 Pivot보다 큰 수, Right는 Pivot보다 작은 수를 가르키고 있으므로 이 둘을 Swap한다. (위의 그림에서는 두 수를 모두 찾고 나서 swap하는 것이 아닌, 빈칸(Vac)이 생기는 곳에 곧바로 찾은 수를 넣고 있다. 예를 들면, Pivot으로 선택된 45가 있던 자리에 Vac이 생기고, ..

이전 포스팅에서는 Change Making 문제를 다뤘다. 이번 동적 프로그래밍 문제에서는 '주어진 동전의 종류를 이용하여 목표치(W)를 만드는 경우의 수 카운트' 문제를 풀어보도록 한다. 알고리즘을 단번에 생각해내기가 상당히 어렵다. 차근차근 이 문제를 접근해보자 예를 들어 설명하는 것이 가장 빠를 듯 하다. 1원 2원을 이용하여 4원(W)을 만드는 경우의 수는 몇 가지인가? 1+1+1+1 = 4 2+1+1 = 4 2+2 = 4 이렇게 총 3가지가 된다. 1원 2원을 이용하여 5원(W)을 만드는 경우의 수는 몇 가지인가? 1+1+1+1+1 = 5 2+1+1+1 = 5 2+2+1 = 5 이렇게 총 3가지가 된다. 자세히 보면, 1원으로 W를 만드는 경우의 수 + 2원을 이용하여 W를 만드는 경우의 수로 ..

change making problem [https://en.wikipedia.org/wiki/Change-making_problem] 위키피디아에서 알 수 있듯이 이 문제는, '주어진 동전의 종류를 조합하여 목표 금액을 만들고자 할 때, 최소의 동전 개수를 구하는 문제' 예를 들면, 다음 문제와 같다. '1원 5원 10원을 가지고 15원을 만들고자 할 때, 15원을 만드는 조합 중 최소의 동전 개수는?' Greedy한 방식으로도 풀 수 있지만 이 문제는 가장 기초적인 동적 프로그래밍(Dynamic Programming)로 해결할 수 있는 문제 중 하나이다. 아이디어는 다음과 같다. 1원이 포함된 n가지 동전으로 W원을 만들고자 할 때, W원을 만드는 최소의 동전 개수는 다음 두가지 경우의 수 중 최소값..

순열을 만드는 아이디어는 다음과 같다 N Permutation 1 a 2 ba ab 3 cba bca bac cab acb abc ... ... 표를 자세히 보면 N이 1에서 2가 될 때, a를 사이에 두고 b가 앞 뒤쪽으로 하나씩 생겨 2개의 순열이 생겨났다. N이 2에서 3이 될 때, O b O a O 의 O에 c가 하나씩 생겨 3개의 순열이, O a O b O 의 O에 c가 하나씩 생겨 3개의 순열이 생겨 총 6개의 순열이 생겼다. 여기서 ba, ab는 N=1 -> N=2로 될 때 만들어 진 것. 따라서 Recursive Call 방법으로 순열을 만들 수 있을 것이다. (N! 이면, '(N-1)!은 내가 만드니 N만 니가 처리해줘' 라는 방식) 코드를 짜봤지만, 그 다지 깔끔한 코드가 아닌 듯 하다..

BigDecimal 클래스- 오차가 존재하지 않는 실수의 표현을 위해 정의된 클래스 - 실제 double이나 float를 사칙연산 시, 근사치 계산으로 정확한 수치의 결과가 나오지 않음예) double a = 4.7double b = 0.4a+b = 5.1000000000000005와 같은 결과가 나옴 이때 a와 b를BigDecimal a = new BigDecimal("4.7")BigDecimal b = new BigDecimal("0.4")의 객체로 만들고 a.add(b)를 하면 결과가 5.1이라는 정확한 실수로 나오게 된다.

▶ 혼잡 회피 알고리즘(Congestion Avoidance Algorithm) → 혼잡(Congestion)이란, 대기(Waiting)/큐잉(Queuing)를 포함하는 어떠한 곳에서도 발생 가능한 것으로, 네트워크 내 대기하는 패킷 수가 네트워크 처리 용량을 초과하는 현상을 보통 말함. → 이를 회피하는 알고리즘으로는 RED, WRED, TCP Vagas, ECN 등이 있다. → RED- 버퍼(큐)가 오버플로우될 떄까지 기다리지 않고, 패킷들을 폐기(Drop)하는 방법- 즉, 패킷을 보낼 수 있지만 특정 Sender(랜덤한 Sender)의 패킷을 Drop시켜 버퍼의 오버플로우를 피함 → WRED- RED 알고리즘에서 Drop시키는 플로우(Flow)를 특정 기준/정책에 준하는 값에 따라 우선순위를 두고 ..

최소값(또는 최대값)을 찾아서 계속해서 앞쪽(또는 뒤쪽)으로 두는 정렬방식... 123456789101112131415161718192021222324 int main(){ int a[10] = { 5, 2, 3, 10, 1, 7, 9, 8, 6, 4 }; for (int i = 0; i

기본적인 아이디어는 인근의 두 수를 비교해서 정렬하는 것. 1234567891011121314151617181920int main(){ int a[10] = { 10, 2, 3, 5, 1, 7, 9, 8, 6, 4 }; for (int i = 0; i

1. 트랜잭션(Transaction)에 대해 설명하라 ▶ 데이터베이스의 상태를 변화시키는 논리적 연산의 집합. 즉, 여러 개의 작업이 발생할 때 하나의 단위로 묶어 '일괄 실행(Commit)', '일괄 취소(Rollback)'를 할 수 있게 해주는 것. 2. 트랜잭션(Transaction)의 ACID에 대해 설명하라 ▶ ACID는 각각 원자성(Atomicity), 일관성(Consistency), 독립성(Isolation), 지속성(Durability)을 의미한다.원자성: 모두 반영되거나 아니면 전혀 반영되지 않아야 함 (부분 실행 안됨)일관성: 트랜잭션이 그 실행을 성공적으로 완료하면 언제나 일관성 있게 DB상태로 변환. 시스템이 가지고 있는 고정요소는 트랜잭션 수행 전과 수행 완료 후에 같아야 함.독립..

SKT 국가재난안전통신망 공모전 참여해서 장려상 받았다!! 한 5일만에 후다닥 적어서 냈는데!! 꽤나 많은 상금을 받지만... 서울에 시상식 참여해야 하는 건 함정...