투 포인터 2개의 포인터로 알고리즘의 시간 복잡도를 최적화함 [문제 006] 연속된 자연수의 합 구하기 N의 최댓값이 10,000,000으로 매우 크므로 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n) 시간 복잡도 알고리즘을 사용해야 함 ⇒ 이런 경우 자주 사용하는 방법이 투 포인터 💡 투 포인터 이동 법칙 sum > N: sum = sum-start_index; start_index++; sum < N: end_index++; sum = sum+end_index; sum = N: end_index++; sum = sum+end_index; count++; start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것 end_index를..

12주차 일정 10/23 - 10/27 미니프로젝트 5차 10/23 - 10/27 미니프로젝트 5차 미프라는 무한 굴레에 빠진 지 2주째.. 다음 주에 바로 6차 미프가 시작된답니다.. 아 즐겁다.. 하하호호^^ 5차 미니프로젝트 중 처음 이틀은 AICE 시험 대비 강의가 있었다. 샘플 문항만 봤을 땐 이 정도면 할 만하지! 싶다가도 이런저런 제약사항들이 꽤 많아서 실제 시험은 어떨지 직접 문제를 마주쳐야만 알 수 있을 거 같은 느낌.. 이번 팀은 유독 처음 함께 팀을 하는 분들이 많았는데 팀원분들과 서로 코드 리뷰를 하면서 새로 알게 된 함수들도 있었어서 나름 쏠쏠한 재미가 있었다! # include: 포함할 type df.select_dtypes(include=[float,bool]) # exclud..

11주차 일정 10/16 - 10/20 미니프로젝트 4차 10/16 - 10/20 미니프로젝트 4차 제목: 절망스러웠던 4차 미프 사유: 미프를 해내기엔 턱 없이 부족한 내 자신 4차 미니프로젝트 중 이번 5일 동안은 문의 유형 자동 분류 모델을 만드는 것이 목표였다. 자연어 처리.. 난 배운 게 없는데.. 내가 해낼 수 있을까..?라는 절망감과 함께 시작! 하자마자 이게 뭐야!!!!!! 속으로 냅다 비명 자연어 처리 경험이 거의 전무한 내가 문제겠지만 진짜 1000000번쯤 소리를 지르고 싶었음.. 사실 머신러닝이던 딥러닝이던 모델링은 거의 정해진 틀이 있다 보니 모델 만드는 건 비교적 쉽지만(튜닝은 나중) 전처리가 진짜 얼마나 중요한지 또 또 깨닫는 시간.. 역시 공부는 실전이라고 프로젝트하면서 직접..

구간 합 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 구간 합의 핵심 이론 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 함 합 배열 S 정의 S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i] # S[i]는 A[0]부터 A[i]까지의 합 인덱스 0 1 2 3 4 5 배열 A 15 13 10 7 3 12 합 배열 S 15 28 38 45 48 60 합 배열 S를 만드는 공식 S[i] = S[i-1] + A[i] i에서 j까지 구간 합을 구하는 공식 S[j] - S[i-1] ex) A[2]부터 A[5]까지의 합 = A[0]부터 A[5]까지의 합 - A[0]부터 A[1]까지의 합 = S[5] - S[1] [문제 003] 구간 합 구하..

10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 코드 n, m = map(int, input().split()) # n개의 수, M으로 나누기 A = list(map(int, input().split())) # n개의 수로 이루어진 원본 배열 S = [] # 합 배열 M = [] # 합 배열 S를 M으로 나눈 나머지 answer = 0 # M으로 나눠지는 (i, j) 쌍의 개수 temp = 0 for i in A: temp += i S.append(temp) # ..

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 코드 import sys input = sys.stdin.readline n, m = map(int, input().split()) # 표의 크기, 합을 구해야 하는 횟수 A = [] # NxN 리스트 for _ in range(n): A.append(list(map(int, input().split()))) # 합 배열 D 구하기 D = [[0] * (n+1) for _ in range(n+1)] # DP 테이블 for..