Jang's coding blog

*투 포인터 특징 말 그대로 시작점, 끝점 두개의 위치를 지정하여 리스트를 탐색하는 방법 O(n)의 시간복잡도를 가지고있음 *투 포인터의 이동 원칙 sum > N : sum-=start; start++; sum < N : end++; sum+=end sum == N: sum+=end; cnt++ *예제 문제(백준 2018 수들의 합 5) # 백준 2018번 문제검색 링크 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. www.acmicpc.net *문제 코드 N=int(input()) start=1 en..

*DFS (깊이 우선 정렬) 그래프 완전 탐색을 위한 구현 재귀함수, 스택 자료구조로 구현가능 시간복잡도 = O(V+E) 여기서 V=노트 수, E= 간선 수 #백준 11724 DFS예시 코드 import sys sys.setrecursionlimit(10000) input= sys.stdin.readline def dfs(v): visited[v]=True for i in graph[v]: if not visited[i]: dfs(i) N,M = map(int, input().split()) graph=[[] for _ in range(N+1)] visited=[False]*(N+1) for _ in range(M): u,v= map(int, input().split()) graph[u].append(v..

*구간 합 알고리즘이 필요한 이유 구간마다 합을 매번 계산하게 되면 계산해야하는 양이 많아지면 시간초과가 발생할 수 있다. 실제 코딩테스트에서 사용 빈도가 많이 높다 *구현 원리 합배열을 미리 만들어 놓으면 큰 구간에서 작은 구간을 빼면 두 구간 사이의 합이 나옴을 이용 ex)1번부터 3번까지의 합은 sum[3]-sum[1]임을 이용 *구현 방법 입력받은 숫자의 합배열을 생성한다 합배열에서의 특정 구간을 값을 S[j]-S[i-1]로 계산한다. *구현 코드 #예시문제 백준 11659번 import sys input =sys.stdin.readline N,M= map(int ,input().split()) #숫자의 수 N, 구간 합 출력 수 M 입력 numbers=list(map(int, input().sp..