파이썬

[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] heapq(힙큐, 우선순위큐)

📗heapq란? 간단하게 리스트내에서 가장 작은 값이 맨처음위치(인덱스 0)애 오게 해주는 내장 모듈 우선순위 큐라고 알면 쉽다. 🔵 시작하기 import heapq 🔵 선언하기 보통 리스트를 선언하는 것처럼 만든다. heap_list = [] 🔵 원소 추가하기 ( heapq.heappush(리스트, 값 )) - 아래 보이는 것 처럼 가장 작은 값이 맨 처음 위치에 왔다. 시간복잡도 O(logn) heapq.heappush(heap_list, 5) heapq.heappush(heap_list, 10) heapq.heappush(heap_list, 99) heapq.heappush(heap_list, 2) print(heap_list) # [2, 5, 99, 10] 🔵 원소 삭제하기 ( heapq.heap..

[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] SWEA - 4261. 빠른 휴대전화 키패드

🤔문제 해결 1. D5 | 이게 왜 D5? 2. 키패드 리스트나 딕셔너리를 만든다. 3. 각각의 단어들을 한글자 한글자 체크한다. 4. 단어 안의 한글자가 누른 키패드의 문자 안에 포함되어 있지 않으면 체크를 멈추고 5. 모두 통과하면 카운트를 세어준다. 💨 D5라서 재귀함수를 통해 가능한 모든 단어를 구하고 포함관계를 구해줬는데 틀렸다. 혹시나 해서 단순하게 접근했더니 쉽게 풀렸다. D5가 아닌거 같다... 💻소스 코드 keypad = { '2': ['a', 'b', 'c'], '3': ['d', 'e', 'f'], '4': ['g', 'h', 'i'], '5': ['j', 'k', 'l'], '6': ['m', 'n', 'o'], '7': ['p', 'q', 'r', 's'], '8': ['t', '..