Posts

중요한 간선을 찾는 코드에서 prev2[next2.to] 가 되어있어야 하는데 prev2[curr2]로 되어 있는 것을 발견하지 못해 푸는데 오래 걸린 문제이다. 중요한 간선의 여부는 최대유량은 찾은 후에 입력 간선들 중에 u->v로 유량을 흘릴수 없는 경우 중요한 간선이라고 판단하였다. ...

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 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 -- 부서번호가 60인 직원의 사원번호,이름,월급을 출력하라 SELECT EMPLOYEE_ID, FIRST_NAME, SALARY FROM HR_EMPLOYEES WHERE DEPARTMENT_ID=60 -- 사원번호가 127인 사람의 이름, 입사일, 부서번호를 출력하라 SELECT FIRST_NAME, HIRE_DATE, DEPARTMENT_ID FROM HR_EMPLOYEES WHERE EMPLOYEE_ID=127 -- 이름의 JOHN인 사람의 모든 정보를 출력하라 SELECT * FROM HR_EMPLOYEES WHERE FIRST_NAME='JOHN' -- 입사일이 97년 1월 5일인 사원의 이름, 부서번호, 월급을 출력하라 SELECT FIRST_NAME, DEPARTMENT_ID, SALARY FROM HR_EMPLOYEES WHERE HIRE_DATE='1997-01-05' -- 직원이 매니저가 아닌 사람의 모든 정보를 출력하라 SELECT EMP1.* FROM HR_EMPLOYEES EMP1 INNER JOIN HR_JOBS JOB1 ON EMP1.JOB_ID = JOB1.JOB_ID WHERE JOB1.JOB_TITLE LIKE '%MANAGER%' -- 입사일이 97년 1월 2일 이후인 사원의 정보를 출력하라 SELECT * FROM HR_EMPLOYEES WHERE HIRE_DATE>'1997-01-02' -- 급여가 6000 이상인 사람의 이름, 급여, 부서번호를 출력하라 SELECT FIRST_NAME,SALARY,DEPARTMENT_ID FROM HR_EMPLOYEES WHERE SALARY>6000 -- 부서번호가 80 이상인 사원의 모든 정보를 출력하라 SELECT * FROM HR_EMPLOYEES WHERE DEPARTMENT_ID>=80 -- 이름이 k로 시작하는 사람보다 높은 이름을 가진 사원의 정보를 출력하라 SELECT * FROM HR_EMPLOYEES WHERE FIRST_NAME>'K%' -- 입사일이 97/12/10 보다 먼저 입사한 사람들의 모든 정보를 출력하라 SELECT * FROM HR_EMPLOYEES WHERE HIRE_DATE>'1997-12-10' -- 직원번호가 127보다 작거나 같은 직원의 입사번호와 이름을 출력하라 SELECT EMPLOYEE_ID, FIRST_NAME FROM HR_EMPLOYEES WHERE EMPLOYEE_ID<=127 -- 입사일이 97/01/01보다 늦고 00/12/07보다 빠른 사원의 이름,월급,부서번호를 출력하라 SELECT FIRST_NAME,SALARY,DEPARTMENT_ID FROM HR_EMPLOYEES WHERE HIRE_DATE BETWEEN '1997-01-01' AND '2000-12-07' -- 급여가 5000보다 크고 8000보다 작은 사람의 이름,직업,급여를 출력하라 SELECT FIRST_NAME, JOB_ID, SALARY FROM HR_EMPLOYEES WHERE SALARY BETWEEN 5000 AND 8000 -- 사원번호가 120~130 이외의 사원의 모든 정보를 출력하라 SELECT * FROM HR_EMPLOYEES WHERE NOT EMPLOYEE_ID BETWEEN 120 AND 130 -- 이름의 B와 J 사이인 직원의 정보를 출력하라 SELECT * FROM HR_EMPLOYEES WHERE FIRST_NAME BETWEEN 'B' AND 'J' -- 입사일 97년 이외에 입사한 사람의 정보를 출력하라 SELECT * FROM HR_EMPLOYEES WHERE YEAR(HIRE_DATE) != 1997 -- 직업이 MANAGER 와 SALEMAN인 사람인 모든 정보를 출력하라 SELECT * FROM HR_EMPLOYEES EMP1 INNER JOIN HR_JOBS JOB1 ON EMP1.JOB_ID = JOB1.JOB_ID WHERE JOB1.JOB_TITLE LIKE '%MANAGER%' OR JOB1.JOB_TITLE LIKE '%SALEMAN%' -- 부서번호 60,90을 제외한 사원의 이름, 부서번호, 사원번호를 출력하라 SELECT FIRST_NAME,DEPARTMENT_ID,EMPLOYEE_ID FROM HR_EMPLOYEES WHERE NOT DEPARTMENT_ID IN (60,90) -- S로 시작하는 사원의 사원번호, 이름, 입사일, 부서번호를 출력하라 SELECT EMPLOYEE_ID, FIRST_NAME, HIRE_DATE, DEPARTMENT_ID FROM HR_EMPLOYEES WHERE FIRST_NAME LIKE 'S%' -- 입사일이 2000년도인 직원의 정보를 출력하라 SELECT * FROM HR_EMPLOYEES WHERE YEAR(HIRE_DATE) = 2000 -- 이름이 J로 시작하고 마지막 글자가 N인 사원의 정보를 출력하라 -- 조건1. 이름은 4자리 이다 SELECT * FROM HR_EMPLOYEES WHERE FIRST_NAME LIKE 'J__N' -- 첫번째 문자를 관계없고, 두번째 문자가 A인 직원의 정보를 출력하라 SELECT * FROM HR_EMPLOYEES WHERE FIRST_NAME LIKE '_A%' -- 커미션이 NULL인 사원의 정보를 출력하라 SELECT * FROM HR_EMPLOYEES WHERE COMMISSION_PCT IS NULL -- 커미션이 NULL이 아닌 사원의 정보를 출력하라 SELECT * FROM HR_EMPLOYEES WHERE COMMISSION_PCT IS NOT NULL -- 부서번호가 100이고 급여가 5000 이상인 직원의 이름,부서,월급을 출력하라 SELECT FIRST_NAME, DEPARTMENT_ID, SALARY FROM HR_EMPLOYEES WHERE DEPARTMENT_ID = 100 AND SALARY >= 5000 -- 첫글자가 K로 시작하거나 부서번호가 30인 사원의 사원번호, 이름, 부서번호를 출력하라 SELECT EMPLOYEE_ID, FIRST_NAME, DEPARTMENT_ID FROM HR_EMPLOYEES WHERE FIRST_NAME LIKE 'K%' -- 급여가 5000이상이고 부서가 100인 사원중 직원이 MANAGER인 사원의 정보를 출력하라 SELECT * FROM HR_EMPLOYEES EMP1 INNER JOIN HR_JOBS JOB2 ON EMP1.JOB_ID = JOB2.JOB_ID WHERE SALARY >5000 AND DEPARTMENT_ID = 100 AND JOB2.JOB_TITLE LIKE '%MANAGER%' -- 부서번호가 100인 사원을 사원번호순으로 정렬 SELECT * FROM HR_EMPLOYEES WHERE DEPARTMENT_ID = 100 ORDER BY EMPLOYEE_ID ASC -- 급여 순서가 많은 순으로 정렬 SELECT * FROM HR_EMPLOYEES ORDER BY SALARY DESC -- 부서번호로 오름차순정렬후 급여 내림차순정렬 SELECT * FROM HR_EMPLOYEES ORDER BY DEPARTMENT_ID ASC , SALARY DESC -- 부서번호 내림차순, 이름 오름차순, 급여 내림차순 출력 SELECT * FROM HR_EMPLOYEES ORDER BY DEPARTMENT_ID DESC, FIRST_NAME ASC, SALARY DESC -- 사원의 이름, 급여, 커미션 금액, 총액을 구하여 총액 내림차순 출력 -- 커미션이 NULL인 사람은 제외 SELECT FIRST_NAME, SALARY, COMMISSION_PCT*SALARY, SALARY+COMMISSION_PCT*SALARY FROM HR_EMPLOYEES WHERE COMMISSION_PCT IS NOT NULL -- 50번 부서의 모든 직원들에게 13%트의 보너스를 지부라기로 했다. 이름, 급여, 보너스, 금액, 부서번호를 출력하라 SELECT FIRST_NAME, SALARY, SALARY*0.13, SALARY*1.13, DEPARTMENT_ID FROM HR_EMPLOYEES WHERE DEPARTMENT_ID = 50 -- 60번 부서의 연봉을 계산하여 이름, 부서번호, 급여, 연봉을 출력하라 -- 연말에 150%의 보너르를 지급한다 SELECT FIRST_NAME, DEPARTMENT_ID, SALARY, 13.5*SALARY FROM HR_EMPLOYEES WHERE DEPARTMENT_ID = 60

오라클 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}$$ 까지 나눠지는 약수가 없으면 소수 라는 성질을 이용해 계산량을 줄일 수 있습니다. ...