DevYoon

link 🔗 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1️⃣ 먹은 대나무 수보다 많은 쪽으로만 이동하는 판다 2️⃣ 완탐으로 풀었다가 시간 초과 3️⃣ DFS + DP로 해결 import sys sys.setrecursionlimit(100000) dir = [(-1, 0), (1, 0), (0, -1), (0, 1)] n = int(input()) board = [list(map(int, input().split())) fo..

link 🔗 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 💫 가장 빨리 동생을 찾는 시간과 그 루트를 출력해주어야 한다. 💫 check 배열의 앞으로 들어갈 값의 위치에 현재 위치를 적어주었고, 역추적해주었다. from collections import deque def BFS(start, target): q = deque() q.append((start, 0)) # start, cnt Mincnt = 0 ..

link 🔗 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 💫 걸어서 갈 때보다 순간이동으로 갈 때 시간이 더 적게 걸림 ➡️ appendleft로 먼저 넣어주기 from collections import deque def BFS(start, target): q = deque() q.append((start, 0)) # start, cnt Mincnt = 0 check = [0]*100001 while q: ..

link 🔗 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net from collections import deque dir = [(-1, 0), (1, 0), (0, -1), (0, 1)] def setfire(): global fires temp = [] for y, x in fires: for i, j in dir: dy, dx = y+i, x+j if 0 불 나면 패스 for i, j in dir: dy, dx = ny+i, ..

link 🔗 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net ✏️ BFS 적록색약인 사람이 보았을 때와 적록색약이 아닌 사람이 보았을 때의 구역 수를 구하는 문제 적록색약일 때와 아닐 때를 구분하여 2개의 visit 배열과 count, BFS 함수를 만들어 주었다. 이중for문으로 visit에 체크가 되지 않았을 때 BFS를 돌리는데, rgBfs(적록색약 BFS)는 색이 R이거나 G일 때만 돌려주었다. 만약 현재 색상이 "B"라면 적록색..

link 🔗 https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net ✏️ DP 알고리즘 잘 풀리지 않아서 고전하다가, 잘 정리된 글(https://gsmesie692.tistory.com/113)을 발견하여 참고할 수 있었다. 2차원 배열로 문제를 해결하는데, 체력이 j보다 작으면 연락 불가능하므로 윗 배열의 값을 가져오고 체력이 j보다 크거나 같으면 새로운 값과 윗 배열의 값을 max 비교한다. 이때, j-power[i]는 앞서 연락을 취해 기쁨을..

link 🔗 https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 1️⃣ DP를 활용하는 문제 2️⃣ 증가할 때와 감소할 때를 나누어 배열을 만들어서 증가하는 상태에서는 증가배열에 더해주고, 감소하는 상태에서는 감소배열에 더해주었다. 3️⃣ 이전 값과 같은 상태에는 증가와 감소 양쪽 모두에 더해주었다. n = int(input()) arr = list(map(int, input().split())) isTrue = [1]*n isFalse = [1]*n..