컴공과컴맹효묘의블로그

https://www.acmicpc.net/problem/11066 이 문제를 봤을 때 Priorty Queue로 풀 수 있을 줄 알았다. 하지만 제약 조건에서 "연속이 되도록 파일을 합쳐나가고, ..."라는 인접 제약조건이 있기 때문에 인접 조건을 무시하는 Priorty Queue로 풀 수 없었다. DP문제라는 사실을 알아도 풀지 못해 정답을 찾아봐도 처음엔 이해하기 어려웠다... 풀이DP[i][j]를 파일 i번부터 j번까지 합쳤을때 최소비용 이라고 정의하자. 이러면 DP[1][N]이 정답이다.그리고 SUM[i][j]는 파일 i번부터 j번까지 파일을 합친 크기라 정의하자. 그러면 다음과 같은 수식을 구할 수 있다.DP[i][j] = min(DP[i][m] + DP[m+1][j] + SUM[i][m] +..

https://www.acmicpc.net/problem/1725 입력이 10만이라, O(N^2)은 시간 내 풀이가 불가능합니다. "이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야한다." 에서 아래쪽 밑변은 히스토그램의 아랫변과 겹치게 그리는 것이 항상 최대이고, 위쪽 밑변은 직사각형이 포함하는 막대들의 높이 중 최소인 막대의 윗변과 겹쳐야합니다. O(NlogN)가 걸리는 분할정복으로 풀어봤습니다.하나의 히스토그램을 절반으로 잘라서 왼쪽의 최대와 오른쪽의 최대, 그리고 중간을 포함하는 큰 히스토그램의 최대를 구하여 비교합니다.중간을 포함하는 큰 히스토그램은 투 포인터로 O(N)이 걸립니다. left와 right를 각각 mid, mid+1로 초기화 하고 left-1, right+1의 높이..

https://www.acmicpc.net/problem/1241 첫 아이디어는 각 학생들의 머리위 숫자에 배수를 한 지점에 1씩 더하는 아이디어다.2 1 2 3 4를 예를 들면, 2는 2, 4에 1을 더하고 1은 1, 2, 3, 4, 3은 3, 4는 4 이렇게 하면 결과는 다음과 같다. arr[1] = 1, arr[2] = 3, arr[3] = 1, arr[4] = 3 결론부터 말하지만 이 코드는 시간초과가 난다.#include #include #include #include #include #include #include #include #define INF 987654321#define lld long long#define MAX_N 1000001using namespace std;int arr[M..

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 순서는 상관 없고 두 수를 골라서 서로 차이가 M상의 최소값을 구하면 되니까 일단 서로 인접한 차이를 배열에 저장해두고, 어떻게든 하면 답을 구할 수 있을것이라고 생각했다. 하지만 이 생각은 아주 틀렸다. 그냥 단순히 두 개의 포인터 left와 right를 이용하면 답을 쉽게 구할 수 있었다. 입력받은 배열을 정렬하고 두 포인터의 값의 차이를 이용해서 right와 left를 적..

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 쉬운 BFS문제이다. 그러므로 여기서는 내가 이 문제를 풀면서 공부한 내용을 적어볼까 한다. #include #include #include using namespace std; int N, K; queue q; bool visited[100001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie..

https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net . 준석이는 주어진 시간 안에 최대한의 점수를 주는 과목들을 공부해야한다. 각 과목은 cost와 그에대한 가치 value가 있다. 주어진 cost 안에 과목들의 가치의 총 합이 최대가 되게하는 과목집합을 구해야한다. 이 문제를 어떻게 풀어야할까? 쉬운 방법으로는 모든 경우의 수를 구할 수 있다. 하지만 단순 계산해보아도 경우의 수가 2^100이나 된다...

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 방법 첫 번째: linked list로 구현. 두 번째: stack로 구현 세 번째: list로 구현 효율성은 stack > list > linked list 순으로 좋다. 1. stack의 풀이는 두 개의 stack을 만들어서 커서 기준으로 좌측은 s1, 우측은 s2로 저장한다. 2. list는 풀이가 조금 어렵다. dat, pre, nxt라는 배열을 만들고 nxt에 따라 값을 출력한다. d..

문제 및 참고 사이트 https://www.acmicpc.net/problem/1019 https://mygumi.tistory.com/180 https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019 풀이 처음 봤을 때 이 문제를 어떻게 풀어야할지 brute force 이외에는 전혀 생각나지 않았다. 이 문제를 쉽게 풀 수 있는 핵심은 문제를 작은 단위로 나누는 것이다. 핵심 아이디어는 각 자릿수를 따로 계산하자라는 것이다. 즉, 1의 자릿수, 10의 자릿수... 를 따로 따로 세서 합치는 아이디어가 이 문제를 최적화 할 수 있는 핵심이다. 정확한 문제 풀이 이해는 백준님의 자료를 참고하자. 코드 #include #include using names..

백준 알고리즘[9694] 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 문제 한신이는 젊고, 똑똑하고 매우 유명한 정치인이다. 그럼에도 그는 여전히 자신의 성공을 위해서도 인간관계는 중요한 것이라고 믿고 있다. 다음 달에 열릴 국회의원선거에서 한신이는 자신의 당이 반드시 이기길 희망한다. 그러기 위해서 최고의원의 지지가 필요하다. 이 최고의원의 지지를 받기위해 한신이는 전략을 세웠다. 그는 그 최고의원을 직접적으로 만날 수 없다면 그를 알고 있는 인맥을 이용하여 만날 것이다. 이것을 위해서 우선 정치인들의 친밀도를 조사하였는데 친밀도를 다음 4단계로 나누어서 기록해놓았다. 최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4] [두 사람의 관계는 이 4가지 경우중 반드시 해당되며, 적(en..

문제 사이트: https://www.acmicpc.net/problem/2410 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 어떤 자연수 N을 2의 멱수의 합으로 나타내는 경우의 수를 구하는 프로그램을 작성하시오. 2의 멱수라는 것은, 2^k으로 표현되는 자연수를 의미한다. 예를 들어 7을 2의 멱수의 합으로 나타내는 경우의 수는 다음의 여섯 가지가 있다. 1+1+1+1+1+1+1 1+1+1+1+1+2 1+1+1+2+2 1+1+1+4 1+2+2+2 1+2+4 입력 첫째 줄에 N(1≤N≤1,000,000)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로..