자료구조

파이썬 자료구조 set

롤케이크 자르기 (해시, Counter, set) karla.tistory.com # add() 요소 추가 my_set = {10, 20, 30} my_set.add(40) # {10, 20, 30, 40} # remove() 요소 삭제 my_set = {10, 20, 30} my_set.remove(10) # {20, 30} # Intersection (교집합) set1 = {3, 4, 9, 1, 4, 2, 5, 6, 7, 8, 10} set2 = {5, 6, 7, 8, 9, 10} # {5, 6, 7, 8, 9, 10} # Union (합집합) set1 = {3, 4, 9, 1, 4, 2, 5, 6, 7, 8, 10} set2 = {5, 6, 7, 8, 9, 10} print(set1 | set2) ..

[11505] 구간 곱 구하기 (세그먼트 트리)

11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 분석 세그먼트 트리, 인덱스 트리, 구간합 1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 karla.tistory.com 풀이 """ 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 ..

[14425] 문자열 집합 (트라이, Trie)

14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 트라이 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조 특징 N진트리 : 문자 종류의 개수에 따라 N이 결정됨. 예를 들어 알파벳은 26개의 문자로 이뤄져있으므로 26진트리로 구성됨. 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지 시간복잡도 문자열의 길이가 m이라면 시간 복잡도는 O(m) 현재 노드의 위치를 i, j번째 문자라고 한다면 trie[i][j]의 위치를 조회하는 건 O(1)에 수행 가능 문자열..

[17298] 오큰수 (스택)

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 분석 스택에 새로 들어오는 수 > top에 존재하는 수 : 새 수는 오큰수, top pop하면서 새 수 push 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1 출력 순서 스택이 채워져 있거나 a[idx] > a[top]인 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장. pop은 조건을 만족하는 동안 계속 반복 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어감 수열의 길이만큼 반복하고 스택에 남아있는 인덱스에 -1 저장 풀이 import sy..

[2018] 수들의 합 5 (투 포인터)

2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 분석 [2003] 수들의 합2 (투 포인터) 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmic karla.tistory.com 풀이 """ 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은..

[1940] 주몽 (투 포인터, 정렬)

1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net """ 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지 출력 첫째 줄에는 재..