JADE's Repository

문제 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..

set (집합) 서로 다른 요소들을 가지는 collection 순서를 보장하지 않음 수학의 relation과 의미 아래와 같이 A 집합과 B 집합이 있을때 각각의 요소들을 선택하여 쌍을 만든다. 그러면 (1, p), (1, q), (1,r), (2, p), (2,q), (2,r) 이 생길 것이다. 그리고 이렇게 표현한 것을 카르테시안 곱(cartesian product)라고 한다. 이 카르테시안 곱이 relation과 관련이 있는데 아래처럼 집합이 A, B 두 개가 있을 경우 binary relation 이라고 한다. 여기서 relation의 의미가 바로 A x B 카르테시안 곱의 부분 집합이라는 것이다. 그리고 아래처럼 집합이 n개까지 있다고 한다면 n-ary relation 이라 하고 n개의 집합에 ..

집합 생성 HashSet setA = new HashSet(); setA.add(1); setA.add(2); setA.add(3); setA.add(4); HashSet setB = new HashSet(); setA.add(3); setA.add(4); setA.add(5); setA.add(6); 합집합 setA.addAll(setB); // {1, 2, 3, 4, 5, 6} 교집합 setA.retainAll(setB); // {3, 4} 차집합 setA.removeAll(setB); // {1, 2}

Data Definition Language (DDL) conceptual schema를 정의하기 위해 사용되는 언어 Storage Definition Language (SDL) internal schema를 정의하는 용도로 사용되는 언어 relation DBMS에서는 SDL이 없고 파라미터 등의 설정으로 대체한다고 함 View Definition Language (VDL) external schema를 정의하기 위해 사용되는 언어 대부분의 DBMS에서는 DDL이 VDL 역할까지 수행 Data Manipulation Language (DML) 데이터 추가, 삭제, 수정, 검색 등의 기능을 제공하는 언어 Data Control Language (DCL) 데이터 핸들링 권한 설정, 데이터 무결성 처리를 ..