jenlog

🚩 분할정복, 재귀함수 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)..

🚩 DFS, 백트래킹, 재귀함수, 스택 thinking for문을 돌면서 1부터 리스트에 넣고 M개가 다 쌓이면 출력하도록 작성함. 어차피 for문이 숫자 순서대로 돌기 때문에 수열의 순서는 굳이 고려 안함. 이미 방문했으면 건너뛰고, 방문 안했으면 방문 체크 한 후, 출력리스트에 넣고 다음 함수를 호출. 코드1 방문체크로 푼 풀이 def DFS(): if len(s) == M: print(*s) return for i in range(1, N+1): if visited[i]: # 이미 방문했으면 건너뜀 continue # 방문 안했으면 방문체크 후, 출력 리스트에 넣음 visited[i] = True s.append(i) DFS() # 함수 다시 호출 s.pop() # 원상복귀 과정 필요 visited..

🚩 브루트포스 thinking W로 시작하는 경우 ◾ WBWBWBWB -> W로 시작했는데 첫번째칸이 W가 아니면 다시 칠해야함 ◾ BWBWBWBW -> W로 시작했는데 두번째칸이 B가 아니면 다시 칠해야함 B로 시작하는 경우 ◾ BWBWBWBW -> B로 시작했는데 첫번째칸이 B가 아니면 다시 칠해야함 ◾ WBWBWBWB -> B로 시작했는데 두번째칸이 W가 아니면 다시 칠해야함 ⇒ WBWB or BWBW가 번갈아가면서 나오니까 행+열 인덱스의 합을 2로 나눈 나머지로 생각 (0101 이런식으로) 코드 N, M = map(int, input().split()) # N:행 M:열 a = [list(input()) for _ in range(N)] res = [] # 8x8 체스판 탐색 for i in r..