전체 글

1. 분류수학, 분할정복 2. 풀이 A를 B만큼 제곱한 수를 C로 나누어 나머지를 구하는 문제이다. 입력 범위가 int 한계치(2^32 - 1)기 때문에 자료형은 unsigned long long형으로 잡았다. 입력 한계치가 매우 큰 만큼 B번 거듭제곱할 때 O(N)으로 구하면 무조건 시간 초과가 나게 된다. B를 반씩 나누어가며 분할정복으로 거듭제곱을 구하면 시간 내에 풀 수 있다.

https://www.acmicpc.net/problem/1780 1. 분류분할정복 2. 풀이 대놓고 분할정복으로 풀라는 문제이다. 3의 제곱으로 입력이 주어진 입력을 계속 9등분하여 영역을 구해야 한다. 중앙부터 시작하여 조건이 충족되었는지 검사하고, 9등분으로 나뉜 각 영역의 중앙으로 이동하여 다시 검사한다. 재귀함수와 각 영역을 검사하는 함수를 만들었다. 1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 1. 재귀함수는 위의 두 가지 조건을 충족시켜야 한다. 1의 조건이 만족하지 않는 영역을 분할하며 각 영역의 중앙을 매개변수로 다시 재귀함수를 실행한다..

https://www.acmicpc.net/problem/1654 1. 분류이분탐색 2. 풀이 14627번 파닭파닭과 굉장히 유사한 문제이다(http://private-space.tistory.com/11). 파닭파닭 문제에서 조금 변형하여 해결했다. 3. 소스코드 #include typedef unsigned long long ull; ull wire[10000]; ull bs(int k, int n, ull max) { ull low = 1, high = max, mid = (low + high) / 2; while (low = n) low = mid + 1; else high = mid - 1; mid = (low + high) / 2; } return mid; } int main() { int k..

https://www.acmicpc.net/problem/14501 1. 분류다이나믹 프로그래밍 2. 풀이 퇴사하기 전 최대한 뽕을 뽑고 가는 방법을 구하는 문제이다. 한 번의 상담에 소모하는 기간이 있으며 그 동안에는 다른 상담을 진행하지 못한다. 각 상담에는 받을 수 있는 금액이 정해져 있고 완전히 종료해야만 수령할 수 있다. 최대 입력이 15정도로 낮기 때문에 어지간한 방법으로는 시간 제한에서는 상당히 자유로워 보인다. 아래는 문제를 해결하는 데 생각했던 것들이다. 1. 상담을 시작하면 (오늘 + t)일에 p만큼 정산을 받는다. - 이번 상담을 진행하는 것이 이익인지를 판단한다. 2. 1일차부터 계산해가며 마지막 날의 최대 금액을 출력한다. 3. 소스코드 #include int dp[25]; int..

https://www.acmicpc.net/problem/11561 1. 분류이분탐색 2. 풀이 최대로 밟을 수 있는 징검다리의 개수를 구하는 문제이다. 1~N까지의 징검다리가 있는데, 어디서 시작하던지는 상관 없다. 단, 다음 단계는 이전 단계보다 무조건 1개 이상 더 멀리 뛰어야 하며 N번째 징검다리는 반드시 밟아야 한다. 이 때 최대로 밟을 수 있는 개수는 무조건 첫 번째 징검다리부터 시작하는 것이다. 앞에서부터 1, 2, 3, ..., N항이라고 할 때 어짜피 이전 단계보다 1 이상만 더 멀리 뛰면 되기 때문에 N-1항과 N항의 거리는 상관 없고 1, 3, 6, 10, 15, ..., N 순서대로 뛰면 최대 개수가 될 것이다. 시작 항이 1인 등차수열의 공식 N * (N-1) / 2에 적합한 N값..

https://www.acmicpc.net/problem/1725 1. 분류스택, 스위핑 알고리즘, 분할정복 2. 풀이 주어진 히스토그램에서 최대 넓이를 갖는 직사각형의 넓이를 구하는 문제이다. 히스토그램을 이루는 막대의 개수와 각 막대의 길이를 입력으로 받는다. 막대기들의 높이는 입력받은 숫자이며 폭은 1로 고정되어 있다. 예제 입력이 최대 10만개까지인데, 100000의 제곱은 100억이므로 O(N^2)으로 풀면 시간초과가 날 것이다. 위의 분류에서 소개한 스위핑 알고리즘을 쉽게 설명하면 진행할 한 쪽 방향을 정하고 쓱 훑고 지나가며 값을 찾는 방법인데 이런 문제에 아주 적합하다. 그림으로 그리면 아래와 같다. 7개를 입력받았을 때 단 7번만 검사하므로 시간 복잡도는 O(N)이다. 입력의 최대값을 주..

https://www.acmicpc.net/problem/14627 1. 분류이분탐색 2. 풀이 시장에서 사 온 파의 일정량을 파닭에 넣고 남은 파는 라면에 넣어 먹으려고 한다. 주어진 조건은1. 하나의 파닭에 한 개 이상의 파를 넣을 수 없고2. 같은 양의 파를 넣어야 하며3. 파닭에 넣을 파는 최대치가 되어야 한다는 것. 예제 입력은 다음과 같다.3 5440350230 파의 개수 3개, 주문받은 파닭의 개수 5개와 각 파의 길이가 입력으로 주어진다. 문제에 모호한 점이 있었다. 파는 1개 이상 넣을 수 없으니 파의 길이는 아무리 길어도 230을 넘을 수 없다라고 생각했었는데 그렇게 코드를 작성하니 0% 입구컷을 당해버렸다... 파닭에 같은 양의 파를 넣어야 하므로 이분 탐색의 초기 high값은 (파 ..

1. 학습 사이트 1) 백준(https://www.acmicpc.net) : 추천 2) 알고스팟 (https://algospot.com)알고리즘 문제 해결 전략 세트작가구종만출판인사이트발매2012.11.01.리뷰보기 ※ 위 책의 저자가 운영자로 있는 곳. 3) 코드포스 (http://codeforces.com) 4) 탑코더 (http://topcoder.com) ※ 코드포스와 탑코더는 rating 제도가 있음. 2. 공부 방법 1) 완벽하게 이해할 필요는 없다. 2) 한 문제는 최대 2시간까지만 시도하자. 모르겠으면 정답이나 풀이를 보고 분석한다. 3) 모르는 부분은 반드시 해결하고 넘어간다. 4) 어떻게 문제를 풀 것인지 생각을 많이 하는 것이 중요하다. 3. 언어 1) 사용하는 언어의 비중 : C++..