코딩성장스토리

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 100,000,000,000번 곱해야하는 문제이다 . 즉 시간복잡도가 O(log n)이 아니면 불가능 하다. 그래서 분할 정복을 생각하였다. 문제 풀이는 제곱수가 n이라 하고 행렬 a가 있다고 할 때, ex)n=10이라고 하자. 나는 재귀로 풀었기에 n은 1,2,4,5,10으로 올라가는 형태이다. 즉 n=1일때 A n=2일때 A*A=A^2 n=4일 떄 는 (A^2)*(A^2)=A^4 n=5일 때 는 ..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 이 문제는 처음에 순열을 이용해서 일일이 위치값 변경하면서 더했는데 이럴경우 시간복잡도가 (n*n!)가 나와 시간초과가 나온다 그 다음으로 재귀함수를 구현해서 모든 부분집합을 구햇다. 시간복잡도는 (2^n-1)이 나오고 시간초과는 나오지 않았다. 함수에는 부분집합의 합과 배열 몇 번째인지 를 인자로 받고 몇번쨰 배열 인자를 더하는 경우와 안더하는 경우를 나누어서..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 이 문제는 재귀를 이용해서 풀었는데 알파벳이 중첩이 안되어야하니 알파벳 중첩을 확인할 체크 배열을 두고 움직이는 함수 go에서 왼쪽, 오른쪽,위쪽,아래쪽 총 4번이동할 경우를 재귀적으로 풀었다. 코드를 보는게 쉽다 #include using namespace std; char alpa[20][20]; bool check[26]; int r,c; int max; void go(int row,..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 이 문제는 재귀를 이용해서 풀었다. 일단 빈 칸에 들어 갈 수 있는 값을 배열에 저장을 하고 그 배열에 있는 값을 스도쿠에 넣은다음에 다음 빈칸을 가서 다시 들어갈수 있는 값을 넣고 만약에 들어갈 수 없으면 다시 돌아오는 재귀를 이용했다. 코드를 보고 이해하는게 빠르다. #include #include using namespace std; int sdq[9][9]; int go(vector& bl..