Algorithm Problem

[python] 프로그래머스 - 경주로 건설 (2020 카카오 인턴십)

🤔문제 해결 1. visited = {} 현재위치 x, y, 현재위치에서 바로보고 있는 방향 을 키값으로, 현재위치까지 오는데 드는 비용을 벨류값으로 딕셔너리를 만든다. ( 0, 1, 2, 3 | 상 하 좌 우 ) 2. q = deque() visited와 같은 값을 가지고 BFS를 실행하기 위해 사용. ( 위치 x,y, 바라보는 방향 k, 비용 ) 3. BFS를 돌며 현재 방향 d 와 앞으로의 방향 k를 비교하여 도로건설 비용을 책정한다. 4. 끝에 도달했을 때 최소비용을 출력한다. ( 끝에 도달하는 경우가 여러번이므로 끝날 때 까지 비교해준다. ) 💨 너무 어려웠던 문제... 몇시간동안 푼거같다. 바라보는 방향을 저장하고 비교하는게 중요!! 💻소스 코드 from collections import de..

[python] 프로그래머스 - 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 1. lv3 | 완전탐색? 2. 자물쇠 주위를 1과0이 아닌 다른 숫자로 채워준다. ( 열쇠의 길이 - 1 만큼 ) 3. 열쇠를 새롭게 만들어진 자물쇠 위에 놓고 2중 for문으로 전부 겹쳐가며 탐색한다. ( 자물쇠를 열쇠의 크기만큼 잘라서 열쇠와 자물쇠를 비교) ( 노란색: 원래자물쇠, 초록색: 새롭게 채워놓은 빈공간, 파란색: 열쇠 4. 열소의 돌기(1)와 자물쇠의 구멍(0)이 만나면 카운트 +1, 열쇠의 돌기(1)와 자물쇠의 돌기(1)가 만나면 탈락, 열쇠의 구멍(0)과 자물쇠의 구멍(0)이 만나면 탈락, 자물쇠의 모든 구멍(0)이 열쇠의 돌기(1)로 채워져야 한다. (즉, 파란영역 안의 자물쇠가 모든 구멍(0)을 가지고 있어야한다) 5. 자물쇠 전체의 구멍의 숫자와 열쇠의 돌기가 자물..

[python] 백준 - 1309. 동물원

🤔문제 해결 1. S1 | DP 2. 사자가 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 오른쪽에 있는 경우의 리스트를 만든다. 3. i번째에서 i-1번째에 사자의 상태에 따라 i번째의 경우의 수가 결정된다. (1) i번째에 사자가 없는 경우는 i-1번째에 사자가 왼쪽, 오른쪽 그리고 없어도 된다. (2) i번째에 사자가 왼쪽에 있는 경우는 i-1번째에 사자가 오른쪽에 있는 경우와 없는 경우만 가능하다. (i-1번째에 왼쪽에 있으면 i번째에서는 왼쪽에 있을 수 없다) (3) 오른쪽도 마찬가지 4. 경우의 수를 점차 더해나가면서 마지막 경우의 수를 다 더해준다. 💨 마지막에만 9901로 나누려고하면 메모리초과가 발생한다. 값을 쌓을 때 부터 나눠주면서 하자. 💻소스 코드 if __name__ == "__..

[python] 백준 - 1992. 쿼드트리

🤔문제 해결 1. 분할정복 | S1 2. 재귀함수를 이용했다 3. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 를 차례로 쪼개서 모두 1이나 0으로 이루어져 있는지 확인하고 4. 아닐 경우 다시 쪼개서 확인한다. 💨 맨 처음 배열이 모두 1인지 0인지 확인을 안해서 잠시 고민을 했던 문제!!! 답이 0이나 1이 될 수 있다 문제를 이해하는 것은 쉬우나 재귀함수를 사용했기 때문에 답을 출력하는게 힘들 수 있다. 맨 처음 함수에 들어왔다는 것은 하나의 묶음을 생성해야 하기 때문에 괄호를 사용해서 적절히 묶어준다.( 시작할 때 끝날 때) 💻소스 코드 from itertools import chain # 2중 리스트를 단일 리스트로 바꾸기 위해서 chain 함수 사용했음 def compression(lst)..

[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 ..