정신차려 하프물범 정신차려 하프물범

누적합은, 보통 이중 반복문(배열 문제)으로 시간 초과가 될때 구간합을 O(1)로 줄여주는 경우가 많아서, 종종 쓰인다. 누적합 사용 유형구간 합 구하기: 배열에서 여러 번 특정 범위의 합을 구하는 경우, 배열의 누적합을 미리 계산해 두면 각 구간의 합을 빠르게 구할 수 있습니다.예시: 주어진 배열에서 여러 번 "i번째 원소부터 j번째 원소까지의 합"을 구하는 문제.최소/최대 구간 합: 배열에서 특정 길이의 구간 중 가장 큰 합 또는 가장 작은 합을 구하는 문제에서, 누적합을 활용하면 구간 합을 효율적으로 계산할 수 있습니다.예시: "배열의 부분 배열 중 합이 가장 큰 구간을 찾아라"와 같은 문제.차이 배열: 누적합을 활용하여 배열에서 구간별로 값을 추가하거나 뺄 때, 전체 배열을 매번 갱신하지 않고도 ..

Dequestruct Deque { private var array: [T?] private var head: Int private var tail: Int private var capacity: Int init(capacity: Int) { self.capacity = max(1, capacity) self.array = Array(repeating: nil, count: self.capacity) self.head = 0 self.tail = 0 } var isEmpty: Bool { return head == tail } var isFull: Bool { ..

TreeMap (SortedDict)TreeMap은 균형잡힌 이진트리 구조로 데이터를 관리해주는 자료구조 이다.- 각 노드는 (key, value) 쌍 형태로 들어가고, key를 기준으로 노드의 위치를 결정한다- 따라서 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부 O(logN)이다.- TreeMap 자료구조는 built-in function이 없다- sortedcontainers 라는 외부 라이브러리가 필요from sortedcontainers import SortedDict차이점1. 선언sd = SortedDict()2. keys(), items()와 같이 저장된 데이터를 순회할 때, 자동으로 key 기준으로 오름차순 순회 된다.대체로 "오름차순" dictionary 출력이 필요한 문제에 쓰이..

리스트의 주요 연산 시간 복잡도 입력 순서가 유지, 내부적으로는 동적 배열로 구현되어 있다. 연산 시간복잡도 설명 len(a) O(1) 전체 요소의 개수를 리턴한다. a[i] O(1) 인덱스 i의 요소를 가져온다. a[i:j] O(k) i부터 j까지 슬라이스의 길이만큼 k개의 요소를 가져온다. 이 경우 객체 k개에 대한 조회가 필요하므로 O(k)이다. elem in a O(n) elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 n만큼 시간이 소요된다. a.count(elem) O(n) elem 요소의 개수를 리턴한다. a.index(elem) O(n) elem 요소의 인덱스를 리턴한다. a.append(elem) O(1) 리스트 마지막에 elem 요소를 추가한다. a.pop() O(1) 리스..

서로소 집합 서로소 집합(Disjoint Sets)은 공통 원소가 없는 두 집합을 의미한다. 이때 집합 간의 관계를 파악하기 위해 서로소 집합 알고리즘을 사용할 수 있는데, 서로소 집합 알고리즘은 union-find 연산으로 구성되며, 모든 노드는 자신이 속한 집합을 찾을 때 루트 노드를 재귀적으로 찾는다. (즉, 루트 노드가 같으면 같은 집합으로 본다.) 서로소 집합 알고리즘은 최소 신장 트리를 찾는 크루스칼 알고리즘에서 사용되기도 하므로 중요하다. union 연산을 확인하며, 서로 다른 두 원소에 대해 합집합(같은 그룹으로 합치기)을 진행할 땐, 각각의 루트노드를 찾아 큰 루트노드가 더 작은 루트를 가리키도록 구현한다. 시간 복잡도: O(V + M(1 + log2-m/vV)) 서로소 집합 구현 코드 ..

최단 경로 최단 경로(Shortest Path) : 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘. 최단 경로 문제는 보통 그래프를 이용해 표현한다. 각 지점(국가, 학교) -> '노드', 지점간 연결된 도로 ->'간선'으로 표현된다. 코테에선 최단 경로를 출력하는 문제 보단, '최단 거리'를 요구하는 문제가 많이 출제된다. 학부 수준의 다익스트라(Dijkstra) 최단 경로 알고리즘 플로이드 워셜(Floyd-Warshall) 알고리즘 벨만포드 알고리즘 최단 거리 알고리즘엔 3가지가 있지만, 그 중에서도 코테에 자주 등장하는 것은 2가지이므로 이것만 우선적으로 설명한다. 최단 경로 알고리즘의 대표적 유형 3가지 한 지점에서 다른 특정 지점까지의 최단 경로 (다익스트라) 한 지점에서 모든 지점까..

최적의 해를 구하기에 시간이 너무 많이 걸리거나 메모리 공간이 많이 필요한 문제가 있다. 이는 컴퓨터의 연산 속도, 메모리 공간에 대한 제약이 걸려 효율적인 알고리즘이 필요하다. 다만, 이런 문제들 중에서도 메모리 공간을 약간 더 사용하여, 속도를 비약적으로 높이는 방법이 있는데 이 중 대표적인 방법이 다이나믹 프로그래밍(Dynamic Programming)기법(동적 계획법)이다. 다이나믹 프로그래밍이란? 한번 해결된 부분 문제의 정답을 메모리에 기록하여, 한번 계산한 답은 다시 계산하지 않도록 하는 문제 해결법 이다. 다이나믹 프로그래밍은 *점화식을 그대로 코드로 옮겨 구현할 수 있다. (점화식: 인접한 항들 사이의 관계식) 대표적인 예시 문제가 피보나치 수열 문제이다. 피보나치 함수 코드 # 피보나치..

이진 탐색탐색의 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색하는 기법.특징이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때만 사용데이터의 개수가 1000만개를 넘어가거나 탐색 범위의 크기가 2000만-1000억 이면 이진 탐색으로 접근하길 권한다.3가지 변수(시작점, 끝점, 중간점)가 사용된다.시작점, 끝점 : 탐색하고자 하는 범위를 나타내기 위해 사용중간점 : 중간점에 있는 데이터와 찾고자 하는 데이터가 일치하는지 비교기위해 사용.시간 복잡도: O(logN) -> 한 번 비교때마다 반 씩 줄어드니까!소스코드 (재귀, 반복문)1. 재귀# 이진 탐색 소스코드 구현 (재귀 함수)def binary_search(array, target, start, end): if start > end: ..