# 분할정복을 이용한 거듭제곱 - C**n연산은 x를 n번 곱하므로 O(N)이지만, 이 방법을 사용하면 O(logN)에 거듭제곱 값을 구할 수 있다. - 아래 코드에서 fpow함수가 그 방법이다. - n이 1이면 그냥 C의 1제곱이므로 return C를 해준다. - n이 2이상일 때, C의 n제곱은 다음과 같다. - n이 짝수이면 윗줄의 식을 만족하고, n이 홀수이면 아래줄의 식을 만족한다. 코드로 짜면 다음과 같다. 1. 재귀사용 def fpow(C, n): if n == 1: return C else: x = fpow(C, n//2) if n % 2 == 0: return x * x else: return x * x * C 2. 반복문 사용 - n & 1은 n이 짝수이면 0이므로 False이고, n이..
www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net (0, 0)에서 (M-1, N-1)까지 이동 가능한 경로의 수를 모두 구해야 하기 때문에 단순히 DFS로는 풀 수 없고, DP를 통해 메모이제이션까지 써야 한다. 1. N * M크기의 지도 m을 입력받고, dp배열을 만들고 -1로 채운다. 2. dp[i][j] = (i, j)까지 이동하는 경로의 수 3. (M-1, N-1)부터 상하좌우 방향을 탐색하며 dp[x][y]에 dfs(nx, ny)값을 더해준다. ->..
www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이번엔 DFS로 푼 문제이다. dfs함수: m[x][y] = 0을 해줌으로써 방문했다는 표시를 해준다. 전에 올린 문제와 비슷하게 nx, ny에 x + dx[i], y + dy[i]를 넣고 탐색한다. BFS는 nx, ny를 방문하지 않았을 경우, (nx,ny)를 deque에 넣고 방문처리를 해줬는데 DFS는 재귀방식으로 dfs함수를 또 호출한다. 매개변수로 cnt+1을 넘겨줌으로써 현재 단지에 속하는 집의 수를 ..
www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net N * M칸의 map을 입력받고 BFS를 돌려준다. 1. (0,0)부터 시작하므로 q에 (0,0)을 넣고 BFS 시작 2. i가 0부터 3까지 돌면서 nx = x + dx[i], ny = y + dy[i]를 통해 현재 좌표의 상하좌우를 모두 '넓게' 탐색한다. 3. 만약 (nx,ny)를 방문한적이 없고 map[nx][ny]가 1이면 q에 넣고 dist[nx][ny]에 dist[x][y] + 1을 저장하고 (nx,ny)에 방문했다는 표시를 한다..
www.acmicpc.net/problem/1260 기초적인 그래프 탐색 문제이다. (그 동안 배우지 않고 어려워보여서 손을 안대고 있었는데, 막상 강의를 듣고 스터디도 하면서 문제를 많이 풀어보니 할 만한 것 같다.) 그래프 탐색방법에는 크게 2가지가 있다. 바로 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)이다. DFS(Depth First Search) - 깊이 우선 탐색이란, 쉽게 말해 한 정점을 정해 끝까지 파고들어가는 방법이다. - 모든 노드를 방문하고자 할 때 이 방법을 쓴다. - 자기 자신을 호출하는 재귀방식을 사용한다. - 시간 복잡도 = O(V + E) (V: 정점의 수, E: 간선의 수) 단점 - BFS에 비해 조금 느리다. - DFS는 해를 구하면 탐색이 종료되므로, 구한 해가..
https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다. www.acmicpc.net * 분할 정복이란? - 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 분할 정복에도 여러가지 종류가 있지만, 이 문제는 쿼드트리(quad-tree)를 통해 풀어 보았다. (https://www.acmicpc.net/problem/1992 ..
https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,00 www.acmicpc.net 주어진 배열에 대해 입력받은 숫자의 갯수를 세야 하는 문제이다. 단순한 이분 탐색으로는 그 숫자의 위치는 찾을 수 있을지 몰라도..
https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 어렵진 않지만 소문제 4개로 나누어져 있고 정리할게 많아서 정리해본다. import sys, collections input = sys.stdin.readline numList = [] T = int(input()) for _ in range(T): n = int(input()) numList.append(n) numList.sort() print(round(sum(numList)/T)) print(numList[int(T/2)])..
모르는 사이에 조금씩 조금씩..
