트리(Tree) 트리는 Node와 Edge로 이루어진 자료구조이다. 각 노드들이 나무가지처럼 브랜치( = 엣지, 링크)로 연결된 비선형적, 계층적 자료구조이다. 트리의 구조 (용어) 노드와 에지 노드(Node) : 트리 구조에서 자료 값을 담고있는 단위 에지(Edge) : 각 노드 간의 연결 선 루트 노드(Root) : 가장 위의 노드 (1) 잎새 노드(Leaf) : 자식이 없는 노드 (8), (9), (10) ... 내부 노드(Internal) : 잎새 노드를 제외한 모든 노드 노드 간의 관계 부모(Parent) : 연결된 두 노드 중 상위 노드 (2번 노드는 4번 노드의 부모 노드) 자식(Child) : 연결된 두 노드 중 하위 노드 (4번 노드는 2번 노드의 자식 노드) 형제(Sibling) : 같..
문제 테스트케이스 첫째줄 (4) : 테스트 케이스 개수 각 테스트 케이스 R과 D로 이루어진 명령어 배열의 길이 배열(문자열로 주어진 배열) 알고리즘 분류 구현, 자료구조, 문자열, 파싱, 데크 자료구조 초기화 substring()을 통해 맨 앞에 ' [ ' , ' ] ' 을 잘라내고, ' , '을 구분자로 하여 split(",")으로 문자열을 쪼개주었다. 여기서 주의할 점은 만약 입력받은 배열 String의 길이가 2인 경우 "[ ]" 으로, 해당 연산을 할 경우 오류가 생긴다. 따라서 arrStr.length() > 2 라는 조건을 걸고 deque에 추가해준다. //arrStr = 입력받은 배열 String Deque deque = new LinkedList(); if(arrStr.length() >..
Map Map key - value 쌍으로 관리하는 메서드를 구현함 검색을 위한 자료구조 key값을 이용하여 값을 지정하고, 값을 꺼내오는 방식 - hash 알고리즘으로 구현됨 객체의 유일성 비교를 위해 equals() , hashCode() 메서드를 구현해야 함. CollectionFramework의 HashMap, Hashtable의 사용법이 궁금하신 분은 목차의 "HashMap 선언" 부터 보시면 됩니다! HashMap, Hashtable의 구조 키(Key) : 해시 테이블 접근을 위한 입력 값 해시 함수(Hash Function) : 키를 해시값으로 매핑하는 연산을 수행 해시 값(Hash Value) : 해시 테이블의 인덱스 HashMap, Hashtable : key - value..
Deque Queue와 Stack의 성질을 둘다 가지고 있다. Stack : push / pop / peek - 제일 늦게 들어간 것이 제일 먼저 나온다. Queue : offer / poll / peek - 제일 먼저 들어간 것이 제일 먼저 나온다. Deque : offerFirst, offerLast 등 : 양방향 Deque의 특징 Deque는 흔히 Stack과 Queue의 특징을 둘 다 갖고 있다고 한다. Queue는 선입선출의 구조를 가지고있다. Deque에서 offerLast로 값을 넣고, pollFirst로 값을 꺼내면 뒤(왼쪽)로 값을 넣고, 앞(오른쪽)에서 꺼내는 Queue와 같다. 또한, offerFirst로 값을 넣고, pollLast로 값을 꺼내면 위와 반대로 앞으로 값을 넣고, 뒤에..
문제 풀러 가기 : https://www.acmicpc.net/problem/11866 이 문제는 Queue 자료구조를 이용하면 매우 간단하다. K회 반복하는 for문을 돌며 queue에서 값을 꺼내고, 다시 넣기를 반복하다가, K번째 반복에서는 다시 넣지 않고 출력하기를 반복하면 된다. 이 반복을 queue.size() == 1이 될때 까지 반복하고, 마지막 남은 원소를 출력하고 마무리 한다. Code import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); StringBui..
Interface Queue 공식 문서 https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html Queue 선형 자료구조 First In First Out : 가장 먼저 입력된 자료를 가장 먼저 꺼낼 수 있음 맨 앞(front)에서 자료를 꺼내고, 맨 뒤(rear)에 자료를 추가함 몰랐던 영어지만, queue는 "차례를 기다리는 사람이나 승용자의 열"이라는 뜻이다. "대기줄"이라고 생각해도 될 것 같다. 먼저온 순서대로 들어가고, 먼저 온 순서대로 나간다. 변수 선언 Queue queue = new LinkedList(); 아래와 같이 new Queue로 직접 생성할 수도 있지만, Queue는 인터페이스 이기 때문에 해당 인터페이스의 메서드들을 모두..
Stack 선형 자료구조 Last In First Out : 가장 나중에 입력된 자료를 가장 먼저 꺼낼 수 있음 맨 마지막 위치(top)에서만 자료를 추가, 삭제, 꺼내올 수 있음 책을 책상 위에 쌓으면 위에서 만 꺼낼 수 있다. stack을 그대로 번역하면 "쌓다." 이기 때문에 말 그대로 아래서부터 데이터를 쌓고, 최근에 쌓은 데이터 즉, 맨 위의 데이터만 꺼낼 수 있다. 스택 생성 Stack stack = new Stack(); 데이터 처리 push(Object obj) : 데이터 추가 데이터를 맨 뒤에 추가한다. //값 추가 stack.push(1);//[1] stack.push(2);//[1,2] stack.push(3);//[1,2,3] pop() : 데이터 조회, 삭제 (꺼내기) 맨 뒤의 데..
BinarySearch : 이진탐색 (이분탐색) 이진탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는 방식이다. 크기가 100인 배열이 있고, 우리가 찾고자 하는 값이 99번째 인덱스에 들어있는 상황을 가정해 보자. 일반적인 반복문을 사용하여 1부터 100까지 반복하면 99번째 반복에서 찾고자 하는 값을 찾을 수 있다. 물론 이 경우 찾고자 하는 데이터가 앞쪽에 있다면 같은 데이터셋에 대하여 탐색 시간이 이분탐색을 이용했을 때보다 빠를 것이다. 그런데 만약 데이터의 크기가 1억 개이고, 운이 나쁘게도 우리가 찾고자 하는 값이 99,999,999 번째의 데이터인 경우에는 시간이 매우 오래 걸릴 ..
