PS
BOJ 1818 - 책정리
www.acmicpc.net/problem/1818 1818번: 책정리 동혁이는 캠프가 끝나고 집에 가서 책꽂이 정리를 하고 있었다. 책들은 한 줄로 길게 꽂히 있었다. 동혁이의 책은 1번부터 N번까지 숫자로 표현되고 현재 뒤죽박죽 되어있는 순서를 왼쪽부터 www.acmicpc.net LIS 알고리즘의 응용문제다 LIS 는 가장 긴 증가 부분 수열을 찾는 알고리즘으로 수열을 찾을때 이분탐색을 활용하여 찾아야만 O(NlogN) 의 시간 복잡도로 탐색이 가능하다. - 참고 : chanhuiseok.github.io/posts/algo-49/ 알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘 컴퓨터/IT/알고리즘 정리 블로그 chanhuiseok.github.io - C++ #include #define M..
BOJ 17828 - 문자열 화폐
www.acmicpc.net/problem/17828 17828번: 문자열 화폐 첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다. www.acmicpc.net 거의 구현문제에 가깝다 먼저 예외 처리 사항으로 1) 문자열 화폐의 값어치 X 가 길이 N 보다 작은 경우 2) 문자열의 길이 N개의 Z 가 있음에도 X 보다 작은 경우 만들수 없는 수 이므로 예외처리로 중단 시킨다. 예외처리를 거치면 문자열이 사전순으로 나와야 하기 때문에 A 로 먼저 다 초기화 시키고 그만큼 넣었으므로, X 에 N 을 뺀다 그리고 사전순으로 최대값을 찾아야 하므로 문자열 뒤에서 부터 탐색을 시도하면서 X 값이..
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]; // ..
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..