Algorithm Problem/Python

[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] 백준 - 2251. 물통

🤔문제 해결 1. S1 | 그래프 이론, 그래프 탐색, BFS 2. 물통이 3개지만 물의 총량이 고정이기 때문에 a,b 두 물통만 체크하면 된다. c는 저절로 정해짐. 3. visited 리스트를 2중 리스트로 작성한다.( 변수가 2개이기 때문 ) 4. 처음 0,0을 넣고 BFS를 한다. (1) a 물통이 0일 때 c 물통의 양을 답리스트에 넣어준다. (2) a -> b, a -> c, b -> a, b -> c, c -> a, c -> b 6가지를 모두 탐색한다. (3) 조건에 맞다면 물을 나누고 계속 탐색한다. 5. 답을 출력조건에 맞게 출력하면 끝. 💨 변수를 2개만 정해서 visited를 2중리스트로 하는 것과 물을 옮기는 경우를 생각해보자 💻소스 코드 from collections import ..

[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 # 누적 합을 ..

[html] 공백 문자, 띄어쓰기

공백문자 가져가세요 "ㅤ" 🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻🔻 ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ 🔺🔺🔺🔺🔺🔺🔺🔺🔺🔺🔺🔺🔺 ㅤ ㅤ ㅤ

[python] 프로그래머스 - 기둥과 보 설치(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 Lv3 설치된 구조물의 정보를 리스트에 쌓는다. ex) 설치된_리스트: [(좌표, 좌표, 구조물), ..., (좌표, 좌표, 구조물)] | x,y,(기둥or보) 이 설치된 구조물 리스트를 for문을 돌며 이 구조물들의 설치가 조건에 맞는 지 체크한다. def check() 구조물 설치일 경우 일단 설치한다. 큰 3번을 체크한다. 구조물들이 조건에 맞지 않으면 추가한 것을 삭제한다. 구조물 삭제일 경우 일다 삭제한다. 3번을 체크한다. 구조물들이 조건에 맞지 않으면 삭제한 것을 추가한다. 잘 정렬해서 답을 출력한다.!!!!! 💨 여기서 set() 을쓰는 이유는 if a in list: 같은 경우 때문. 리스트로 탐색하는 경우는 O(n) 이지만 셋으로 탐색하는 경우는 O(1) 이다. 마지막에 답..