Posts

오라클 DB의 문제이만 Mysql 계열의 MariaDB로 풀었습니다. 제가 구한 샘플데이터에 맞게 문제의 수치도 조금 바꿨습니다. 풀면서 느낀 SQL의 가장 큰 차이는 MAX(count(*))가 안된다는 것.. ...

1. Join Join을 통해서 2개 이상의 테이블을 연결할 수 있다. Join은 기본적으로 기본키나 외부키의 값의 연관에 의해 성립되지만, 논리적인 값들의 연관만으로도 성립할 수 있다. Join의 조건은 where절에 기술한다. Join의 종류는 다음과 같다. Join 방법 의미 equi join 두 개의 테이블 간의 칼럼값들이 정확하게 일치하는 경우에 사용 non- equi join 두 개의 테이블 간의 칼럼값들이 정확하게 일치하지 않는 경우에 사용 outer join Join의 조건을 만족하지 않는 데이터들도 보고자 하는 경우 self join 두 개의 테이블이 아니라 같은 테이블 행들을 Join하는 경우 2. Cross Join(Cartesian Product) 테이블들 간의 Join 조건을 생략하거나 조건을 잘못 설정했을 경우, 첫 번째 테이블의 모든 행들에 대해서 두번째 테이블의 모든 행들이 Join되어 조회되는 데이터의 형태를 말함. 카티션 곱이 발생하면 조회되는 데이터의 수가 기하급수적으로 증가하기 때문에 DB나 네트워크에 부담이 된다. 2.1 예 1 SELECT D.DEPARTMENT_ID, D.DEPARTMENT_NAME, E.FIRST_NAME, E.LAST_NAME FROM HR_DEPARTMENTS D, HR_EMPLOYEES E 3. Equi join(Inner Join,등가 조인) : ‘=’ 연사자 이용 두 테이블의 일치하는 칼럽을 연결해서 Join하는 것을 등가조인이라고 함. 두 테이블간의 칼럼 값들이 일치하는 경우에 사용하며, 테이블별로 alias를 사용해 구분해주는 것이 좋다. Join을 하는 테이블이 N개인 경우, 최소 N-1개의 Join조건이 where절에 와야 한다. 3.1 예제 1 2 //사원테이블로 부서 테이블에서 부서아이디가 일치하는 경우, 부서아이디, 부서이름, 직원 이름 조회하기 SELECT D.DEPARTMENT_ID, D.DEPARTMENT_NAME, E.FIRST_NAME, E.LAST_NAME FROM HR_DEPARTMENTS D, HR_EMPLOYEES E WHERE D.DEPARTMENT_ID = E.DEPARTMENT_ID 4. Non-Equi Join(비등가조인) 두 개의 테이블간의 칼럼값들이 정확하게 일치하는 않는 경우에 사용(범위를 이용해 등급을 나눌때 용이). = 이 아닌 다른 연산자 들을 사용한다. 5. Outer Join(Left/Right Join) 조건을 만족하지 않는 데이터들도 보고싶을 때 사용한다 equi join을 사용하면 칼럼값이 일치하는 데이터만 볼 수 있지만, outer join을 사용하면 다른 데이터 들도 볼 수 있음 (+) 연산자를 쓰거나, 보고자하는 테이블이 왼쪽이면 Left, 오른쪽이며 Right를 명시에 사용한다. 5.1 예제 1 2 //직원 테이블과 부서테이블에서 부서아이디가 일치하는 경우 부서아이디 별로 묶어서 개수를 보여주고 부서아이디로 오름차순 정렬, 일치하는 부서가 없는 경우도 보여주기 SELECT D.DEPARTMENT_ID, COUNT(*) FROM HR_EMPLOYEES E RIGHT JOIN HR_DEPARTMENTS D ON E.DEPARTMENT_ID = D.DEPARTMENT_ID GROUP BY E.DEPARTMENT_ID ORDER BY DEPARTMENT_ID ASC 6. Self Join 하나의 테이블에서 두 개의 테이블을 Join하는 것처럼 사용하는 Join alias명을 지정해서 구별해 준다 6.1 예제 1 2 //각 사원의 매니저가 실제로 직업이 매니저인 경우 사원아이디, 이름, 매니저아이디, 매니저의 사원아이디, 매니저 이름, 매니저 직업아이디를 출력하라 SELECT E1.EMPLOYEE_ID, E1.FIRST_NAME, E1.MANAGER_ID, E2.EMPLOYEE_ID, E2.FIRST_NAME, E2.JOB_ID FROM HR_EMPLOYEES E1, HR_EMPLOYEES E2 WHERE E1.MANAGER_ID = E2.EMPLOYEE_ID AND E2.JOB_ID LIKE '%MAN'

시간초과가 계속해서 나는 것은 최적화 하면서 근근이 풀긴했는데, 속도가 많이 느리다. 자바로 풀 사람들 중에서 꼴등임 ㅎ 다른 정답자들의 풀이를 보니, 나는 에드몬드 카프 알고리즘을 이용해 풀었지만 빠르게 푼 사람들은 “디닉 알고리즘"이라는 것을 이용해서 풀었다. ...

어제 못 풀고 오늘에서야 푼 문제 정점을 1번만 지나는 조건을 만족하기 위해 정점을 분할하고 분할된 정점사이에 용량의 1의 간선을 추가해야 한다. 주의해야 할 것은 입력되는 간선들을 분할될 정점을 고려해 잘 이어주는 것이다. ...

원본과 동일한 서명값을 만들어 내는 메시지를 구하는 문제입니다. 48bit의 해쉬함수가 사용되는데 함수를 분석해보면 16bit의 값만을 갖는 걸을 알 수 있습니다. ...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 /** * */ import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; /** * @author jaeji * */ class edge{ int to; int flow; int cap; edge rever; edge(){ this(0,0,0,null); } edge(int ar_to, int ar_flow, int ar_cap, edge ar_rever){ to = ar_to; flow = ar_flow; cap = ar_cap; rever = ar_rever; } int residu() { return cap-flow; } void addflow(int ar_flow) { flow+=ar_flow; rever.flow -=ar_flow; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) ); //BufferedReader br = new BufferedReader( new FileReader("input.txt" ) ); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[] prev = new int[402]; ArrayList[] adj = new ArrayList[402]; Queue<Integer> q = new LinkedList<Integer>(); int total = 0; for(int i=0;i<402;i++) { adj[i] = new ArrayList<edge>(); } for(int i=0;i<n;i++) { edge temp_edge = new edge(i,0,1,null); edge temp_rever_edge = new edge(400,0,0,temp_edge); temp_edge.rever = temp_rever_edge; adj[400].add(temp_edge); adj[i].add(temp_rever_edge); } for(int i=200;i<200+m;i++) { edge temp = new edge(401,0,1,null); edge temp_rever_edge = new edge(i,0,0,temp); temp.rever = temp_rever_edge; adj[i].add(temp); adj[401].add(temp_rever_edge); } int no = 0; int temp = 0; for(int i=0;i<n;i++) { st = new StringTokenizer(br.readLine()); no = Integer.parseInt(st.nextToken()); for(int j=0;j<no;j++) { temp = Integer.parseInt(st.nextToken())+199; edge temp_edge = new edge(temp,0,1,null); edge temp_rever_edge = new edge(i,0,0,temp_edge); temp_edge.rever = temp_rever_edge; adj[i].add(temp_edge); adj[temp].add(temp_rever_edge); } } int curr = 0; edge next = null; int S = 400; int E = 401; while(true) { edge[] path = new edge[402]; Arrays.fill(prev, -1); q.clear(); q.add(S); curr = 0; next = null; while(!q.isEmpty()) { // 소스에서 흐를수 있는 유량찾기 curr = q.poll(); for(int i=0;i<adj[curr].size();i++) { next = (edge) adj[curr].get(i); if(next.residu() > 0 && prev[next.to] == -1) { q.add(next.to); prev[next.to] = curr; path[next.to] = next; if(next.to == E) break; } } } if(prev[E] == -1) break; // 경로를 탐색 한 후 싱크로 가는 경로가 없는 경우 for(int i=E;i!=S;i=prev[i]) { path[i].addflow(1); } total += 1; } System.out.println(total); } }

주어진 두 정수 범위내의 소수를 구하는 문제입니다. 에라토스테네스의 체 라는 것을 사용해 구합니다. 개념적으로 주의해야 할 것은 소수 판별하는 것과 다릅니다. 에라토스테네스의 체 는 특점 범위의 소수를 구할때 쓰는 알고리즘입니다. ...

주어지는 수들 중에서 소수의 개수를 출력하는 문제입니다. 소수를 판별하는 가장 기초적인 방법인 2~n-1 까지 나눠지는지 확인해서 판별하면 됩니다. 또한 $$\sqrt{n}$$ 까지 나눠지는 약수가 없으면 소수 라는 성질을 이용해 계산량을 줄일 수 있습니다. ...

두 자연수의 최대 공약수와, 최소 공배수를 출력하는 문제입니다. 유클리드 호제법을 이용해 최대공약수를 구하고 최대공야수를 이용해 최소 공배수를 구하면 됩니다. 최소 공배수만 구하라고 하는 경우에도 최대공약수를 구하여 최소공배수를 구하는 것이 쉽습니다. ...

피보나치 수를 구하는 가장 기초적인 알고리즘입니다. $$ F_n = F_{n-1} + F_{n-2} (n>=2) $$ 점화식을 그대로 구현하여 재귀적으로 풀어내면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 /** * */ import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; /** * @author jaeji * */ public class Main { static int fibonacci(int no) { if(no==0) return 0; else if(no==1) return 1; else return fibonacci(no-1)+fibonacci(no-2); } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) ); //BufferedReader br = new BufferedReader( new FileReader("input.txt" ) ); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int result = fibonacci(n); System.out.println(result); } }