devbelly

문제 https://www.acmicpc.net/problem/1231 알고리즘 knapsack 풀이 $D$일동안 갯수제한없는 knapsack을 하는 문제입니다. 그리디한 DP임을 눈치채야 풀 수 있습니다. A일에 사서 B일에 파는 것은 A+1일에 해당 주식을 팔지 말지 결정하고 팔았다면 무조건 재매수를 하는 것을 B일까지 반복하는 것과 동일합니다. 만일 10 15 20에 해당하는 주식이 있다면 10에 주식을 사서 3일째 되는 날 20에 팔아 10의 이득을 챙기는 것과 2일째에 15에 팔고 다시 15에 사서 20에 파는 것은 동일합니다. 즉 갯수제한이 없는 knapsack을 D-1일 동안 하는 것과 동일한 문제로 바뀌게 됩니다. $cache[i]$= 현재 사용가능한 돈이 $i$원일때, 얻을 수 있는 최대..

데이터베이스 연동 데이터베이스 연동에 사용되는 기술은 JDBC, 마이바티스, 하이버네이트와 같은 ORM에 이르기까지 매우 다양합니다. 특히 하이버네이트 같은 경우는 개발자가 직접 SQL을 작성하지 않아도 된다는 점에서 굉장히 편리합니다. 이후 여러 ORM이 등장하고 이를 표준화 한것이 JPA 입니다. 스프링 데이터 JPA는 복잡한 JPA를 간단하게 사용할 수 있게 해주는 스프링 모듈입니다. 연동 기술은 크게 SQL을 직접 다루는 기술과 프레임 워크가 SQL을 생성해주는 기술로 나눌 수 있습니다. 마이바티스는 SQL을 XML 파일에 직접 저장하여 사용하게 됩니다. 만일 추가적인 기능이 필요해 SQL을 수정하게 된다면 해당 SQL을 사용하는 코드또한 수정되어 번거롭습니다. 하지만 SQL을 직접 다루지 않는 ..

문제 https://www.acmicpc.net/problem/12865 알고리즘 knapsack 풀이 갯수제한이 있는 01 knapsack 문제입니다. $cache[i]$=현재 담은 무게가 $i$ 일때 얻을 수 있는 최대가치 안쪽 포문을 역순으로 고려하면 갯수를 하나 택할 때 상황만을 고려할 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N >> K; rep(i, N) rep(j, 2) cin >> bag[i][j]; rep(i, N) { for (int j = K; j >= bag[i][0]; --j) { cache[j] = max(cache[j], cache[j..

문제 https://www.acmicpc.net/problem/6066 알고리즘 Knapsack 풀이 갯수제한이 없는 01 Knapsack 문제입니다. $cache[i][j]$ = $i$번째 물건까지 택하고 현재 얻은 hay양이 $j$ 일때 지불해야하는 최소 금액 으로 가정하면 풀 수 있습니다. $cache[i][j]$가 갱신하는 다음 상태는 현재 상태에서 hay를 구매했을때 상태인 $cache[i][j+hay]$ 와 현재 물건을 택하지 않고 다음 물건을 택하는 $cache[i+1][j]$가 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N >> H; rep(i, N) ..

문제 https://www.acmicpc.net/problem/7045 알고리즘 DFS 풀이 각 정점을 루트로 했을 때, 서브트리 크기의 최댓값이 절반 이하가 되는 정점을 찾는 문제입니다. 문제에서 주어진 $N$ 제한은 1만이므로 각 정점마다 DFS를 돌리면 $O(N^2)$ 이므로 시간초과를 받게 됩니다. 한 정점에서 DFS를 시작하여 임의의 정점에 도달했을 때, 해당 정점의 서브트리의 크기는 재귀적으로 찾을 수 있습니다. 추가적으로 고려해야할 것은 현재까지 탐색한 트리의 크기입니다. 이 정보는 현재까지 탐색했던 트리를 제외한 서브트리 크기의 총합을 안다면 $N-sum[i]$를 통해 구할 수 있습니다. $sum[i]$는 서브트리크기의 총합을 의미합니다. DFS를 수행한 후 각 정점마다 $MAX[i]$ 값..

스프링 부트 로깅 애플리케이션을 운용하며 문제가 발생하면 로그 메세지를 보게 됩니다. 에러가 발생할때 뿐만 아니라 애플리케이션의 성능을 분석하는데에도 쓰는 등 다양한 용도로 사용됩니다. 마켓플레이스에서 ANSI Esacpe in Console을 설치하여 메인함수를 실행하면 로그 레벨별로 색깔이 구분되어 표기됩니다. Level Color 의미 1. ERROR Red 사용자 요청을 처리하는 중 문제 발생 2. WARN Yellow 현재는 처리가능, 향후 문제가능성 존재 3. INFO Green 상태변경과 같은 정보성 메세지 4. DEBUG Green 개발 시 디버깅 목적 5. TRACE Green DEBUG 레벨보다 더 상세한 메세지 로그 레벨은 우선순위가 정해져 있어 특정 로그 레벨을 지정하면 해당 레벨을..

문제 https://www.acmicpc.net/problem/1662 알고리즘 재귀 풀이 압축된 문자열이 주어졌을 때, 원래 문자열의 길이를 구하는 문제입니다. 재귀적인 시각으로 문제를 바라보면 이해하기 쉽습니다. $abcd(efg(hi))$ 와 같이 문자열이 주어졌다면 그대로 보기보다는 $abcd(*)$ 와 같이 이해를 해봅시다. 문제에서 주어진 문자열을 해결하는 함수 $solve()$가 있다면 우리는 $abc$ 길이에 $d$ X $solve(*)$ 와 같이 문제를 나눌 수 있습니다. $solve()$ 함수 내에서 또 다른 $solve()$를 호출하여 재귀적으로 해결하도록 합시다. 이 문제에서 생각해야할 부분은 괄호를 제외한 *에 해당하는 문자열을 인자로 넘겨주는 방법입니다. 올바른 괄호 문자열 문제..

스프링부트 테스트 웹 애플리케이션에서 개발자가 만든 컨트롤러가 정상적으로 동작하기 위해서는 서블릿 컨테이너가 구동되어야하고 브라우저를 통해 요청/응답 결과를 확인해야합니다. 하지만 컨트롤러가 수정될때마다 이러한 수행을 할 수 없기에 JUnit 기반의 단위테스트를 통해 컨트롤러를 검증하게 됩니다. 이를 위해 JUnit은 서버를 구동하지 않고 컨트롤러를 테스트하거나 컨트롤러와 연관된 비즈니스 컴포넌트를 실행하지 않고 컨트롤러를 독립적으로 테스트할 수 있어야합니다. 기존에 작성한 BoardController의 검증을 위해 다음과 같은 테스트케이스를 작성했습니다. package com.rubypaper; import org.junit.Test; import org.junit.runner.RunWith; impo..