문제 www.acmicpc.net/problem/20971 알고리즘 DP 풀이 특정 구간을 칠하지 않은 상태로 할 때, 남은 구간들을 칠하기 위한 최솟값을 구하는 문제입니다. 문제의 가장 큰 특징은 페인트를 칠하는 순서가 정해져 있다는 것입니다. 이를 유의하며 풀도록 합시다. 쿼리를 빠르게 처리하기 위해 DP 아이디어를 떠올렸습니다. 특정 구간에 대한 DP를 사용하기 위해선 $cache[i][j]$와 같은 배열을 사용할 수 있는데, 구간의 길이가 100,000 이라는 점에서 해당 2차원 배열을 사용하기는 어렵습니다. 하지만 문제를 자세히 보면 특정 구간을 칠하기 위한 최솟값이 아닌 특정 구간을 제외한 나머지 구간을 칠하기 위한 최솟값을 묻고 있습니다. 이는 DP의 정의가 "앞에서부터 길이 $N$인 구간을..
문제 www.acmicpc.net/problem/18320 알고리즘 이분탐색 풀이 갚을 금액, 기한, 하루에 최소 갚을 금액이 주어졌을 때, 조건을 충족하는 $X$를 구하는 문제입니다. 문제를 풀기 위한 첫 번째 단계는 $X$를 결정해야하는 것입니다. 결정문제는 이분탐색으로 바꿀 수 있습니다. 이 문제가 어려운 이유는 $X$를 결정했을 때, 그대로 시뮬레이션하여 $K$일 이내에 돈을 갚을 수 있는지 계산하게 되면 시간초과가 발생하기 때문입니다. 이유는 $N$제한이 $10^{12}$이기 때문입니다. $X$를 결정하는 시간복잡도는 $O(logN)$에 해당하는데 그대로 시뮬레이션 하게 되면 $X$마다 선형시간이 요구되기 때문입니다. 한가지 할 수 있는 관찰 중 하나는 John이 갚아나가는 금액은 비오름차순의 ..
문제 www.acmicpc.net/problem/9376 알고리즘 01BFS 풀이 한 사람이 두 죄수를 탈옥시키기 위한 최소 문의 수를 구하는 문제입니다. 3인 통화문제와 마찬가지로 세 사람의 위치를 구한 후 다익스트라를 세번 사용하면 풀 수 있는 문제입니다. 죄수의 위치는 주어지지만 구출하는 사람의 위치는 주어지지 않습니다. 주어지는 공간(N X M)을 테두리를 확장하여 (N+2 X M+2)로 만듭니다. 이렇게하면 구출하는 사람의 위치를 임의로 (0,0)으로 설정해도 됩니다. BFS는 이동에 사용하는 값이 모두 동일할 때, queue를 사용해서 원하는 목표까지의 거리를 구하게 됩니다. 다익스트라는 이동에 사용하는 값이 다를 때 사용하는데, 가중치가 0과 1로만 주어져 있을 때는 다익스트라보다 더 빠르게..
문제 www.acmicpc.net/problem/2398 알고리즘 Dijkstra 풀이 세명이 통화를 하기 위해 간선들을 연결하기 위한 최소비용, 그 때 사용하는 간선들을 출력하는 문제입니다. 사람들이 그래프 위에서 움직여 최적의 장소에서 모이는 문제로 해석해보겠습니다. 각 사람마다 각 노드마다의 최소거리를 알 수 있다면 즉, 한 지점마다 세 사람의 최소거리를 안다면 우리는 어디 지점에서 세 사람이 만나야 하는지 알 수 있습니다. 사람마다 다익스트라를 돌려 총 세번의 다익스트라를 수행하고 그때마다 그 사람이 어디 노드에서 어디 노드로 갔는지를 기록하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (..
문제 www.acmicpc.net/problem/4716 알고리즘 greedy 풀이 방 A, B에 풍선이 있고 각 팀마다 방마다의 거리와 얻을 풍선수가 주어질 때 최소로 이동하는 거리를 구하는 문제입니다. 이 문제의 답을 가장 방해(?)하는 것은 방과의 거리가 먼 팀입니다. 답을 최소로 만들어야하는데 먼 거리를 통해 해당 팀에 풍선을 전달하면 답을 찾기가 어려워집니다. 입력 예제에서 3번팀은 각 방과의 거리가 40과 10입니다. 거리가 10인 방을 이용해서 풍선을 전달해야 거리가 40인 방의 풍선을 전달받지 않아 최소로 답을 구할 수 있을 것입니다. 그렇다면 우선적으로 고려해야할 것은 방과의 거리가 먼 팀일까요? 비슷하긴 하지만 답은 아닙니다. A방에서 가져올 풍선을 B방을 선택해서 이득을 보거나 B방에..
문제 www.acmicpc.net/problem/17493 알고리즘 DFS 풀이 포레스트에서 트리의 지배집합의 수를 찾는 문제입니다. 동아리의 홍보효과가 인접한 지역까지 영향을 미칩니다. 하나의 트리에서 문제를 살펴보겠습니다. 잘 생각해보면 리프노드에는 굳이 홍보를 할 이유가 없습니다. 리프노드에 홍보를 하면 자신의 부모노드에만 영향을 미치지만 그 부모노드에 홍보를 하게 되면 리프노드뿐만 아니라 그 부모가 갖는 자식들에게 모두 홍보를 할 수 있기 때문입니다. 즉 리프노드의 부모노드는 무조건 홍보를 해야 이득임을 알 수 있습니다. [잘못된 풀이] 처음에 이 문제를 리프노드의 부모로부터 BFS를 수행해 현재 노드가 빨간 노드(홍보노드)면 주변은 노 란노드(영향을 받는 노드), 현재 노드가 노란 노드면 주변을..
날짜 값 변환 사용자가 설정한 기간 사이에 회원가입을 한 멤버들을 확인하는 요청을 하고 싶은 경우가 있습니다. 이를 위해 MemberDao 클래스에 다음과 같은 메서드를 추가할 수 있습니다. private RowMapper memRowMapper = new RowMapper() { @Override public Member mapRow(ResultSet rs, int rowNum) throws SQLException { Member member = new Member(rs.getString("EMAIL"), rs.getString("PASSWORD"), rs.getString("NAME"), rs.getTimestamp("REGDATE").toLocalDateTime()); member.setId(rs...
Session 웹 프로그래밍은 여러 웹서버 프로그램들이 모여 이루어지는 것이라고 볼 수 있습니다. 클라이언트에서 특정한 요청을 하면 웹서버는 알맞는 프로그램을 찾아 실행한 후 종료하게 됩니다. 이 때 실행되는 프로그램은 실행이 완료된 후 메모리에서 제거됩니다. 이 때문에 다음 요청에서 이전에 실행한 결과를 담은 값들에 대해 접근을 할 수가 없습니다. 이 문제를 해결하기 위해 전역변수와 같이 저장공간을 두어야합니다. 이러한 저장공간은 크게 HttpSession과 Cookie로 나눌 수 있습니다. 우선 알아볼 것은 Session을 활용하여 로그인 상태를 유지하는 방법에 대해 알아보겠습니다. 우선적으로 세션에 저장할 객체를 정의해야합니다. package spring; public class AuthInfo {..
- Total
- Today
- Yesterday
- union find
- 2-SAT
- 정렬
- knapsack
- implementation
- sorting
- 이분탐색
- 스위핑
- spring boot
- kmp
- Fenwick
- string
- 세그먼트트리
- 동적계획법
- greedy
- Oracle
- Suffix Array
- dijkstra
- 펜윅트리
- DP
- 트라이
- Segment tree
- sweeping
- dfs
- 좌표압축
- bfs
- SCC
- 이분매칭
- hld
- spring
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |