Algorithm

Baekjoon - 10866번

- 문제 - Dequq을 활용하여 구현하는 문제이다. Buffer을 통하여 명령 수를 입력 받고 if문을 통하여 조건 별로 Dequq 인터페이스에 내재되어있는 메소드를 활용하면 되는 간단한 문제이다. - 그런데 출력쪽에서 문제가 생겼다. - 출력 조건이 명령이 주어질 때마다, 한줄에 하나씩 출력해야 한다. * 다시 말해, push_back 1과 push_front 2를 입력한 다음에 3번째 명령어인 front를 입력하면 바로 2가 출력되어야 하고 back을 입력하면 1이 바로 출력되어야 한다는 뜻이다. - 여태 껏 풀었던 문제는 모든 명령어를 입력한다음 한번에 출력이 되는 방식이었기 때문에 이 부분에서 헤매었다. - 처음 작성한 코드는 다음과 같다. package _10866_Dequq; import j..

Deque(덱)

- Double Ended Queue 의 줄임말 - Queue의 양쪽으로 엘리먼트의 삽입과 삭제를 수행 할 수 있는 자료구조 1. 한쪽으로 입력 가능한 덱을 스크롤(scroll), 한쪽으로만 출력 가능한 덱을 셸프(shelf)라고 한다. 2. 자바에서 덱은 인터페이스로 구현되어 있다. 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 존재한다. - Dequq의 인터페이스 메소드 - 대표적인 Dequq 구현 방법

Big-O 표기

- 시간 복잡도 : 단순 시간이 아닌 연산 연산 횟수를 기준 - 시간 복잡도 예시 N = 입력 된 수 : ex) 16 O(1) : 상수시간 O(logN) : 로그 = 4 O(N) : 직선(선형) = 16 (for 문) O(NlogN : 선형 로그 = 16 * 4 = 64 O(N^2) = 256 (이중 for문) O(2^N) = 65,xxx (피보나치 수열) 아래로 내려갈수록 시간 복잡도는 높아짐. * 알고리즘 작성에 있어서 효율성을 증가시키는 것은 매우 중요함. * 시간 복잡도 = N값의 증가에 따른 처리 시간이 증가하는 정도