머신러닝 숄구

특정 목적지의 좌표에서부터 출발해서 행이 0인 라인에 도착할 때까지 이동하면 되는 문제 이동은 오른쪽 , 왼쪽, 위 순으로 하도록 한다 - 사다리 타기는 위 보다는 좌우 이동이 먼저이다 다시 뒤로 돌아가는 경우를 생각하면 안되니 중복을 방지해야 한다 BFS 방법으로 풀어보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 if __name__=='__main__': game = [list(map(int, input().split())) for _ in range(10)] dx = [0, 0, -1] dy = [1, -1, 0] queue = deque() for i in range(10): if game[9][i] == 2: de..

지금까지 BFS 문제에서는 출발점을 격자판의 좌상단으로 해도 무리가 없었다면, 이 문제에서는 익은 토마토가 random한 위치에 주어지고, 익은 토마토를 기점으로 다른 토마토가 익는 상황이므로 익은 토마토들의 위치를 queue에 먼저 쌓아줘야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 import sys from collections import deque # sys.stdin=open('input', 'r') sys.setrecursionlimit(10**6) # 10**6 정도의 시간 limit을 주면 ..

먼저, BFS로 풀어보았다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 import sys from collections import deque # sys.stdin=open('input', 'r') sys.setrecursionlimit(10**6) # 10**6 정도의 시간 limit을 주면 이걸 넘어가면 재귀를 끝낸다 # 백준사이트 같은 곳 가서 채점 받을 때 필요 if __name__=='__main__': n = int(input()) island = [list(map(int, input().split())) for ..

고민했던 점 1 : 하나의 그룹 안에서 다 돌고 이제 더이상 갈 곳이 없을 때, 다음 그룹으로 어떻게 이동할 것인가? 해결 : 이미 방문한 곳은 0으로 바꾸어 놓을 것이니, 격자를 이중 for문으로 하나하나 돌리면서 아직 1번으로 표시된 곳에서부터 DFS를 돌리면 된다 고민했던 점 2 : 집을 어떻게 카운팅 할 것인가? 해결 : 이중 for문 안에서 DFS 시작 전에 cnt = 0으로 해주어, for 문 돌면서 각 그룹당 cnt를 진행할 수 있게끔 해준다. 카운팅 결과는 리스트 안에다 차곡차곡 append 해준다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 def DF..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 def DFS(x, y): global cnt if x==y==6: cnt+=1 else: for i in range(4): x_ = x + dx[i] y_ = y + dy[i] if 0

1. Bottom Up 방식으로 풀이 가장 작은 부분 부터 직관적으로 풀어보자. 이 후 점화식을 이용하여 점차 큰 문제를 풀어나간다. 1 2 3 4 5 6 7 8 9 10 11 12 import sys sys.stdin=open('input', 'r') n = int(input()) arr = [0] * (n+1) arr[1]=1 arr[2]=2 for i in range(3, n+1): arr[i] = arr[i-1] + arr[i-2] print(arr[n]) Colored by Color Scripter cs 2. Top Down 방식으로 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def DFS(len): if memo[len] > 0: return memo[len] if le..

동적 계획법이란 - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다 동적 계획법을 적용하려면 다음 두 가지 속성을 만족시켜야 하는데, 부분 반복 문제 (Overlapping Subproblem) - 대표적으로 피보나치 수열의 경우 계속해서 같은 부분 문제가 여러번 재사용되거나 재귀 알고리즘을 통해 해결되는 문제를 가지고 있다. 문제: n 번째 피보나치 수 구하기 | 부분문제: n-1번째 + n-2번째 피보나치 수 구하기 문제: n-1번째 피보나치 수 구하기 | 부분문제: n-2번째 + n-3번째 피보나치 수 구하기 최적 부분 구조 (Optimal Substructure) - 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다는 것. 피보나지 수열에..

병합 정렬 설명 - 후위순회 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 def Dsort(lt, rt): if lt

BFS 는 한번만에 가는 경우, 두번만에 가는 경우...에 대한 기록을 할 리스트가 필요하다 BFS 는 되돌아가는 경우는 없기 때문에, 그 vertex를 지나왔는지 아닌지에 대한 기록을 할 리스트가 필요하다 - 이 문제에서는 격자판 상에서 갈 수 있는 곳이 0, 없는 곳이 1 로 표시된 7x7 행렬이 이미 존재하기 때문에, 이 격자판을 활용해서 문제를 풀면 된다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import sys from collections import deque # sys.stdin = open('input', 'r') board = [list(map(int, input().split..

처음에 풀이 방식을 절반 먼저 사과 개수 계산하고, 나머지 거꾸로 시작해서 절반 전까지 더해서 계산하는 방법으로 풀이했었다. 해설을 듣고 나니, 무릎을 탁! 쳤다... 가운데 좌표점을 시작으로 십자 모양으로 뻗어나가면 되는 문제 1234567891011121314151617181920212223242526272829303132import sysfrom collections import deque # sys.stdin=open('input', 'r')n = int(input())apple = [list(map(int, input().split())) for _ in range(n)]check = [[0]*n for _ in range(n)]dx = [-1, 0, 1, 0]dy = [0, 1, 0, -1] ..