전체 글
BOJ 1911 - 흙길 보수하기
www.acmicpc.net/problem/1911 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1 N >> L; for (int i = 0; i > start >> end; pools.push_back({start, end}); } sort(pools.begin(), pools.end()); int next = 0; for (int i = 0; i
DP 와 누적합
코딩테스트에 주요 유형 중 하나는 DP 와 누적합을 이용해서 푸는 문제들이 있다. 예제 1) 백준 1912 연속합 www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net N 개의 정수로 구성된 임의의 수열이 주어지고, 이들 중에서 연속된 몇개를 골라서 가장 큰 합을 구하는 문제이다. 이문제는 몇개를 고른다는게 정해져 있지 않고 그냥 구간합 중에서 최대 값이 되는게 얼마냐만 찾으면 되는 그런 문제다 - C++ #include #include using namespace std;..
BOJ 14728 - 벼락치기
www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 냅색 기본 문제인 백준 12865 평범한 배낭 문제와 사실상 똑같은 문제다 참고 : sdy-study.tistory.com/240 - C++ #include using namespace std; int N, T; int time[101], score[101]; // 각 단원별 예상 시간, 배점 int dp[101][10001]; // 첫번째 ~ i 번째 과목까지 봤을..
BOJ 17845 - 수강 과목
www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net 냅색 기본 문제인 백준 12865 평범한 배낭 문제와 사실상 똑같은 문제다. 참조 : sdy-study.tistory.com/240 - C++ #include #include using namespace std; int N, K; int importance[1001], time[1001]; // 중요도, 시간 int dp[1001][10001]; // ..
Intellij 에 Spring Framework 설정하기
Eclipse IDE 에서 작성하던 스프링 프레임워크 기반의 프로젝트를 Intellij IDEA 에 그대로 이식하면 아주 단순한 어플일 경우에는 될지도 모르나, 일반적으로는 있는 그대로는 이식이 안된다. 톰캣 서버 설정, 데이터베이스 서버 연결, 프로젝트 모듈 관리 등의 별도의 작업들이 필요한데, 아래에는 몇가지 예시를 넣어서 정리를 해보려 한다. (참고로, 스프링 부트가 아닌 스프링 프레임워크 기준이다) - 톰캣 서버 설정하기 먼저 프로젝트의 Edit Configuration 에 들어가면 Templates 부분에 아래 화살표를 눌러서 자세히 목록들을 살펴보면 아래 그림처럼 Tomcat Server 가 나온다 이 상태에서 우측 상단에 보이는 Create Configuration 을 눌러주고 아래와 같이 ..
BOJ 10026 - 적록색약
www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 그냥 BFS 를 두번 쓰면 되는 그런 문제였다. - C++ #include #include #include #define MAX 101 using namespace std; int N, answer1, answer2; int dy[4] = {-1, 1, 0, 0}; int dx[4] = {0, 0, -1, 1}; char adj[MAX][MAX]; bool visited[MAX][MAX]; void bf..
BOJ 2661 - 좋은 수열
www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 백트래킹을 이용해야 하는 문제다. N 자리 수 중에서 숫자를 1, 2, 3 만을 이용하여 인접한 부분수열 중 동일한 부분수열이 나오지 않도록 해야한다 그리고 좋은 수열 중에서 작은 수를 골라야 한다. 작은 수를 찾아내야 되기 때문에, 문자열 앞에서 부터 시작하는게 아니라, 뒤에서 부터 시작하는게 좋다 앞자리 수가 작은 숫자일 수록 전체적으로 작은 수가 되기 때문이다. - C++ #include #include using n..
BOJ 3114 - 사과와 바나나
www.acmicpc.net/problem/3114 3114번: 사과와 바나나 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net DP 와 누적합을 이용해서 풀어야 하는 문제이다. 불도저가 이동할 수 있는 방향은 오른쪽, 아래쪽, 대각선 오른쪽 아래 이렇게 3가지 인데, 각각의 경우에 대해서, 최대 누적합을 뽑아낼 수 있는 점화식이 필요하다. 사과에 대한 누적합과 바나나에 대한 누적합이 따로 있어야하기 때문에, 배열을 따로 따로 만들어서 선언해준다 (apple[][], banana[][]) dp 배열을 채우기 전에, 일련의 전처리 작업이 필요한데, 우측으로 ..