seungineer

결론Nullable field에 NULL 값이 하나라도 포함되는 경우, WHERE 'A' NOT IN (nullable field)의 경우 항상 false로 평가된다. 이에 Nullable field에서 'A'가 존재하지 않는 경우에 대해 조건을 걸고자 하는 경우 WHERE NOT EXISTS (nullable field에 NULL을 제외한 'A'인 경우의 서브 쿼리)의 형태로 구현해야 한다. 서브쿼리에는 'A'가 존재하지 않을 시 아무 것도 존재하지 않게 되고, NOT EXISTS()는 true가 된다. 3중 논리MySQL의 3중 논리에 의해서 'True', 'False', 'Unknown' 중 하나로 논리가 결정된다. 가령 WHERE 'A' IN ('A', NULL, 'B') 라고 하면, 서브쿼리에 ..

17387번: 선분 교차 2 boj.ma문제 요약2차원 좌표 평면 위에 두 선분 L1, L2가 주어졌을 때 두 선분이 교차하는지 아닌지 구분하면 된다.접근어떤 선분의 식을 f(x, y)라고 가정하자. 해당 선분 위에 있는 점 (x1, y1)을 함수에 대입하면 0이 나온다. 즉, f(x1, y1) = 0이다. 그러면 선분보다 '위에 있는 점'을 대입하면 어떻게 될까? '위'의 관점에 따라서 양수 또는 음수가 나온다. 이를 응용하면 선분 '위'에 있는 점과 선분 '아래'에 있는 점인지 부호를 통해 알 수 있다. 이를 부호 판별법이라고 한다.해당 성질을 알고 있으면 쉽게 접근할 수 있다. 두 선분이 교차한다는 뜻은 어떤 한 선분에 대해서 다른 선분의 점 두 개가 위, 아래 영역에 위치되고 또 다른 한 선분에 ..

9466번: 텀 프로젝트 boj.ma문제 요약각각의 학생이 가리키는 타 학생 번호 정보를 통해 무리(cycle)가 만들어지지 않는 학생의 수를 구한다. 가령 A ➡️ B ➡️ C ➡️ D ➡️ E ➡️ C 순서로 지명하는 경우 무리가 만들어진 학생은 C, D, E이고, 무리가 만들어지지 않은 학생은 A, B이다. 가리키는 정보를 순서대로 따라가기 위해 DFS 구조를 사용하기로 하였다. 동시에 DFS 함수의 반환 값(결과)을 통해 무리 지어졌는지 여부를 저장할 수 있다.DFS 구성DFS를 어떻게 구성할 수 있을까?위 이미지 처럼 cycle이 형성되면 형성되는 순간의 학생을 무리 친구들끼리 갖는다. DFS의 반환 값으로 '도착' 했을 때의 학생을 반환하면 되는 것이다. 이후 DFS가 반환(파란 화살표)되면서..

1508번: 레이스 boj.ma문제를 간단하게 표현하면 가장 가까운 심판 간 거리가 최대가 되도록 배치하는 문제이다. 최대한 듬성듬성 배치하는 것이다. 최대한 '듬성듬성' 배치하기 위해 '심판 간 거리에 대해 그리디 전략'을 취할 수 있다. 심판의 거리를 최대한 넓혀서 배치해 보고, 문제 조건에 맞지 않으면 좁혀서 배치해 보고, 또다시 넓혀 보고, ... 반복하며 정답을 찾을 수 있다. 즉, 이분탐색으로 경계(심판 간 최대 거리)를 설정한 후에 해당 경계에서 몇 명의 심판을 배치할 수 있는지 배치해보는 것이다.심판 배치 로직출력할 때는 예제와 같이 심판을 세울 곳에는 1을, 세우지 않을 곳에는 0을 출력한다. 만약 정답이 여러개일 경우에는 사전순으로 가장 늦는 것을 출력한다.문제의 출력 조건을 살펴보면 ..

2141번: 우체국 boj.ma문제의 조건첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.N이 10^5으로 O(N^2) 이하의 알고리즘만 적용 가능함을 알 수 있다.만약 O(N^2) 알고리즘이 적용 가능하다면 모든 N에 대해 우체국을 세워서 해당 우체국에서 마을까지의 거리를 구하면 쉽게 '거리의 합이 최소가 되는 위치'를 찾을 수 있다. 문제 접근임의의 우체국 위치를 가정하고 식을 세워보면 아래와 같은 형태임을 알 수 있다. 마을은 (1, 0), (2, 0), (3, 0)에 위..

