목록알고리즘 (72)
짱이 될거야
코드의 중복을 막기 위해서, bfs 함수의 인자로 현재 위치 뿐만 아니라 색도 함께 전달했다. 방문하지 않았으면서 색이 일치하는 것들만 counting 하고, 마지막에 제곱해서 결괏값에 더한다. from collections import deque import sys input = sys.stdin.readline def bfs(si, sj, color): army = 0 q = deque() q.append((si, sj)) visited[si][sj] = 1 while q: si, sj = q.popleft() army += 1 for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]: ni, nj = si+di, sj+dj if 0
1. 에러 코드 0부터 10000까지의 수에 대해 소수 여부를 판단할 수 있는 배열을 만든다. 숫자 2의 경우 2의 배수인 4, 6, 8, ... 은 소수가 아니므로 이것을 코드로 구현했다. 이대로 코드를 제출하면 틀리는데, while 문 때문인 것 같다. 2, 3 등 원래 소수인 숫자는 배열에 체크하면 안되고, 그 다음 배수부터 체크해야 하기 때문에 while문을 돌리기 전 수를 2배 해주고 그 수가 10000이하일 때까지만 돌린다. 하지만 그렇게 하면 2~5000까지만 배수로 소수 체크를 하는 것이기 때문에 5001 부터는 체크되지 않는다. 따라서 while num
이 문제는 Memoization 유형을 풀 때처럼 풀었다. 우선 1000의 크기를 가진 리스트를 만들고, 그 안에 수열을 미리 넣어두었다. 이후 입력받는 숫자 A, B 범위에 속하는 리스트 값들을 더해서 출력한다. A, B = map(int, input().split()) arr = [0] * 1000 cnt = 1 # 현재 숫자(1, 2, 3...) tot = 1 # 배열 인덱스 while tot 1000: break cnt += 1 print(sum(arr[A-1:B]))
1. 메모리 초과 이번 문제는 이해하기는 쉬운데, 구현 도중 시간 초과 혹은 메모리 초과 조건이 까다로웠다. 아래처럼 했을 때 메모리 초과가 나왔는데, 각 셀에 대해 bfs를 돌릴 때 조건이 visited[i][j] = 1이면서 arr[i][j] != '#'일 때로 설정해뒀기 때문에 그런 것 같다. # 메모리 초과 from collections import deque import sys input = sys.stdin.readline def bfs(si, sj): global sheep, wolf q = deque() q.append((si, sj)) n_sheep, n_wolf = 0, 0 while q: si, sj = q.popleft() if not visited[si][sj] and arr[si..
from collections import deque def bfs(v): q = deque() q.append(v) while q: v = q.popleft() if v == K: return visited[v] for i in (v-1, v+1, 2*v): if 0
예제 입력 중 0의 경우 첫 번째 시행하자마자 결과가 자기 자신이 된다. 그렇기 때문에 while문을 실행하기 전 먼저 cycle을 하나 돌려준다. 이 문제의 경우, 각 자리수를 더하는 것 자체는 어렵지 않지만 cycle을 처음 한 번 실행시켜 준다는 것과 cycle을 돌릴 때마다 직전 값을 따로 저장해둘 필요가 있다는 게 어려웠다. num = int(input()) digit_tot = 0# 각 자리수 더한 값 first_num = num# 입력값 옮겨두기 result = 10 * (num % 10)# result = 기존 값의 십의 자리 수 if num < 10: digit_tot = num else: while num: digit_tot += num % 10 num //= 10 result += (..