pinevienna blog

크기를 변경할 수 없고, 비순차적인 데이터 추가/삭제에 시간이 많이 걸리는 배열의 단점을 보완하기 위해 고안되었다 배열이나 ArrayList는 물리적으로 데이터가 연속하지만 LinkedList는 불연속적인 데이터를 서로 연결(link)한 형태로 구성되어 있다 class Node { Node next; Object obj; } 이런식으로 다음 노드의 주소값을 가짐으로써 연결시킨다 삭제도 간단하다! 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음요소를 참조하도록 변경하면 된다 이전과 다르게 새로운 데이터의 추가, 삭제가 매우 빨라졌다 여기서 이전요소에 대한 접근도 가능한 Doubly Linked List도 등장한다 class Node { Node next; Node previous; Objec..

자바는 배열 생성시 고정된 배열 size를 입력해주어야 하지만 ArrayList 클래스를 사용하면 데이터를 추가할 때 자동으로 사이즈가 늘어난다 그러나 ArrayList의 입력 시간은 배열과 마찬가지로 O(1)이다 (검색은 정렬된 경우엔 O(log n), 정렬되지 않은 경우엔 O(n)이 걸린다) 입력할 때는 어차피 배열 사이즈가 고정되어 있기 때문이다 ArrayList는 배열이 다 차면 두 배 큰 크기의 새로운 배열을 선언하고 기존 배열의 데이터를 모두 옮겨오는 Doubling 작업을 하는데, 이 과정에서 n이 자꾸 두배로 늘어나기 때문에 입력값이 n을 따라갈 수 없다 (컬렉션 프레임워크가 도입되면서 증가율이 달라졌다고 함... 50%?) 더블링 작업에 걸리지 않은 데이터를 입력하는데 n만큼의 시간이 걸..

많은 데이터들을 효율적으로 관리하기 위해 자료구조와 알고리즘이 개발되었다 이 알고리즘의 성능을 수학적으로 표현하기 위해 빅오 표기법을 사용함 빅오로 시간 복잡도와 공간 복잡도를 나타낼 수 있음! 이 복잡도에는 몇 가지 규칙들이 있다 1. 입력값은 항상 0보다 크다 (입력값이 음수일 수 없음) 2. 입력값이 많을수록 더 많은 작업을 한다 3. 모든 상수를 삭제한다 : 어떤 알고리즘의 시간복잡도가 O(3n)이라면 3을 삭제한 O(n)이 해당 알고리즘의 시간 복잡도가 됨 4. 낮은 차수의 항들은 무시한다 : n과 n^2을 비교할 때, 어느 시점에선 n^2이 더 빠를 수 있지만 복잡도는 n이 무한으로 커진 경우를 가정해야 하기 때문에, 무조건 n^2가 더 오래 걸린다고 판단함 n^3 + n^2 + n 이라는 함..

AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 문제 함수와, 배열에 들어있는 수의 개수, 배열이 주어졌을 때 결과를 구하면 된다! RDD 4 [1,2,3,4] 이렇게 입력되면 [2,1]을 출력한다 문제 자체는 쉽다!! 근데 시간초과를 조심해야 한다 R이 순서를 뒤집는 함수라고 했는데, 진짜 뒤집으려 하면 끝도 없음 내가 또 그 끝도 없는걸 한 번 했었지..^^! 덱의 장점을 살려서, R을 홀수번 수행하면 역방향으로 출력하게..

큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐의 크기 N, 뽑아내려고 하는 수의 개수 M 뽑아내려고 하는 수의 위치가 순서대로 주어졌을 때 2번, 3번 연산의 최솟값을 출력하는 문제 덱을 이용하면 쉽다! 양방향으로 뺐다 넣었다.. 최솟값을 출력하라고 했으니 뽑아내려고 하는 수의 위치가 덱의 앞쪽이면 front의 원소를 뒤로 보내는게 빠르고,..