makeUptheBed

문제

https://www.acmicpc.net/problem/6588

아이디어 및 알고리즘

에라토스에라토스테네스의 체를 이용하여 1부터 100만까지의 소수를 저장해 놓고 확인한다.

과정

1. 에라토스테네스의 체를 이용하여 1부터 100만까지의 소수를 boolean[1000000]에 체크를 해놓는다.

2. boolean 배열만 이용하면 시간이 초과되기 때문에  int배열에 따로 소수만 저장한다.

3. 골드바흐의 추측을 확인할 값을 N이라 할때 int배열에 저장된 작은 소수부터(p) N-p가 소수인지 확인한다. 

코드

import java.util.HashSet;
import java.util.Scanner;
	
	public class Main {
		
		public static void main(String[] args) throws Exception{
			Scanner sc=new Scanner(System.in);
			boolean[] check=new boolean[1000000];
			int size=0;
			int index=0;
			for(int i=1;i<1000000;i++) {
				check[i]=true;
			}
			for(int i=2;i*i<1000000;i++) {
				if(check[i]) {
					for(int j=i*i;j<1000000;j+=i) {
						check[j]=false;
					}
				}
			}
			for(int i=3;i<1000000;i++) {
				if(check[i]) {
					size++;
				}
			}
			int[] primes=new int[size];
			for(int i=3;i<1000000;i++) {
				if(check[i]) {
					primes[index++]=i;
				}
			}
			
			while(true) {
				int N=sc.nextInt();
				
				if(N==0) {
					break;
				}
				for(int i=0;i<size;i++) {
					int prime=primes[i];
					if(check[N-prime]) {
						System.out.println(N+" = "+prime+" + "+(N-prime));
						break;
					}
				}
			}
		}
		
		
	}

문제

https://www.acmicpc.net/problem/5052

아이디어 및 알고리즘

입력을 long으로 받는대신 String으로 받아 좀 편하게 한것같다.

HashSet을 구현해서 입력받은 값을 넣은 뒤 Substring을 이용해서 HashSet에 넣어보며

이미 SubString이 포함되는지 확인했다.

과정

1. 전화번호를 저장 할 String[N]과 HashSet<String>을 만들고 값을 저장한다.

2. 각각의 전화번호에 대해 예를들어 전화번호=1234 라 하면 1, 12, 123 이 HashSet에 포함되어 있는지 확인하고

   포함되어있으면 NO를 출력한다. 만약 모든 전화번호에 대해 포함하지 않으면 YES를 출력한다. 

코드

import java.util.HashSet;
import java.util.Scanner;
	
public class Main {	
	public static void main(String[] args) throws Exception{
		Scanner sc= new Scanner(System.in);
		int t=sc.nextInt();
		while(t-->0) {
			int N=sc.nextInt();
			String[] list=new String[N];
			HashSet<String> hs=new HashSet();
			
			for(int i=0;i<N;i++) {
				list[i]=sc.next();
				hs.add(list[i]);
			}
			boolean flag=false;
			loop:
			for(int i=0;i<N;i++) {
				String check=list[i];
				int length=check.length();
				for(int j=1;j<length;j++) {
					if(hs.contains(check.substring(0,j))) {
						flag=true;
						System.out.println("NO");
						break loop;
					}
				}
			}
			if(!flag) {
				System.out.println("YES");
			}
		}
	}
	static long power10(int n) {
		long total=1;
		for(int i=0;i<n;i++) {
			total*=10;
		}
		return total;
	}
}

DDL ( 데이터 정의어 )

* 실행시키면 자동으로 commit 된다.

create : 테이블 생성

테이블 이름 규칙 :

1) 문자로 시작

2) 길이 1~30

3) 대문자,소문자,숫자,_,$,# 만 포함가능

4) 예약어 불가, 중복 불가

*default : 입력 안했을시 자동으로 default 값 입력됨

*이미 만들어진 테이블 구조,데이터 그대로 복사해서 테이블을 생성 할 수 있다.

데이터 유형

1) VARCHAR2(size) : 가변 길이 문자 데이터 size 이내 길이면 된다.

2) CHAR(size) : 고정 길이 문자 데이터 길이가 정확히 size여야 한다.

3) NUMBER(p,s) : 가변길이 숫자데이터 자릿수 p, 소수점 이하 자릿수 s

4) DATE : 날짜 및 시간 값

constraint(제약조건)

1) not null : null값을 허용하지않는 제약조건

2) unique key : 중복은 안되지만, null 허용

3) primary key : 중복,null 둘다 안됨

* primary key, unique key를 만들면 자동으로 index가 생성된다.

4) check key : 조건으로 제약을 줌

5) primary key, unique key를 만들면 자동으로 index가 생성된다.

6) foreign key : 참조하는 테이블의 pk값 + null

alter : 구조 변경

1) add: column 추가

2) modify : column 데이터 타입 변경

3) drop : column 삭제

4) set unused : 실제 삭제는 아니지만 출력되지 않도록 설정

  drop unused columns 을 통해 set unused해논 column삭제

5) read only : 변경 불가능하게 설정 ( drop table 만 가능하다)

drop :테이블 삭제

1) flashback table 테이블명 to before drop : drop한것 다시 살릴 수 있다.(휴지통에 넣은거 복구하듯)

2) drop table 테이블명 purge : flashback하지 못하게 drop하는 옵션

truncate : 테이블 존재, data만 모두 삭제

DML (데이터 조작어)

insert : 새 행 추가

* 데이터 타입이 문자열인경우 ''(빈 문자열)로 null값을 입력 할 수 있다.

*같은 구조의 table 에서 행을 가져와 insert 할 수 있다.

update : 칼럼 data값 변경

where 절을 통해 조건을 주지 않으면 다 변경된다.

*업데이트할때 서브쿼리를 사용 할 수 있다.

delete : 행 삭제

where 절을 통해 조건을 주지 않으면 다 삭제된다.

TCL : 트랜젝션 제어어 

트랜잭션 : DML의 논리적 작업단위 (commit , rollback 하기 전까지의 DML)

* commit 하기 전엔 실행한 DML의 작업이 저장되지 않으며 rollback 하면 마지막 commit 으로 돌아간다.

  DDL을 하면 자동으로 commit이 되므로 주의해야한다.

* 세이브 포인트를 만들어서 원하는 위치까지만 rollback 할 수 있다.

commit : 영구반영

rollback : 취소

commit : 영구반영

rollback : 취소

집합연산자

SELECT 하는 열의 갯수가 같아야하고 상응하는 열의 데이터유형이 같아야한다.

UNION / UNION ALL : 합집합 연산 

INTERSECT : 교집합 연산

MINUS : 차집합 연산

* 기본적으로 집합연산이기때문에 UNION ALL 을 제외한 나머지 연산들은 중복행을 제거한다. 

SELECT 열 의 갯수와 상응하는 데이터 유형이 같아야 하므로 한 테이블에만 있는 열은 

다른 열에서억지로 규격을 맞춰서 SELECT 해야한다.

*FULL OUTER JOIN이 (+)로 구현하지 못하였는데 UNION 연산을 이용하면 구현가능하다.

문제

https://www.acmicpc.net/problem/19238

아이디어 및 알고리즘

BFS를 통해 모든 택시의 위치에서의 최소 거리를 미리 다 구해놓고 문제를 풀었다.

조건을 최대한 디테일하게 구현하는것을 위주로 하면 좋을것 같다. 

과정

1. 모든 위치에서의  최소거리를 구하기위해 int costs[N+1][N+1][N+1][N+1] 을 구현한다.

2. BFS를 통해 최소거리를 구하고 costs에 저장한다.

3. costs를 통해 매번 최소 위치에 있는 손님의 위치를 구한다.

4. 조건에 맞게 최소 위치에 있는 손님이 많을때 낮은 행, 낮은 열에 있는 손님을 다시 구한다.

