전체 글

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축, 대각선의 조건을 거스는 것이 하나 있었다..

https://www.acmicpc.net/problem/1011 시작점 x부터 도착점 y까지 이동하는 문제. 이동 횟수를 구해야 한다. 이동 속도는 1부터 시작하고, 한 번 이동할 때마다 ±1씩 증감한다. 마지막 지점에 들어오는 속도는 반드시 1이 되어야 한다는 조건이 있다. 즉, 속도는 1씩 증가하여 중간 지점에서 최대치에 도달한 후 서서히 감소하여 다시 1로 돌아온다. 규칙을 찾아보기 위해 표로 정리해 보았다. 두 지점 사이의 거리 최적의 속도 변화 1 1 2 11 3 111 4 121 5 1211 6 1221 7 11221 8 12221 9 12321 10 112321 11 122321 12 123321 ... ... 1번 이동 : 1항부터 2번 이동 : 2항부터 3번 이동 : 3항부터 4번 이동..

https://www.acmicpc.net/problem/1463 정수 X를 1로 만드는 연산의 최소 횟수를 구하는 문제이다. ① 3으로 나누기 ② 2로 나누기 ③ 1 빼기 1로 만드는 가장 빠른 것은 1번 연산이다. 그 다음은 2로 나누기, 1 빼기 순이 될 것이다. 숫자 1은 이미 1이므로 연산이 필요 없고 2와 3은 1번의 연산을 해야 한다. int d[1000001] = { 0, 0, 1, 1, }; 여기서 d[X]은 X을 나누는 최소 횟수이다. 배열의 인덱스는 X의 최대값인 106 + 1 까지이며 0~3을 1로 만드는 최소 횟수를 초기화했다. 3까진 이미 정했으니 4부터 규칙을 차근히 생각해보면 숫자 4를 만드는 방법 : 2 * 2, 3 + 1 숫자 5를 만드는 방법 : 4 + 1 숫자 6를 만..

https://www.acmicpc.net/problem/6588https://www.acmicpc.net/problem/9020 유사한 두 문제에 관한 풀이이다. 소수를 구하는 방법은 여러가지가 있다. 가장 간단한 방법으로는 임의의 숫자 n에 대하여 [1, n-1]의 범위에서 일일이 나누어보는 방법이 있겠지만 시간의 제약이 있는 알고리즘 문제에서는 사용할 수 없다. 소수를 구하는 유명한 알고리즘으로 '에라토스테네스의 체'가 있는데, 이 문제에서도 힌트로 주어져 있다. 소스 코드로 적용하기는 쉽다. 우선 bool 또는 정수형 배열 하나를 만든다. 나는 간단하게 c라고 정의했다. 우선 모든 값을 0으로 초기화하고, 숫자 n이 소수라면 c[n]의 값은 1이 된다. for(int i = 4; i