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++..
1. 수학적 귀납법가장 유용하게 사용되는 방식. 대부분의 알고리즘이 반복적인 요소를 가지고 있기 때문이다. 1) 단계 나누기 : 증명하고자 하는 문제를 여러 단계로 나눔. 2) 첫 항 증명 : 첫 번째 단계가 참인지를 증명 3) 귀납 증명 : 첫 번째가 참이면 N번째 단계도 참인지를 증명 2. 반복문 불변식반복문의 내용의 중간 결과가 어떠한 경우에도 우리가 원하는 답으로 가는 길 위에 있는지 명시하는 조건 1) 반복문 진입 전 불변식이 성립함을 증명 2) 반복문 내용이 불변식을 깨뜨리지 않음을 증명 3) 반복문 종료 시 불변식이 성립하면 정답을 구한 것임. 3. 귀류법원하는 상황과 반대의 경우를 가정하고 논리를 전개하여 결론이 잘못되었음을 증명하는 방법.
https://www.acmicpc.net/problem/1676 N!의 뒤에서부터 0 개수를 세는 문제. N의 값은 0부터 500인데, 12!만 되어도 4억이 훌쩍 넘는다. 당연히 팩토리얼을 직접 구해서 풀 수 없다. 조금 달리 생각하여, 어떠한 값에 x10을 계산하면 뒤에 0이 하나씩 생긴다는 것에 주목했다. N의 값을 받고 그 값을 소인수분해하여 (2 * 5) 한 세트당 1씩 증가시키면 된다. 2는 굉장히 많이 곱해질 것이기 때문에 결국 5의 개수만 세면 끝이다. 5! = 1 * 2 * 3 * 4 * 5 = 1 * 3 * 4 * (2 * 5) = 12 * 10 = 120 ※ 1개 10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = 1 * 3 * 4 * 6 * 7 * ..
https://www.acmicpc.net/problem/1874 스택 문제에서 조금 더 꼬아본 문제. 풀 때는 오래걸렸는데 스택의 기본 개념을 고려하면 쉽게 풀 수 있던 문제였다. 불가능한 경우는 입력값(pop했을 때의 값)이 stack[top]과 다른 경우가 되겠다. push와 pop이 각 n번씩 수행되고 n번 입력하므로 O(3n) = O(n)으로 풀 수 있다. stack용 배열 하나와 예제 출력에 불가능한 경우 NO, 가능한 경우에만 +, -로 표현하도록 되어 있으니 출력용 배열을 하나 더 만들었다. #include int stack[100000] = { 0 }; char out[200000] = { 0 }; int main() { int n, in = 0, stTop = 0, outTop = 0;..
https://www.acmicpc.net/problem/3344 백트래킹에서 유명한 문제 중 하나인 N-Queen이다. N값을 입력받고 N * N 크기의 체스판에 N개의 서로 공격하지 못하는 위치에 퀸을 놓는 것. 그런데... 문제가 좀 다르다. N의 값은 8, 26, 213, 2012, 99991, 99999 중 하나로 정해주었다. 그리고 만족하는 퀸들의 위치를 아무거나 한 개씩만 출력하면 되는 문제이다. N값 중 99991, 99999이 존재하는 것으로 보아 시간복잡도가 O(n2) 이상이면 시간 초과가 날 것이다. 백트래킹 관련 문제를 별로 풀어본 적도 없어서 공부도 할 겸 백트래킹으로 짜보았으나 역시 시간초과로 실패했다. 번뜩 생각이 난게 같은 x, y축, 대각선의 조건을 거스는 것이 하나 있었다..