5. 목적지까지 도달 할수 있는지 확인하고  목적지에 도달하면 다시 손님을 찾는것을 반복한다.

코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int[] dx= {1,-1,0,0};
	static int[] dy= {0,0,1,-1};
	public static void main(String[] args) {
		int total=0;
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int M=sc.nextInt();
		int fuel=sc.nextInt();
		
		location driver=new location(0,0);
		location[] passengers=new location[M];
		location[] destinations=new location[M];
		
		int[][] map=new int[N+1][N+1];
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				map[i][j]=sc.nextInt();
			}
		}
		
		driver.x=sc.nextInt();
		driver.y=sc.nextInt();
		
		for(int i=0;i<M;i++) {
			passengers[i]=new location(sc.nextInt(),sc.nextInt());
			destinations[i]=new location(sc.nextInt(),sc.nextInt());
		}
		
		int[][][][] costs=new int[N+1][N+1][N+1][N+1];
		for(int i1=1;i1<=N;i1++) {
			for(int j1=1;j1<=N;j1++) {
				if(map[i1][j1]==0) {
					Queue<location> q=new LinkedList();
					q.add(new location(i1,j1));
					costs[i1][j1][i1][j1]=1;
					while(!q.isEmpty()) {
						location check= q.poll();
						int x=check.x;
						int y=check.y;
						for(int i=0;i<4;i++) {
							int nx=x+dx[i];
							int ny=y+dy[i];
							if(nx>=1&&nx<=N&&ny>=1&&ny<=N) {
								if(map[nx][ny]==0&&costs[i1][j1][nx][ny]==0) {
									costs[i1][j1][nx][ny]=costs[i1][j1][x][y]+1;
									q.add(new location(nx,ny));
								}
							}
						}
					}
				}
			}
		}
		boolean[] visited=new boolean[M];
		for(int i=0;i<M;i++) {
			int min=10000;
			int index=0;
			int x1=driver.x;
			int y1=driver.y;
			for(int j=0;j<M;j++) {
				int x2=passengers[j].x;
				int y2=passengers[j].y;
				if(costs[x1][y1][x2][y2]>0&&costs[x1][y1][x2][y2]<min&&!visited[j]) {
					index=j;
					min=costs[x1][y1][x2][y2];
				}
			}
			if(min==10000) {
				System.out.println(-1);
				return;
			}
			int cost1=min;
			
			
			for(int k=0;k<M;k++) {
              	int x3=passengers[index].x;
                int y3=passengers[index].y;
				int x2=passengers[k].x;
				int y2=passengers[k].y;
				if(!visited[k]&&costs[x1][y1][x2][y2]==cost1) {
					if(x2<x3) {
						index=k;
					}
					else if(x2==x3) {
						if(y2<y3) {
							index=k;
						}
					}
				}
			}
			visited[index]=true;
			driver=passengers[index];
			cost1--;
			fuel-=cost1;
			
			if(fuel<0) {
				System.out.println(-1);
				return;
			}
			int cost2=
            	costs[driver.x][driver.y][destinations[index].x][destinations[index].y]-1;
			if(cost2==-1) {
				System.out.println(-1);
				return;
			}
			fuel-=cost2;
			if(fuel<0) {
				System.out.println(-1);
				return;
			}
			driver=destinations[index];
			fuel+=2*cost2;
			total++;
		}
		if(total==M) {
			System.out.println(fuel);
		}
		else {
			System.out.println(-1);
		}
	}
}
class location{
	int x;
	int y;
	public location(int x,int y) {
		this.x=x;
		this.y=y;
	}
}

문제

https://www.acmicpc.net/problem/1613

아이디어 및 알고리즘

방향그래프를 구현하고 BFS를 이용하여 푼다.

과정

1. int[N+1][N+1] graph를 구현하고 사건1이 사건2보다 먼저 일어났을때 graph[1][2]=1 값을 대입한다.

