문제 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..
스타터 이해하기 스프링부트는 복잡한 라이브러리 관련 설정을 위해 스타터를 사용합니다. 스타터는 실행에 필요한 라이브러리들을 관련된 것끼리 묶어서 제공합니다. 만일 데이터베이스 연동을 위해 JPA 라이브러리만 다음과 같이 추가했다고 해봅시다. org.hibernate hibernate-entitymanager 5.4.32.Final 하지만 JPA와 연동하기 위해서는 하이버네이트말고도 spring-orm.jar 과 spring-data-jpa.jar와 같은 라이브러리가 추가적으로 필요합니다. 이러한 문제를 해결하기 위해 스프링부트는 관련된 라이브러리를 묶어 스타터로 제공합니다. org.springframework.boot spring-boot-starter-data-jpa POM파일 상속구조 스타터에는 ve..
WebApplicationType 스프링부트는 웹 애플리케이션이나 일반 자바 애플리케이션으로 실행가능합니다. 아무런 설정을 하지 않았을 때는 웹 애플리케이션으로 실행이 되어 내장된 톰캣서버가 실행됩니다. 일반 자바 애플리케이션으로 실행하기 위해서는 SpringApplication의 WebApplicationType을 NONE으로 수정해야합니다. 만일 값이 NONE이 아닌 SERVLET으로 되어있다면 다시 웹 애플리케이션으로 실행됩니다. @SpringBootApplication public class Chapter01Application { public static void main(String[] args) { SpringApplication application = new SpringApplicatio..
문제 https://www.acmicpc.net/problem/5214 알고리즘 BFS 풀이 역들을 잇는 하이퍼튜브들이 주어질 때, $N$역으로 가기 위해 거쳐야하는 최소 역의 수를 구하는 문제입니다. 하이퍼튜브마다 일일이 역들을 연결하게 되면 메모리초과가 발생합니다. 대신에 하이퍼튜브마다 임의의 정점을 하나씩 만든 후, 각 역과 새로 만든 임의의 정점끼리 연결하여 메모리를 절약하였습니다. 위 그림은 문제에서 주어진 첫번째 예시에서 첫번째 하이퍼튜브와 두번째 하이퍼튜브를 시각화한 것입니다. 저는 튜브마다의 임의의 정점을 100005+$i$로 하였습니다. 검은 실선을 가중치 1로 설정하여 풀고난 후, 마지막에 반을 나누어 실제로 거친 역의 수를 구했습니다. 코드 #include #define rep(i, ..
문제 https://www.acmicpc.net/problem/2437 알고리즘 Greedy 풀이 $N$개의 저울이 주어졌을 때, 잴 수 없는 무게의 최솟값을 구하는 문제입니다. 기존에 잴 수 있는 구간이 [0,R] 일 때, 새로운 추 A가 새로이 등장하면 새롭게 잴 수 있는 구간은 [A,A+R] 일 것입니다. 만일 R+1>=A 라면 이 구간은 [0,A+R]로 통합되어 잴 수 있는 구간이 새로이 갱신되겠지만 아니라면 답은 R+1입니다. 즉, 추의 무게를 정렬한 후 R과 추가할 추 A의 무게를 계속해서 비교해주면 됩니다. R은 잴 수 있는 무게의 최댓값이므로 지금까지의 추의 무게의 총합입니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #defi..
- Total
- Today
- Yesterday
- 세그먼트트리
- 동적계획법
- 펜윅트리
- 이분매칭
- Fenwick
- 정렬
- 2-SAT
- 좌표압축
- Oracle
- string
- bfs
- implementation
- hld
- Segment tree
- 스위핑
- spring boot
- sorting
- dijkstra
- DP
- union find
- 트라이
- kmp
- 이분탐색
- dfs
- spring
- greedy
- sweeping
- knapsack
- Suffix Array
- SCC
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |