Algorithm/etc111 [파이썬] 백준 1806 : 부분합 (골드4) [파이썬] 백준 1806 : 부분합 (골드4)https://www.acmicpc.net/problem/1806풀이방향성 생각$N=10^{6}$이라 $N^2$로는 불가능하다.투포인터를 통해서 한쪽 피벗에서 누적 합을 기록하며 목표값을 넘는 순간 값을 기록한다.전체코드N,goal = map(int,input().split())arr = list(map(int,input().split()))l,r = 0,0carr = 0answer = N+1while True: if carr >= goal: answer = min(answer,r-l) carr -= arr[l] l += 1 elif r == N: break else: carr +=.. 2024. 8. 2. [파이썬] 백준 11660 : 구간 합 구하기 5 (실버1) [파이썬] 백준 11660 : 구간 합 구하기 5 (실버1)https://www.acmicpc.net/problem/11660풀이방향성 생각2차원 누적합을 통해서 중복 영역 계산을 피해준다.전체코드import sysinput = lambda : sys.stdin.readline().rstrip()N,M = map(int,input().split())arr = [list(map(int,input().split())) for _ in range(N)]carr = [[0]*(N+1) for _ in range(N+1)]for i in range(1,N+1): for j in range(1,N+1): carr[i][j] = arr[i-1][j-1] + carr[i-1][j] + carr[i][.. 2024. 8. 2. [파이썬] 백준 30804 : 과일탕후루 (실버2) [파이썬] 백준 30804 : 과일탕후루 (실버2)https://www.acmicpc.net/problem/30804풀이방향성 생각각 시작지점마다 가능한 길이를 찾는다.$NlogN$이하로 해야하므로, 투포인터로 찾는다.각 과일 개수를 카운팅해줘야 하므로 딕셔너리 하나 사용해주기전체코드from collections import defaultdict as ddN = int(input())arr = list(map(int,input().split()))l,r,count = 0,0,0infos = dd(int)answer = 0while r 2: infos[arr[l]] -= 1 if infos[arr[l]] == 0: count -= 1 l += 1 .. 2024. 6. 11. [파이썬] 프로그래머스 : 유사 칸토어 비트열 (레벨3) [파이썬] 프로그래머스 : 유사 칸토어 비트열 (레벨3)https://school.programmers.co.kr/learn/courses/30/lessons/148652풀이방향성 생각범위가 $5^{20}$이라서 그냥은 못푼다.규칙 찾아서 푸는 분할정복 / 재귀 형태가 보인다.전체코드def solution(n,l,r): l -= 1 r -= 1 def dfs(n,l,r): # 0번째 칸토어 비트열 if n == 0: return 1 # n-1번째 칸토어 비트열의 길이 leng = 5**(n-1) count = 0 for i in range(5): # 11011 에서 0 부분은.. 2024. 6. 10. 이전 1 ··· 6 7 8 9 10 11 12 ··· 28 다음