답은 알고리즘 뿐이야!

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/59044 ANIMAL_INS 테이블과 ANIMAL_OUTS 테이블이 주어졌을때, 아직 입양을 못 간 동물 중, 가장 오래 보호소에 있었던 동물 3마리의 이름과 보호 시작일을 조회하는 SQL문을 작성하는 문제입니다. SELECT I.NAME, I.DATETIME FROM ANIMAL_INS I LEFT OUTER JOIN ANIMAL_OUTS O ON O.ANIMAL_ID = I.ANIMAL_ID WHERE O.ANIMAL_ID IS NULL ORDER BY I.DATETIME ASC LIMIT 3 INS 테이블을 왼쪽, OUTS 테이블을 오른쪽으로 두고 ANIMAL_ID 를 기준으로 LEFT OUT..

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/59043 ANIMAL_INS 테이블과 ANIMAL_OUTS 테이블이 주어졌을 때 보호시작일보다 입양일이 더 빠른 동물의 아이디와 이름을 조회하는 SQL문을 작성하는 문제이다. (결과는 보호 시작일이 빠른 순으로 조회) SELECT O.ANIMAL_ID, O.NAME FROM ANIMAL_INS I INNER JOIN ANIMAL_OUTS O ON I.ANIMAL_ID = O.ANIMAL_ID WHERE I.DATETIME > O.DATETIME ORDER BY I.DATETIME ASC INS 테이블과 OUTS 테이블을 ID 기준으로 INNER JOIN 해서 입양 나간 동물들을 조회합니다. 거기서 ..

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/59042 ANIMAL_INS 테이블과 ANIMAL_OUTS 테이블을 조인하여 입양간 기록은 있는데 보호소로 들어온 기록은 없는 동물들의 ID와 이름을 ID순으로 조회하는 문제입니다. SELECT O.ANIMAL_ID, O.NAME FROM ANIMAL_INS I RIGHT OUTER JOIN ANIMAL_OUTS O ON I.ANIMAL_ID = O.ANIMAL_ID WHERE I.ANIMAL_ID IS NULL INS를 왼쪽 OUTS를 오른쪽으로 두고 RIGHT OUTER JOIN을 합니다. 그러면 RIGHT 인 OUTS 테이블에 관해서만 데이터 조회를 하게 되고 거기서 INS와 OUTS에서 ID..

문제 출처 : https://www.acmicpc.net/problem/2207 풀이 : 2-SAT 문제입니다. i번째 라운드에서 원장선생님이 무엇을 냈는지를 나타내는 변수를 Xi라 할때, 원장선생님은 바위 또는 가위만 낼수 있으므로 바위를 ㄱXi, 가위를 Xi라 두고 절을 구성한 후 CNF 가 TRUE가 되면 "^_^", FALSE가 되면 "OTL"을 출력하면 되는 문제입니다.

문제 출처 : https://www.acmicpc.net/problem/14725 풀이 : 문자열로 트리를 구성하는 문제입니다. 문제에서 주어지는 인풋 대로 트리를 채워나가시되 이진 트리가 아닌 N진 트리로 구성하시면 됩니다. 저는 정렬을 하기 위해 처음부터 사전순으로 비교하여 현재 인덱스의 스트링이 사전순으로 뒤에있으면 그 자리에 삽입하고 나머지를 뒤로 푸쉬해주는 방식으로 하였습니다.

문제 출처 : https://www.acmicpc.net/problem/4354 풀이 : KMP의 Fail 함수를 이용해서 해결하는 문제입니다. abababab 라는 문자열이 있다고 가정해봅시다. 문자열의 길이는 len이라고 표현 하겠습니다. 이 문자열은 ab가 4번 반복되는 문자열입니다. 이 문자열의 Fail 값을 계산한다면 abababab abababab 00123456 이 나옵니다. 이러한 사실에서 우리가 알 수 있는 사실은 반복되는 횟수가 1이 아닌 문자열은 무조건 반복되는 기준이 있는 문자열이기 때문에 최대로 반복되는 문자열을 처음 지나는 순간 그 다음은 Fail 값이 계속 Fail[n] = Fail[n-1] + 1의 형태로 흘러가게 됩니다. 다시 abababab의 Fail값을본다면 최대로 반복..

문제 출처 : https://www.acmicpc.net/problem/1031 풀이 : Maximum Flow 문제입니다. 아래의 조건에 따라 푸시면 됩니다. 1. A팀의 경기수 총합 != B팀의 경기수 총합 => -1 2. A팀의 경기수 총합 != Maximum Flow => -1 3. A팀의 경기수 총합 == Maximum Flow => 사전순 정렬 이문제의 핵심은 3번 사전순 정렬인데 사전순 정렬은 엣지 하나를 고르고 엣지와 동일한 시작점에서 동일한 끝점으로 갈수있는 다른 플로우가 있는지 찾은 후 있으면 엣지의 플로우를 지워주고 경로에 Flow를 흘려주시면 됩니다. 단 찾을때 정렬을 해야하기 때문에 시작점과 끝점의 범위에 주의해야합니다. 만약 인풋이 2 2 1 1 1 1 일때, 1->3, 2->4..

문제 출처 : https://www.acmicpc.net/problem/3640 풀이 : MCMF 문제입니다. 1 을 source, V 를 sink로 잡고 mcmf를 해주시면 되는데 조건중에 정점 중복이 없다라는 말이 있으므로 정점 분할을 하고 V번 정점에서 V ' 번 정점으로 가는 Capacity를 2로, S번 정점에서 S ' 번 정점으로 가는 Capacity를 충분히 준 후 MCMF를 돌리시면 됩니다. 아래는 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 47 48 49 50 51 ..

문제 출처 : https://www.acmicpc.net/problem/2367 풀이 : 네트워크 플로우 (Maximum Flow) 문제입니다. 파티에 N명의 사람이 오고 D개의 음식을 준비해야하는데 한 사람당 음식을 K개 준비할 수 있고 같은 음식은 1개만 준비할 수 있습니다. 따라서 다음과 같이 모델링 할 수 있습니다. 1. Source에서 사람으로 K만큼의 Capacity를 가진 Edge를 연결 2. 사람에서 각 사람당 준비할 수 있는 음식으로 1만큼의 Capacity를 가진 Edge를 연결 (한개의 음식은 한사람당 하나만 들고갈수 있으므로) 3. 각 음식에서 Sink로 가져올 수 있는 갯수만큼의 Capacity를 가진 Edge를 연결 예제의 경우를 네트워크 플로우로 모델링 하면 아래와 같은 모형이..

문제 출처 : https://www.acmicpc.net/problem/13511 풀이 : LCA 문제 입니다. 첫번째 쿼리를 처리하기 위해선 아래와 같이 LCA를 구하기 위해 전처리를 할때 cost 값도 같은 점화식으로 구해주시면 되고, for (int i = 1; depth[ni] > 1 > b >> c; if (a == 1) cout