백준

[python] 백준 - 7569. 토마토

🤔문제 해결 1. BFS | silver1 2. 익은토마토(값이 1)를 찾아서 리스트에 담는다. 3. 3번의 리스트를 BFS를 실행한다. 4. 4번을 다 하고 나면 아직 익지 않은 토마토(0)가 있는 확인하고 있으면 -1을 답으로 출력 5. 없으면 가장 큰 값에서 -1한 값을 답으로 출력 💨 3차원 배열이라서 헷갈릴 수 있는 문제. 하지만 단순히 BFS로 풀면 된다. 💻소스 코드 from _collections import deque dx, dy, dz = [-1, 1, 0, 0, 0, 0], [0, 0, -1, 1, 0, 0], [0, 0, 0, 0, -1, 1] # 아래층 윗층 앞 뒤 좌 우 # BFS로 주변 토마토 익히기 def ripen(): while q: x, y, z = q.popleft()..

[python] 백준 - 1495. 기타리스트

🤔문제 해결 1. S1 | 다이나믹프로그래밍 2. 각각의 연주 차례에 가능한 볼륨을 저장하기 위해 2차원 리스트를 만든다. 3. 리스트를 설명하자면 맨 첫줄(i = 0)은 연주 시작전 단계이고 값이 0이 아니라 1인 부분은 내가 가지고 있는 볼륨이다. 현재 테스트케이스 예시(S=5)로 작성됐으므로 [0][5] = 1 이다. 4. 테스트케이스: 시작값 5, 최대값 10, 연주리스트 = [5, 3, 7] 5. 첫번째 연주를 하기 전에 볼륨을 바꾼다. 현재 볼륨은 5, 첫번째 연주 볼륨은 5 이므로 5+5 = 10, 5-5 = 0 으로 둘다 0보다 크고 10보다 작으므로 아래와 같이 저장할 수 있다. 6. 첫번째 연주를 하기 전에 볼륨을 바꾼다. 첫번째와 다른점은 현재 볼륨이 2가지(0과 10)이다. 먼저 현..

[python] 백준 - 11660. 구간 합 구하기 5

🤔문제 해결 S1 | DP (0,0) 부터 리스트의 모든 지점까지 각각의 합을 구한다. 2번을 수행하고 나면 아래와 같은 결과를 얻을 수 있다. 합을 누적한 리스트로 아래 그림처럼 구하고자 하는 영역을 구하고 필요없는 부분은 빼주면 된다. 여기서 많이 헷갈릴 수 있는데 문제는 1,1부터 시작하지만 우리는 0,0부터 시작한다. 또, 빼줘야하는 영역(빨간색) 부분은 두번 빼는 경우가 있기 때문에 다시 더해줄 영역(초록색)을 한번 더해준다. 여기서 끝이 아니다. x축이 처음부터 인경우와 y축이 처음부터인 경우, 둘 다 아닌경우 이 3가지 경우로 나눠서 풀어줘야한다. 💨 시간초과 때문에 힘들었던 문제... 💻소스 코드 import sys from itertools import accumulate # 누적 합을 ..

[python] 백준 - 1074. Z

🤔문제 해결 1. 재귀,분할정복 | S1 2. 모두 쪼개려고 하는경우 메모리초과 혹은 시간초과가 발생한다. 3. 내가 찾고자하는 행과 열이 포함된 박스만 찾아서 재귀함수를 실행시킨다. 4. 여기서 각 박스의 첫 숫자를 구한다. (1) 예를 들어 사이즈가 8인 박스의 첫숫자는 0이다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 박스를 쪼개면 (2) 각 박스의 첫 숫자는 0, 16, 32, 46 이다. (3) 왼쪽 위 박스는 그대로, 오른쪽 위 박스는 첫숫자에 (size//2)**2*1 값을 더해준다. (4) 왼쪽 아래 박스는 첫숫자에 (size//2)**2*2 값을, 오른쪽 아래 박스는 첫숫자에 (size//2)**2*3 값을 더해준다. 5. 박스의 크기가 2가 되면 찾고자 하는 행과 열을 찾..

[python] 백준 - 11048. 이동하기

🤔문제 해결 1. DP | silver1 2. 주어진 2차원 배열보다 한칸씩 더 큰 0으로 채워진 배열을 만든다. (한칸씩 더 많은 이유는 가장 윗줄과 가장 왼쪽줄도 비교해주기 위해서) 3. 현재 지점의 값(maze)과 그 점 이전의 값들(왼쪽, 왼쪽위, 위)중 큰 값(dp)을 더해서 (dp에) 값을 계속 쌓아 준다. 💨 다이나믹프로그래밍 문제. BFS로도 간단히 풀 수 있지만 시간초과가 난다. 💻소스 코드 N, M = map(int, input().split()) maze = [list(map(int, input().split())) for _ in range(N)] # 가장 윗줄과 가장 왼쪽줄도 비교를 해줘야 하기 때문에 한칸씩 더해서 만들어준다. dp = [[0] * (M + 1) for _ in ..

[python] 백준 - 10799. 쇠막대기

문제 해결 1. 스택을 활용한 문제. S3 2. '(' 가 나오면 막대기의 시작점이라 생각하고 stack 에 쌓는다. 3. ')' 이 나왔을 때 두가지의 경우 (1) 이전에 '(' 가 나온 경우: 쇠막대기가 아니라 레이저 이므로 잘라준다. (2) 이전에 ')' 가 나온 경우: 쇠막대기의 끝 부분 이다. 4. 레이저로 자른경우는 stack 에 쌓여있는 막대기만큼 count를 더해준다. 5. 쇠막대기의 끝부분이 나온경우 막대히 하나만큼 count를 더해준다. 🚗 소스 코드 bars = input() stack = [] cnt = 0 # '('를 막대기의 시작점으로 주고 '()' 이렇게 여는괄호와 닫는괄호가 연속으로 나오면 레이저로 취급한다. for i in range(len(bars)): if bars[i]..