1. 정적 배열 자바에서 배열을 선언하기 위해 다음과 같이 선언한다. //길이 100인 정수형 배열 int[] array = new int[100]; 이렇게 선언한 배열을 정적 배열이라고 부른다. 정적 배열은 배열의 선언과 동시에 크기를 정해주어야하고, 이후 크기를 변경할 수는 없다. 변경하는 방법이야 있겠지만.. 그 방법이 쉽지는 않다 2. 동적 배열 자주 길이가 바뀌는 경우, 정적 배열을 사용하고 싶다면, 길이를 아주 충분히 큰 배열로 선언한다면 가능할지도 모른다. 하지만 너무 많은 메모리를 낭비하는 것일 수도 있다. 이를 해결하기 위해 나온 것이 동적 배열 동적 배열은 자유롭게 길이가 줄어들고 늘어날 수 있다. 정확히 사용하고 싶은 만큼만 공간메모리를 차지하여 사용하는 방식이다. 삽입, 삭제, 탐색..
1. 문제 9935번: 문자열 폭발 (acmicpc.net) 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 2. 풀이1 주어진 첫번째 문자열에서 제시된 두번째 문자열을 모두 지우고 합친다음에, 또 두번째 문자열이 존재한다면 지우고 합쳐서... 이를 반복해서 더이상 지울 문자열이 존재하지 않으면 그것을 출력하면 되는 간단한 문제 단순히 replace 함수를 사용하면 그냥 시간초과다 replace 함수가 O(N)보다 조금 더 걸린다고 함 from sys import stdin s1 = stdin...
1. 문제1 5052번: 전화번호 목록 (acmicpc.net) 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 2. 풀이1 한 번호가 다른 번호의 접두어인 경우가 없어야한다 번호를 트라이에 순차적으로 저장하다가, 마지막을 나타내는 플래그 '*'을 만난다면, 지금 저장하려는 번호는 다른 번호의 접두어가 될 것이다 class Trie: def __init__(self): self.head = {} def add(self,word): current_node = self.head #문자열의 ..
1. 문자열 단어 저장 'hello', 'hi', 'hey' 등을 저장하고자 할때, 생각할 수 있는 방법중 하나는 dictionary에 저장하는 것이다 d = {'hello':1, 'hi':1, 'hey':1} 단어를 key값으로 저장해두면, 특정 단어를 찾고자 할때, d['hello']같이 key로 접근해서 1인지 확인해보면 되니까 O(1)로 바로 찾을 수 있는 장점이 있다 하지만 공간복잡도 측면에서 단어가 100만개가 있다면 100만개의 공간이나 필요할 것이다 2. Trie 자료구조 Trie 자료구조는 효율적인 공간복잡도를 가지면서도, 시간복잡도도 충분히 효율적으로 만드는 문자열 저장 자료구조라고 할 수 있다. dictionary보다 조금 느리지만, 단어를 찾는데 단어를 구성하는 알파벳(문자)개수만..
1. 문제 11505번: 구간 곱 구하기 (acmicpc.net) 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 특정 구간의 합을 구하라는 것에서 특정 구간의 곱을 구하는 것으로 바뀜 근데 구간의 합을 구하는 것에서 몇가지 살짝? 신경써야함 2. 풀이 기본적으로 트리의 노드에 왼쪽 자식과 오른쪽 자식의 합을 저장하던 것을 왼쪽 자식과 오른쪽 자식의 곱을 저장하는 것으로 바꾸면 된다 tree[tree_index] = tree[2*tree_index]..
1. 트리의 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조 ############### 선형구조와 비선형구조 간단히 ################################# 2. 트리의 정의 1개 이상의 노드로 이루어진 유한 집합 즉, 노드가 1개만 있어도 트리 최상위 노드를 root라고 부른다 루트 이외의 나머지 노드들은 n개의 부분집합 $T_{1}, T_{2}, T_{3},... , T_{n}$으로 분리 가능하다 그림과 같이 $T_{1}, T_{2}, T_{3},... , T_{n}$도 하나의 트리가 되며, 루트의 부 트리(subtree)가 된다 그러니까 어떤 tree의 일..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