다익스트라로 최단 거리를 구하는 방식에서 경로 정보를 추가하는 로직! 11779번: 최소비용 구하기 2 boj.ma 다익스트라 알고리즘은 ‘특정 시작 지점’에서 ‘어떤 마지막 지점’으로 최소 비용으로 이동할 때의 '최소 비용'을 구할 수 있는 알고리즘이다. 그렇다면 경로 정보를 어떻게 추가할 수 있을까?다익스트라에서 heap queue를 pop 했을 때 나오는 정보는 최단 거리 관련 정보라고 할 수 있다. 즉, 유의미한 정보이다. 여기에 경로 정보가 포함되도록 해야 한다.path = [st]hq.heappush(qu, [0, st, path])while qu: 해당 코드를 보면 path 정보가 heap queue에 포함되는 것을 알 수 있다. 다익스트라 알고리즘을 위한 첫 heap queue부터 경로 정..

부분 수열 후보군의 '범위'를 최대한 넓게 갖도록 욕심부리는 문제이다.  30805번: 사전 순 최대 공통 부분 수열 boj.ma 문제 요약수열 A와 수열 B가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하여야 한다. 여기서 사전 순에 대한 정의는 문제에서 내린다. 정리하면, 여러 부분 수열들 중에서 1️⃣ 가장 index가 낮은 수가 큰 것이 사전 순으로 나중이다. 만약 이 값이 같다면 2️⃣ 그 다음 index 값을 순서대로 비교하여 큰 수가 사전 순으로 나중이다. 마지막으로 3️⃣ 부분 수열의 길이가 더 긴 것이 사전 순으로 나중이다.요약하면 부분 수열 중에서 큰 수가 많은 것이 사전 순으로 나중이다! 문제를 풀 때도 이 관점에서 생각해보면 큰 수부터 찾아야 한다는 감이 온다. ..

2차원 배열 내 수를 특정 형태에 맞게 회전시키는 로직을 for문과 while문을 적절히 활용하여야 하는 문제이다. 17144번: 미세먼지 안녕! boj.ma문제요약숫자로 표현된 먼지들은 사방으로 퍼지며 그 크기가 퍼진 만큼 줄어든다. 또한, 숫자 -1로 표현된 공기 청정기로 먼지가 들어가면 해당 먼지는 사라지게 된다. 공기 청정기가 작동하여 먼지의 위치를 이동 시키는 특정 패턴으로 정해져 있다. 몇 달 전에 풀어보려고 시도하였으나 실패했었던 문제이다. 실패의 원인은 공기청정기에 의해서 먼지가 이동하는 것을 어떻게 구현해야 할지 감이 오지 않았기 때문이다. 공기청정기에 의해서 먼지가 어떻게 움직이게 되는지가 해당 문제의 핵심이라고 할 수 있다. 무조건 공기청정기에 의해 순환 기류가 형성된다.문제 조건을 ..

‘flag를 어디에 세울 것인지’에 따라 시간 복잡도가 N의 제곱만큼 차이가 났다. 현재 문제에서 N은 최대 100이므로 TLE가 발생하는지 안 하는지 차이를 내는 중요한 요인이었다. 2638번: 치즈 boj.ma문제 요약숫자 1로 표현된 치즈가 몇 번의 연산 후에 모두 녹을지 구하는 문제이다. 치즈(숫자 1)는 주변에 숫자 0이 2개 이상 있는 경우 해당 연산에서 녹게 된다. 다만, 숫자 0 중 치즈에 둘러싸인 것은 제외한다는 조건이 있어 다소 까다롭다.1트: counting되면 안 되는 영역을 표시한다숫자 1이 모든 숫자 0과 맞닿는 경우를 센다면 쉬운 문제였겠지만, 숫자 1로 만들어진 영역 내에 포함된 숫자 0은 counting 하지 않아야 하여 까다로운 문제가 되었다.숫자 1로 만들어진 영역 내의..

오늘 백준 17298 '오큰수' 문제를 풀면서 드디어(..!) 스택 자료 구조를 사용해야 하는 상황임을 알 수 있는 직관을 얻을 수 있었다. 재귀, dynamic programming에서 이런 직관을 얻고, PS 역량이 약간 올라갔다고 체감했던 터라 기분 좋은 깨달음이었다.스택 자료 구조는 양파 껍질 같은 상황에서 쓰인다.정글 과정 중 코치님께서 하신 말씀이다. 그때 당시에는 백준 9012 '괄호'와 같은 문제를 풀면서 어렴풋이 '문제가 양파 같긴 하다' 정도로 생각하고 끝났다. 그런데 사실은 더 큰 뜻이 있었다.양파 '껍질'이라, 양파 안은 관심이 없다!9012 '괄호' 문제와 같이 올바르게 괄호가 닫혔는지 확인할 때를 가정한다. (()(())) 이 case의 경우 가장 마지막에 빨간색 ')'으로 닫히..