jenlog

🚩 그래프이론, 그래프탐색, DFS, BFS thinking 상하좌우 다 탐색하면서 방문탐색하고 값이 1이면(==배추면) 카운팅 1 증가 ⭐ 처음에 그냥 풀었더니 런타임에러가 났다. 구글링 했더니 재귀 limit을 설정해주지 않아서 발생한 문제라고 한다. K(1 ≤ K ≤ 2500)의 범위가 엄청 커서 그런듯? 파이썬의 기본 재귀 한도가 (1000)이어서 재귀 깊이가 1000을 넘어갈 경우 모듈을 추가해줘야한다. 파이썬 최대 재귀 깊이 늘리는 모듈 import sys sys.setrecursionlimit(탐색하고자하는 깊이) 코드 import sys sys.setrecursionlimit(10000) def dfs(r,c): dr = [0, 1, 0, -1] dc = [1, 0, -1, 0] a[r][..

🚩 동적프로그래밍(DP) thinking 1. 시간초과 난 코드 피보나치 수열 코드와 동일하게 짜되, n == 0 or 1 인 경우 0과 1의 호출횟수를 카운트하도록 함수를 구성했다. output은 맞게 나왔지만 시간초과 뜸 2. success 😀 0호출횟수와 1호출횟수를 리스트로 만들어 피보나치 수열처럼 n-1, n-2의 호출횟수를 더하는 방식으로 코드를 짬. n = 8 인 경우, cnt_0 = [1, 0, 1, 1, 2, 3, 5, 8], cnt_1 = [0, 1, 1, 2, 3, 5, 8, 13]가 되어 n번째 원소를 출력하면 된다 코드 (pass) T = int(input()) for tc in range(T): N = int(input()) cnt_0 = [1, 0] # 0 호출횟수 기록하는 리..

🚩 분할정복, 재귀함수 thinking 처음에 4부분으로 쪼개고 카운팅했는데 output은 맞게 나왔으나 시간초과가 떴다. 시간초과를 줄이고자 마지막 else문의 범위를 나눴더니 패쓰됐다.. 코드 (pass) def divide(s_x, s_y, N): global cnt if N == 2: if s_x == r and s_y == c: # 1위치 print(cnt) return if s_x == r and s_y+1 == c: # 2위치 cnt += 1 print(cnt) return if s_x+1 == r and s_y == c: # 3위치 cnt += 2 print(cnt) return if s_x+1 == r and s_y+1 == c: # 4위치 cnt += 3 print(cnt) return..

🚩 분할정복 thinking N이 1이 될때까지 쪼개면서 체킹하자 그럼 어케 쪼갤 것이냐? → 시작점의 좌표를 구해서 종이크기만큼 range를 설정한 후, 범위 체킹하자. 반복문 돌리면서 체킹하다 색깔이 전부 같으면 거기는 stop하고 white or blue 개수에 카운팅해서 경우의 수를 줄이자 코드 def divide(s_x,s_y,N): global cnt_w, cnt_b if N == 1 and a[s_x][s_y] == 0: cnt_w += 1 return if N == 1 and a[s_x][s_y] == 1: cnt_b += 1 return flag_w = 0 flag_b = 0 for i in range(s_x, s_x+N): for j in range(s_y, s_y+N): if flag..

🚩 큐(queue) thinking 포인트는 deque 모듈 을 사용하는 것이다!!!!! 그냥 pop(0)으로 풀면 시간초과 남 deque 사용하는 이유 : popleft의 시간차이 때문에 list의 경우 pop()으로 마지막 값을 꺼내는 경우 O(1) (일정한 시간) 시간이 걸리는데, pop(0)으로 가장 앞단에 값을 꺼낼때는 list 크기에 따라 읽어 오는 시간이 달라져 O(n) 시간이 걸림. 하지만 deque를 사용할 경우에, popleft()를 사용하면 리스트의 pop(0)과 같은 기능을 주면서 걸리는 시간은 O(1)이 걸린다. 코드 (pass) from collections import deque N = int(input()) queue = deque() for i in range(1, N+1)..