study/PS
-
[백준 1629] 곱셈 python (수학)study/PS 2021. 2. 4. 22:49
자연수 A를 B번 곱한수를 만들고 이를 C로 나눈값을 출력하면 된다. A ** B % C 하면 될 것 같지만 시간 복잡도 O(B)이기 때문에 시간 초과한다... 매우 크게.. 이때 이진수를 활용하면 빠르게 풀이 할 수 있다. 아이디어 : 거듭제곱은 거듭제곱 간의 곱으로 표현 가능하다. A^13이라는 값을 이진수로 표현하면 A^1101이 되는데 1101 / 2 => 110 ... 1 110 / 2 => 11 ... 0 11 / 2 => 1 ... 1 1 / 2 => 0 ... 1 이렇게 2로 나누면 나머지가 원래 가지고 있던 이진수가 됨을 알 수 있다. A^13 = A * A^4 * A^8 조건문 + N진수 변환 방법으로 해결 가능하다는 것을 알 수 있다. def answer(a, b): ret = 1 w..
-
[백준 1309] 동물원 C++ (DP, 다차원)study/PS 2020. 2. 21. 16:02
다이나믹 프로그래밍으로 풀이가 가능한 대표적인 문제입니다. 일차원 배열을 사용하여 풀이할 수 있지만, 이차원 배열을 사용하여 풀이하는 방법도 존재합니다. 코드 #include using namespace std; const int mod = 9901; int n; int d[100010][4]; // d[n][m] = n은 2*n배열에 사자를 배치하는 경우의 수 // m은 배치 방식(배치x, 왼쪽, 오른쪽) int main(void) { scanf("%d", &n); d[1][1] = 1; //배치 x d[1][2] = 1; //왼쪽 배치 d[1][3] = 1; //오른쪽 배치 for (int i = 2; i
-
[백준 1012] 유기농 배추 C++ (bfs, dfs)study/PS 2020. 2. 10. 16:38
BFS, DFS를 이용하는 탐색문제인 유기농 배추입니다. 저는 BFS를 이용하며 풀었지만, DFS역시 사용 가능합니다. 테스트 케이스 방식의 입력을 받기 때문에 각각의 테스트 케이스마다 배열을 초기화 해주는 부분이 필요로 합니다. 풀이 #include #include #include using namespace std; typedef pair p; queue q; int n, m, k; int map[51][51]; int visited[51][51]; int cross_x[] = {0, 0, -1, 1}; int cross_y[] = {1, -1, 0, 0}; void bfs(int x, int y) { visited[x][y] = 1; while (!q.empty()) { x = q.front().f..