JADE's Repository

문제 26008번: 해시 해킹 첫째 줄에 비밀번호의 길이 $N$과 문자 종류의 개수 $M$, 정수 $A$가 주어진다. ($1 \le N, M, A \le 5\,000\,000$) 둘째 줄에 재현이가 알아낸 해시값 정수 $H$가 주어진다. ($0 \le H < M$) www.acmicpc.net 풀이 $P_1 \cdot A+...+P_{N-1}\cdot A^{N-1}$ 을 $x$라고 해보자 $x=2, M=5$일 때 $P_0$ 값을 변경함에 따라 해시 함수의 결과 값이 0 ~ M-1 으로 나오는 것을 확인할 수 있다. 즉, $P_0$ 값에 따라 $h(P)$의 결과를 원하는 값으로 만들 수 있다. 하지만 $h(P)$를 해시값 정수 H로 만들 수 있는 $P_0$는 딱 1개 밖에 없다. 대신 $P_1 \cdot ..

Map? 키(key)와 값(value)으로 구성된 Entry 객체를 저장하는 구조 key와 value는 모두 객체 key는 중복 저장될 수 없으며 value는 중복 저장 가능 Map 컬렉션에는 HashMap, Hashtable, LinkedHashMap, Properties, TreeMap 등이 있음 Map의 공통 메소드 메소드 설명 put(key, value) 주어진 키로 값을 저장하며 새로운 키일 경우 null을 반환하고 동일한 키가 있을 경우 값을 대체하고 이전 값을 리턴 containsKey(key) 주어진 키가 있는지 여부 containsValue(value) 주어진 값이 있는지 여부 entrySet() 키와 값의 쌍으로 구성된 모든 Map.Entry 객체를 Set에 담아 반환 get(key) ..

많은 수의 데이터를 다룰 때 사용하는 자료 구조 각 데이터를 인덱스와 1:1 대응 메모리 상에 연속적으로 저장 장점 인덱스를 이용하여 데이터에 빠르게 접근 Array의 요소에 접근하거나 할당할 때의 시간복잡도는 O(1)이다. 단점 데이터의 추가시 최대 길이를 정하여 생성 후 생성한 배열에 옮겨야함 배열의 크기를 변경할 때마다 새로운 배열 생성 Java에서 배열 생성시 요소의 초기값은 각각 다음과 같다. 정수형 (int, short, byte, long): 0 부동소수점형 (float, double): 0.0 논리형 (boolean): false 문자형 (char): '\u0000' 또는 null 참조형 (객체 배열): null

문제 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 1. 정렬을 통한 풀이 import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int[] intArray = new int[N]; for (int i=0..

문제 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 N=10, M=3, 원소의 위치={2,9,5}라고 할 때 2번, 3번 연산에 따라 아래와 같이 진행되어야한다. 왼쪽으로 이동했을 때와 오른쪽으로 이동했을 때의 거리를 계산하여 가장 짧은 쪽의 방향을 선택하여 수행하면 되는 문제이다. 아래 코드는 직접 LinkedList로 구현하여 양방향 이동을 가능하게하였다. import java.util.*; import java.util.stream.Collectors; import java.util.strea..

Queue? 위 그림의 왼쪽처럼 식당에 입장하기 위해 줄을 서는 것을 생각해보면 가장 먼저 줄을 선 사람이 가장 먼저 입장한다. Queue도 이와 같은 방식으로 동작한다. 이처럼 먼저 들어간 것이 먼저 나오는 것을 선입선출(First In First Out, FIFO)라고 한다. Queue의 주요 연산 Enqueue와 Dequeue Enqueue(): 값을 집어넣는 것을 의미 Dequeue(): 값을 꺼내는 것을 의미 Java에서 Queue의 Enqueue와 Dequeue 메소드 Enqueue: add, offer Dequeue: remove, poll Queue의 시간복잡도 Enqueue(): O(1) Dequeue(): O(1) 탐색: O(n) Queue에서 값을 탐색하여 얻는 것은 부적절하다. 실제..

문제 25556번: 포스택 포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다. www.acmicpc.net 풀이 N=10, A={4,3,6,7,8,9,10,2,1,5} 일 때 4개의 Stack에 아래와 같이 삽입한다. 결과가 {1,2,3,4,5,6,7,8,9,10} 이어야하고 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치해야하므로 각 4개의 Stack에 담긴 Element를 가장 큰 수부터 차례대로 아래와 같이 꺼낼 수 있다. 차례대로 Stack에서 가장 큰 수를 차례대로 꺼낼 수 있게하는 조건은 Stack에 값을 Push할 때 반드시 작은 값이 아래로 가고 큰 값은 반드시 위에 쌓여야한다. e.g. {1, 3, 4} (O), {3, 1, 4} (X) 따라서 ..

Stack? 위처럼 접시를 쌓으면 마지막에 쌓은 접시가 맨 위에 놓일 것이다. 그러면 당연하게도 가장 마지막에 쌓은 접시를 제일 먼저 꺼내게 된다. Stack도 이와 같은 방식으로 동작한다. 이처럼 마지막에 쌓은 것을 가장 먼저 꺼내게되는 것을 후입선출(Last In First Out, LIFO)이라고 한다. Stack의 주요 연산 Push와 Pop push(): 요소를 추가 pop(): 가장 최근에 추가된 요소를 제거 Stack의 시간복잡도 push(): O(1) pop(): O(1) get(): O(n) get(): 값을 조회하는 메소드 Appendix 1946년 앨런 튜링은 서브 루틴을 호출하는 과정을 bury, 되돌아오는 과정을 unbury라고 불렀는데 이것을 스택의 기원이라고도 한다. 스택은 콜..

relation database의 relations들이 지켜야하는 제약사항 implicit constraints relational data model 자체가 가지는 constraints relation은 중복된 tuple을 가질 수 없다 relation 내에서는 같은 이름의 attribute를 가질 수 없다 schema-based constraints DDL을 통해 schema에 직접 명시할 수 있는 constraints explicit constraints라고도 함 1. domain constraints attribute의 value는 해당 attribute의 domain에 속한 value여야 한다. 예를 들어서 email attribute에 포맷에 맞지않는 "email"이 들어가 있으면 안되고 "e..

super key relation에서 tuples를 unique하게 식별할 수 있는 attrubutes set 예를 들어 User(id, name, email, phone)의 super key는 {id, name, email, phone}, {id, name}, {name, email} 등이 된다. {name}과 같은 경우에는 동명이인과 같은 상황이 발생할 수 있기때문에 superkey가 될 수 없다. candidate key 어느 한 attrubute라도 제거하면 unique하게 tuples를 식별할 수 없는 super key super key 중 가장 최소한의 attribute를 가지는 key 예를 들어 위 super key 예시에서 {id, name, email, phone}는 email과 phon..