정보의 바다 헤엄치기

누적합, 구간합배열의 구간 합을 구할 때 해당 구간을 순회하면서 구하면 최대 O(n)의 시간이 걸리지만, 누적합 배열을 미리 만들어 놓으면 O(1)의 시간 복잡도로 구할 수 있다.index 0 1 2 3 4 nums = [1, 2, 3, 4, 5] acc = [0, 1, 3, 6, 10, 15] nums[i]부터 nums[j]까지의 합 = acc[j+1] - acc[i]누적합 배열 acc[i+1]는 nums 배열의 0번 값부터 i번 값까지의 합을 의미한다.따라서 nums 배열의 i번째 값부터 j번째 값까지의 합은 0번 ~ j번 값까지의 합인 acc[j+1]에서 0번 ~ i-1번 값까지의 합인 acc[i]를 뺀 값이 된다.누적합과 관련한 백준 문제https://www.acmicpc.net/problem/2..

✏️문제 링크https://www.acmicpc.net/problem/19236문제 풀이델타 이동 구현 + DFS로 풀었다.문제의 요구사항에서 물고기 이동 단계와 상어 이동 단계가 반복되므로 각 단계를 함수로 만들었다.상어 이동 단계는 상어가 이동 가능한 위치가 여러 개 있을 수 있고 모든 경우의 수를 탐색해야 하므로 DFS를 적용하여 재귀적으로 탐색했다.제출 코드import sys import copy input = sys.stdin.readline drc = [(-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)] arr = [[0] * 4 for _ in range(4)] # 물고기 배치. (fish, direction): 물고기..

✏️문제 링크 https://www.acmicpc.net/problem/162361년 전 처음으로 백준 사이트에 가입할 때 이 문제를 보고 제목이 귀여워서 아이디를 baby_shark로 지었었다.닉값을 하기 위해 아기 상어를 풀고 싶었지만 귀여운 제목과는 달리 골드 난이도의 문제였고, 당시에 나는 프로그래밍 공부를 시작하는 단계였기 때문에 BFS가 뭔지 몰라서 풀 수 없었다😂이 문제를 풀고싶어서 알고리즘을 열심히 공부한 것도 일정 부분 있지 않을까? 아무튼 골드 문제 중에서 처음으로 도전했던 문제이고, 기념비 삼아 첫 게시물로 올려본다....그런데 1년이 지나고 코드를 다시 보니 개선될 여지가 많아서 성능 및 가독성을 향상시킨 v2 코드를 새로 작성하였다.1년 전 풀이N = int(input()) fis..