자바에 진심인편

Deque 란 Queue에서 확장된 개념이다. 선입선출로 가장 첫번째 node만 꺼내고 빼올 수 있던 단방향 구조인 Queue와는 달리 Deque ( Double-ended Queue)는 양방향 구조이다. Queue의 연장선이기 때문에 Queue와의 차이점은 한쪽에서만 뺄 수 있느냐(단방향이냐) 양쪽에서 뺄 수 있느냐(양방향이냐)일 뿐 다른 차이점은 없다. 따라서 단방향구조였던 Queue 인터페이스를 상속받아서 양방향으로 메소드를 더 추가해주는 과정을 거친 것이 Deque라고할 수 있다. 구현 Deque는 구조적으로 Queue의 기능을 양방향으로 확장한 개념이기 때문에 Queue를 상속받아서 구현한다. Queue 구현에서 메소드는 너무 단순했다. LinkedList가 Queue를 상속(Deque를 상속받..

Queue 란 Stack과는 다르게 데이터가 들어간 순서대로 나오는 즉, FIFO(First In Last Out) 선입선출의 자료구조이다. First In First Out 선입 선출 먼저 들어간 것이 먼저 나온다. 데이터를 추출할 때 Stack은 마지막 데이터를 꺼내는 것과 달리 가장 앞에 있는 index를 꺼낸다. 먼저 들어온(push)된 값을 먼저 보낸다(pop)가 기본 베이스로 깔려서 다른 PrioritoyQueue나 Deque로 개념을 연장할 수 있다. Queue는 사실 먼저 들어온게 먼저 나가는 대기열로 생각하면 되고 대학생때 고통받는 수강신청에서 트래픽 대기가 보통 Queue 형태로 구현되어있다. 구현 사실 Queue도 또한 Collection 프레임워크에 포함되어있고, 물론 Stack과 ..

문제 설명 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한쪽은 1 감소시킵니다. 하지만, 모든 트리가 위의 행동을 통하여 모든 점들의 가중치를 0으로 만들 수 있는 것은 아닙니다. 당신은 주어진 트리에 대해서 해당 사항이 가능한지 판별하고, 만약 가능하다면 최소한의 행동을 통하여 모든 점들의 가중치를 0으로 만들고자 합니다. 트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a와 트리의 간선 정보를 의미하는 edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가..

Stack 이란 Stack, 우리는 스택이라는 용어를 쌓여가는 것에 사용한다. 1스택, 2스택 .... . 즉, Stack은 데이터가 쌓여가는 것을 나타내는 자료구조로 생각하면 편한다. Stack을 이야기할 때 항상 따라서 나오는 용어는 LIFO(Last In First Out)이다. (FILO(First In Last Out) 선입후출로 표현하기도 하는데 여기서는 후입선출로 통일하여 이야기 할 것이다.) Last In First Out 후입 선출 먼저 나온 것이 먼저 나온다. Stack은 데이터를 쌓아가면서 가장 마지막에 넣은 데이터를 먼저 꺼내는 형태의 자료구조를 말한다. 개념 자체는 매우 단순하다 먼저 넣을수록 밑으로 쌓여가고 빼낼때는 가장 최근에 넣은 값을 빼는 것, 예로 들면 웹페이지의 뒤로가기..

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 오지 탐험가인 프로도는 탐험 도중 n개의 방으로 이루어진 지하 동굴을 탐험하게 되었습니다. 모든 방에는 0부터 n - 1 까지 번호가 붙어있고, 이 동굴에 들어갈 수 있는 유일한 입구는 0번 방과 연결되어 있습니다. 각 방들은 양방향으로 통행이 가능한 통로로 서로 연결되어 있는데, 서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다. 임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며, 또한 임의의 두 방 사이에 이동이 불가능한 경우는 없습니다. 탐험에 앞서 이 지하 동굴의 지도를 손에 넣은 프로도는 다음과 같이 탐험 계획을 세웠습니다. 모든 방을 적어도 한 번은 방문해야 합니다. 특정 방은 방문하기 전에 반드시 먼저 ..

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 22843 6129 3657 28.573% 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시..

왜? 자바를 공부하면 For문을 먼저 배우게되고 For문을 배우면 따라나오는 것이 For Each문이다. 한국어로 이를 표현했을 때 "향상된 For문"이라는 말이 많이 나오는데 정말 향상되었는가에 대한 궁금증으로 인해 확인해보기로 했다. 테스트는 List안에 10000건의 값을 넣고 1로 초기화하는 것으로 진행하였다. public static long testFor(List list, long runTime){ int size = list.size(); long result = 0; long runTimeTmp = runTime; while(0 < runTimeTmp--){ long start = System.nanoTime(); for(int i=0; i index; i--) x = x.prev; re..

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 512 MB 237 74 33 20.625% 문제 N 개의 광물이 있다. i 번째 광물은 (Xi , Yi )에 있으며 캐내는 비용은 1이고, 이것의 아름다운 정도는 Vi 이다. 호석이는 지금 (0, 0)에 있다. 타고난 광부인 호석이는 시그니쳐 스킬인 "광산 뒤집기"를 쓰려고 한다. 이 스킬을 쓰면 자신이 있는 위치를 꼭지점으로 하며, 원하는 높이 H(H ≥ 0), 너비 W(W ≥ 0) 인 직사각형 영역 안에 있는 모든 광물을 캘 수 있다. 영역의 테두리에 존재하는 광물도 캐야한다. 주의할 점은, 직사각형 영역 안에 들어오는 광물은 무조건 캐야 하며, 영역에 속한 광물들의 캐내는 비용의 총합이 현재 가진 돈 C 보다 크면 파산을 하게 된다. ..