수학은 재밌다. 시험 치는게 힘들어서 그렇지. 귀납법이나 귀류법과 같은 강력한 논리 도구들을 가지고 새로운 성질을 찾아내는 과정과, 증명의 누적은 가히 인류 문명의 유산이라 할 수 있다. 대입을 위한 고등학교 수학은 대수학의 일부분에 국한되는데, 그러다보니 수학이라는 학문의 재미있는 부분들을 많이 놓치게 된다. 시험이라는게 어쩔 수 없이 줄세우기를 할 수 밖에 없지만, 그래도 아쉬운 부분이다. 이 책은 그동안 수학을 문제풀이로만 생각했거나, 지루하지만 억지로 공부했던 과목이라고 생각했던 사람들에게 수학에 대한 새로운 시선과 관념을 제공하는 책이다. ...
백준 17626번 바로가기 나의 풀이 # 입력 import sys n = int(sys.stdin.readline().strip()) squares = [i**2 for i in range(1,int(n**0.5)+1)] queue = [n] count = 0 # 처리 - bfs 활용 while len(queue) > 0: count += 1 temp = set() for q in queue: for s in squares: if q < s: break temp.add(q-s) if 0 in queue: break queue = list(temp) print(count-1) 고수의 풀이 dp = [50001 for i in range(n + 1)] dp[0] = 0 for i in range(1, n + 1): for j in range(1, i + 1): val = j * j if val > i: break dp[i] = min(dp[i], dp[i - val] + 1) print(dp[n]) 출처 CODE REVIEW 처음에는 제곱수들을 역순으로 배열해서 차례대로 빼면 되겠지 생각했지만, 그게 최선의 수가 아니라는걸 깨달았다… bfs을 응용해서 n에서 0까지 top2bottom 방식으로 알고리즘을 구상했다. BFS(너비 우선 탐색) 방식이 층별로 내려가는 식이라 과정이 유사하다는 점에서 착안했다. dp로는 도저히 풀어내는 방법을 모르겠어서 다른 사람의 풀이를 참고했다. 짧고 깔끔하게 잘 짰구만…👍👍 min(dp[i], dp[i-val]+1) 발상이 쉽지 않다. 허허
백준 2178번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline n,m = map(int, read().split()) maze = [] for _ in range(n): maze.append(list(map(int,read().strip()))) dx = [1,-1,0,0] dy = [0,0,1,-1] # 처리 - bfs 활용 def bfs(x, y): from collections import deque queue = deque() queue.append((x,y)) while queue: x,y = queue.popleft() for i in range(4): new_x = x+dx[i] new_y = y+dy[i] if 0<=new_x<n and 0<=new_y<m and maze[new_x][new_y] == 1: queue.append((new_x,new_y)) maze[new_x][new_y] = maze[x][y] + 1 bfs(0,0) print(maze[n-1][m-1]) CODE REVIEW 처음에는 DFS을 이용해서 문제를 풀어내려하다가 최적값을 찾는데 애를 먹었다. 미로찾기 문제에서 최단경로를 찾기 위해서는 BFS가 편리하다. 어느정도 난이도 있는 문제를 풀 때에 무작정 풀어나가지 말고, 어떤 전략이 나을지 고민해보는 자세를 가지자!
백준 2667번 바로가기 DFS을 이용한 풀이 # 입력 import sys read = sys.stdin.readline n = int(read().strip()) graph = [] for _ in range(n): graph.append(list(map(int, read().strip()))) dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] # 처리 - dfs 활용 def DFS(x, y): if not 0<=x<n or not 0<=y<n: return False if graph[x][y] == 1: global count count += 1 graph[x][y] = 0 for i in range(4): nx, ny = x + dx[i], y + dy[i] DFS(nx, ny) return True return False count = 0 ans = [] for i in range(n): for j in range(n): if DFS(i,j): ans.append(count) count = 0 print(len(ans)) for a in sorted(ans): print(a) BFS를 이용한 풀이 # 입력 import sys read = sys.stdin.readline n = int(read().strip()) graph = [] for _ in range(n): graph.append(list(map(int, read().strip()))) dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] # 처리 - BFS 활용 def BFS(x, y): from collections import deque queue = deque([(x,y)]) graph[x][y] = 0 count = 1 while queue: x,y = queue.popleft() for i in range(4): nx, ny = x + dx[i], y + dy[i] if 0<=nx<n and 0<=ny<n and graph[nx][ny] == 1: graph[nx][ny] = 0 queue.append((nx,ny)) count += 1 return count count = 0 ans = [] for i in range(n): for j in range(n): if graph[i][j] == 1: ans.append(BFS(i,j)) count = 0 print(len(ans)) for a in sorted(ans): print(a) CODE REVIEW DFS와 BFS 두 방법으로 풀 수 있는 문제였다. BFS의 경우 queue을 이용해서 차례대로 구역 안의 1인 영역을 찾아내었고, DFS의 경우 재귀를 통해 찾아내었다.
백준 1004번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline eq = read().strip().split('-') ans = eq[0] if '+' in ans: ans = sum(map(int, ans.split('+'))) else: ans = int(ans) # 처리 for e in eq[1:]: if '+' in e: e = sum(map(int, e.split('+'))) ans -= int(e) print(ans) CODE REVIEW 한 정점과 원 사이의 거리를 활용한 기하학 문제. (시작점 - 원의중심 거리) = $l_{1}$ , (도착점 - 원의중심 거리) = $l_{2}$ , 반지름을 $r$ 이라 하면, ( $l_{1}$ - $r^2$ ) * ( $l_{2}$ - $r^2$ ) < 0 일 때 경계를 지나갈 수 밖에 없다. 이유: 중간값 정리 ( $l_{1}$ - $r^2$ ) > 0 이면 원 외부에 속함 ( $l_{1}$ - $r^2$ ) < 0 이면 원 내부에 속함 cf) 문제 번호가 천사(1004)라니 왠지 멋진걸?!