SY DevLog

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 합이 k원이 되면서, 순서만 다르고 조합이 같은 경우는 하나의 경우로 여긴다. 우선 각각의 동전의 가치를 coin 배열을 생성하여 차례대로 넣어주었다. int[] coin = new int[n]; coin[0] = 1 coin[1] = 2 coin[2] = 5 이 문제를 다이나믹 프로그래밍으로 풀기 위해 점화식을 세웠다. 처음에는 합이 k원이 되는 조합을 dp[k]라고 할 때, dp[k] = dp[k-coin[0]] + dp[k-coin[1]] + dp[k-coi..

자바에서 예외는 크게 Error 와 Exception 로 나눌 수 있다. 자바에서 모든 예외는 Throwable 클래스로부터 파생된다. Throwable 클래스로부터 Error와 Exception으로 나뉘게 되며, Exception은 다시 기타 예외들과 RuntimeException으로 나뉜다. Error Error는 치명적인 오류가 발생하는 경우이다. 여기서 '치명적이다' 라는 것은 오류가 복구 불가능하여 별다른 처리를 할 수 없는 상태이다. 따라서 Error는 예외처리 대상이 아니다. 우리가 흔히 접하는 Error에는 대표적으로 OutOfMemoryError, StackOverflowError 등이 있다. - OutOfMemoryError : 메모리를 초과하는 경우 발생하는 에러 - StackOver..

자바에서 문자열을 나타낼 때 String, StringBuffer, StringBuilder 3가지 클래스를 사용할 수 있다. 하지만 이 3가지는 약간의 차이가 존재한다. String 가장 기본적인 문자열 클래스이다. String str = "Hello"; 를 선언하면 str는 참조변수로써 "Hello"가 존재하는 주소를 가리킨다. String 클래스는 기본적으로 Immutable이다. Immutable 객체란, 변하지 않는 객체임을 의미한다. 예를 들어 String str = "Hello"; 라고 선언한 후, 기존의 "Hello" 문자열 뒤에 "World" 를 추가하고 싶은 경우, str = str + "World"; 을 실행하면 문자열 뒤에 "World"를 추가할 수 있게 된다. String str ..

7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net HashSet을 이용하여 직원이 들어오면("enter") set에 추가하고, 직원이 나가면("leave") set에서 제거하는 방식으로 문제를 해결하였다. 최종적으로 set에 남아있는 직원이 현재 회사에 있는 사람이 된다. Iterator를 통해 set에서 직원을 하나씩 꺼낸 다음에 list에 담고, list를 이름 역순이 되도록 정렬했다. 전체 코드 :

ArrayList, LinkedList, Vector 모두 java.util 패키지에 존재하는 List 인터페이스를 구현한 클래스이다. ArrayList ArrayList는 List를 배열로 구현한 것이다. 따라서 인덱스를 통해 요소에 접근한다는 점에서 배열과 유사하다. 하지만 배열은 그 크기가 고정되어 있는데 반해 ArrayList는 크기를 동적으로 변경이 가능하다. add() 메서드를 통해 요소를 새로 추가할 수 있다. Vector Vector도 List를 배열로 구현한 것이다. 배열과 달리 동적으로 크기를 변경할 수 있다는 점에서 ArrayList와 유사하다. ArrayList와 마찬가지로 add() 메서드를 통해 새로운 요소를 추가할 수 있다. ArrayList는 멀티 스레드 환경에서 동기화를 지..

3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 누적합으로 문제를 해결하였다. 각각의 높이에 따라 석순과 종유석의 개수를 카운트하는 두 개의 배열 bot, top을 생성하였다. 예를 들어, 첫 번째 구간에서는 석순이 7개 존재하므로 bot[1] = 7 이 된다. 두 번째 구간에는 석순이 6개 존재하므로 bot[2] = 6 세 번째 구간에는 석순이 5개 존재하므로 bot[3] = 5 네 번째 구간에는 석순이 1개 존재하므로 bot[4] = 1 다섯 번째 구간에는 석순이 0개 존재하므로 bot[5] = 0 첫 번째 ..

후보키(Candidate Key) 튜플을 유일하게 식별할 수 있는 속성의 부분집합이다. 후보키는 유일성과 최소성을 만족한다. - 유일성 : 튜플을 유일하게 식별할 수 있음을 의미한다. - 최소성 : 튜플을 식별하기 위해서 꼭 필요한 속성들로 구성되어 있어야 한다. 위의 [학생] 테이블에서 각 튜플을 유일하게 식별할 수 있는 속성은 주민등록번호, 학번, 전화번호다. 주민등록번호, 학번, 전화번호 모두 사람마다 가지고 있는 고유한 정보이기 때문이다. 따라서 위의 테이블에서 후보키가 될 수 있는 속성은 주민등록번호, 학번, 전화번호이다. 기본키(Primary Key) 후보키 중에서 튜플을 대표하는 키를 하나 선택하여 기본키라 한다. 기본키는 유일성과 최소성을 만족하며, NULL값을 허용하지 않는다. [학생] ..

Disjoint Set(분리집합)이라고도 한다. 서로 중복되지 않는(교집합이 없는) 둘 이상의 집합의 정보를 저장, 조작하는 자료구조이다. 유니온 파인드는 3가지 연산이 존재한다. make - set(x) : 초기화를 하는 연산이다. x를 원소로 하는 새로운 집합을 생성한다. 이때 생성되는 집합은 x만을 원소로 갖는다. union(x, y) : x가 포함된 집합과 y가 포함된 집합을 하나의 집합으로 합친다. find(x) : x가 어느 집합에 속해 있는지를 찾는다. 유니온 파인드를 구현하는 방법은 다양한데, 그 중에서도 가장 잘 알려진 트리를 이용한 방법을 설명할 것이다. 트리를 이용한 Union-Find 트리를 이용하여 유니온 파인드를 구현할 경우, 하나의 트리는 집합 1개를 의미하며 트리의 루트 노드..

3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 매번 느끼는거지만 스택을 이용한 문제는 개인적으로 너무 어렵다.. 보통 스택을 사용하는 문제의 경우, 스택 자체보다는 스택을 어떻게 사용해야할 지 생각해내는게 어려운 것 같다. 이번 문제도 역시 해결하는데 오랜 시간이 걸렸는데, 가장 어려웠던 것은 키가 같은 사람이 여러명일 경우에 어떻게 해야할지 고민을 오래 했다. 먼저, 이 문제는 특정 사람이 비교기준이 될 때, 스택안에 어떤 사람들이 들어가야 하는지 고민해야 한다. 2 4 3 2 1 ..

비트마스크(BitMask) 이진수 표현을 자료구조로 사용하는 기법이다. 하나의 비트에서 나타낼 수 있는 경우의 수는 0 혹은 1 두가지가 있다. 보통 비트마스크를 이용하는 경우에 0이면 false, 1이면 true를 나타내며, 특정 집합에서 원소의 포함 여부를 표현할 때 사용한다. 비트단위로 정보를 처리하기 때문에 메모리를 적게 사용할 뿐만 아니라 수행 속도가 빠르다는 장점이 있다. 비트 연산 비트마스크는 비트 연산을 이용하여 집합 내의 원소를 다룰 때 주로 사용된다. 예를 들어, 0부터 9까지 넣을 수 있는 어떠한 집합 S가 존재하고 그 집합 내에 들어있는 원소가 0,1,2 이라고 하자. 만약 배열로 이를 표현한다고 하면, 10개의 크기를 가지는 boolean 배열을 생성하고, arr[0] = true..