Algorithm Problem/Python

[python] 프로그래머스 - 블록 이동하기(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 1. Lv3 | BFS 심화 2. BFS를 돌릴 q와 방문체크할 visited리스트를 준비한다. (1) q는 deque를 이용. 로봇의 좌표 4가지 (x1,y1,x2,y2)와 현재의 거리 d 를 넣는다. (2) visited에는 로봇의 좌표만 넣는다. 3. BFS를 돌린다. (1) 먼저 끝점에 도달했다면 바로 멈춰주고 거리를 출력한다. (2) 그렇지 않다면 로봇이 세로인경우와 가로인경우를 나누고, 상하좌우 움직일 수 있는 지 체크한다. (3) 로봇이 세로인 경우 오른쪽 이동이 가능하면 오른쪽 회전도 가능하다. 마찬가지로 왼쪽이동이 가능하면 왼쪽으로 회전도 가능하다. (4) 가로도 마찬가지 (5) 이동이나 회전이 가능하면 visited리스트를 확인해 방문한적이 없으면 q와 visited에 넣어..

[python] 프로그래머스 - 가사 검색(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 1. Lv4... | 트라이 자료구조 2. 트라이 자료구조를 구성한다.( 쉽게 말하자면 dict안에 dict안에 dict안에 dict.... 구조 ) 대략 위의 그림과 같은 형태로 구성하게 된다. 맨 앞의 숫자는 길이가 5인 단어, 6인 단어 다음 f로 시작하는 단어 4개, r로시작하는 단어 4개, o로 시작하는 단어3개, d로 시작하는 단어 1개... 가 있다는 의미 4. 찾는다... 만약 'fro??' 을 찾는다고 하자 (1) 길이가 5 인 곳으로 들어간다 (2) 거기서 f 로 들어간다. cnt에는 f로 시작하는 단어가 4개있다는 것을 저장한다. (3) r 로 들어간다. cnt에는 r로 시작하는 단어가 4개 있다는 것을 저장한다. (4) o 로 들어간다. cnt에는 o로 시작하는 단어가 ..

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