파이썬 알고리즘 문제풀이/누적합3 BOJ 16139 인간-컴퓨터 상호작용 https://www.acmicpc.net/problem/16139 진짜로 푸는데 개오랜 시간이 걸렸다.. 일반적인 누적합 문제와 다른 점은 문자별로 다른 누적합 리스트를 가지고 있어야 한다는 것이다. 예를들어 그냥 단순 특정구간 덧셈 계산을 했을때는 일정구간 자연수에 대한 누적합 리스트가필요했지만 이건 문자 별로 필요한 문제이다. 이문제가 골치아팠다. 그럼 리스트 26개를 만들어야되는데, 동적으로 리스트명을 만들어 안에 append시킬 수 있을까? 라는 생각을 했다. 그런데 동적 변수 할당은 있어도 동적으로 리스트를 만드는 것은 존재하지 않았다. 이중리스트를 만들어 인덱스로 접근하는 발상을 생각해내는데 오랜 시간이 걸렸다.. 일단 for 문으로 26개의 0을 원소로하는 리스트를 요소로 가지는 이중 리스.. 2023. 4. 8. BOJ 2559 수열 - python 이런 문제.. 처음의 풀이. from sys import stdin def main(): def input(): return stdin.readline().rstrip() N,K = map(int,input().split()) ls1= list(map(int,input().split())) ls2 = [] sum1 = 0 for i in range(N-K+1): for j in range(K): sum1 += ls1[i+j] ls2.append(sum1) sum1 = 0 print(max(ls2)) if __name__ == "__main__": main() 하지만 시간 복잡도상 N*K 최악의 경우 N ^2 이기 때문에 입력값이 100000인 이상 시간 초과를 피할 수 없다.. 다음 풀이. from sy.. 2023. 4. 7. BOJ 11659 - 구간 합 구하기 4 백준에서 처음 풀어보는 문제.. 일단 ide가 없어 굉장히 러프하고, 발상보다 시간복잡도, 알고리즘을 고려해야하는 문제이다. 언뜻 보면 굉장히 간단한 문제처럼 보인다. 하지만 제한사항에 n,m이 100,000 과 100,000 최악의 경우 시간복잡도가 오버될 수 있음을 볼 수 있다. 누적합을 배우기전 나의 답. N, M = input().split() ls1 = list(map(int,input().split())) ls2 = [] sum1 = 0 for k in range(int(M)): i,j = input().split() sum1 = sum(ls1[int(i)-1:int(j)]) ls2.append(sum1) for i in ls2: print(i) 일단 백준이 처음이라 그런지 input에 대해 .. 2023. 4. 6. 이전 1 다음