2. boolean[N+1][N+1] visited를 구현해서 visited[a][b]=true 의 의미를 "a사건이 b사건 보다 먼저 일어난다" 라는 사실을 저장하는 용도로 사용한다. (중복해서 확인하는 일을 제외하기 위해)

3. 사건 1부터 N까지 Queue를 활용하여 이후에 일어난 사건을 구한다.

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int M=sc.nextInt();
		int[][] graph=new int[N+1][N+1];
		boolean[][] v=new boolean[N+1][N+1];
		
		for(int i=0;i<M;i++) {
			int x=sc.nextInt();
			int y=sc.nextInt();
			graph[x][y]=1;
		}
		
		for(int i=1;i<=N;i++) {
			Queue<Integer> q=new LinkedList();
			q.add(i);
			while(!q.isEmpty()) {
				int check=q.poll();
				for(int j=1;j<=N;j++) {
					if(graph[check][j]==1&&!v[i][j]) {
						v[i][j]=true;
						graph[i][j]=1;
						q.add(j);
					}
				}
			}
		}
		
		int K=sc.nextInt();
		for(int i=0;i<K;i++) {
			int x=sc.nextInt();
			int y=sc.nextInt();
			if(graph[x][y]==1) {
				System.out.println(-1);
			}
			else if(graph[y][x]==1) {
				System.out.println(1);
			}
			else{
				System.out.println(0);
			}
		}
	}
}

JOIN : 두개 이상의 테이블에서 데이터를 사용할때 필요하다.

EQUIJOIN : 동일한 column의 동일한 값을 중심으로 두 테이블을 join

1) JOIN 명령어 없이 쓰는 조인

    alias를 사용하여 where 절에서 공통된 column에 조건을 줘서 조인을 한다.

 2) NATURAL JOIN

  두 테이블간 공통된 column 이 존재할 경우 알아서 column값이 일치하는 row들을 출력

  공통된 column이 2개 이상이면 공통된 모든 column이 일치하는 row들을 출력한다.

 3) USING 절을 사용하여 JOIN

 여러 column이 동일하지만 하나의 column을 이용하여 조인을 하고싶을때 사용

4) ON 절을 이용하여 JOIN

 ON 절은 WHERE 절 역할을 한다.

 3개 이상의 테이블을 join 할 수 있다.

 추가적인 조건을 위해 AND, WHERE 둘다 쓸 수 있다.

 5) SELF JOIN

  같은 테이블이지만 마치 다른테이블처럼 조인할때 사용한다.

NONEQUIJOIN : 등호연산자 외에 다른 연산자를 포함하는 JOIN

OUTER JON

한쪽의 정보를 다 보고싶을때 null값을 가지더라도 출력하는 join

위와 같이 Grant 의 department_id = null 이지만 left outer join에 의해 출력이 된다.

* outer join을 직접쓰지 않고도 구현 가능하다. null값까지 출력을 원하느 곳에 (+)를 쓰면 된다.

FULL OUTER JOIN

겹치는거,양쪽의 정보 다 보고 싶을때

*양쪽에 (+)를 쓴다해서 실행되지 않는다.

CARTESIAN PRODUCT

CROSS JOIN

따로 조건을 주지않고 모든 경우의수를 다 나타내는 조인

where 절이나 on 절을 쓰지 않고 바로 조인하였을때 (컬럼의 row 개수 * 컬럼의 row 개수) 만큼 출력된다.

Subquery

쿼리(outer 쿼리)안에 조건을 쿼리(inner 쿼리)를 쓰는 형식

subquery는 무조건 괄호 안에 써야한다.

any : 집합 안의 적어도 하나의 원소에 대해 참이면 참을 반환한다.

all : 집합 안의 모든 원소에 대해 모두 참이어야지만 참을 반환한다.

* not in 연산을 할때 집합 안에 null이 있으면 아무것도 반환하지 않는다.

  그러므로 not in 연산을 할땐 집합이 반환되는 subquery에서 where is not null을 해줘야 한다.

  하지만 in 연산을 할땐 집합 안에 null이 있어도 상관 없다.