seungineer

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로 만들어진 영역 내의..

알고리즘 문제를 풀이한 후에 구글링 해보며 효과적인 풀이었는지 항상 확인한다."12904 파이썬" 키워드로 구글링 하면 대부분 reverse(), array slice를 사용한 풀이 밖에 없어서 풀이의 다양성을 추가하고자 투 포인터 풀이에 대해 작성한다.Intuition1. S를 T로 변환 가능? ➡️ T를 S로 변환 가능?문제에서는 S를 T로 만들기 위해 '문자열의 뒤에 A를 추가'하거나 '문자열을 뒤집고 뒤에 B를 추가'할 수 있다고 한다. 이 두 방법을 이용해 S를 T로 만들 수 있는지 확인하면 된다.문자열의 뒤에 A 혹은 B가 있을 때, A가 있다면 문자열에 곧바로 추가된 것이고 B가 있다면 뒤집혀서 추가되었다고 생각할 수 있다. 즉, 만들어진 결과를 보고 이전 상태를 생각할 수 있으므로 T를 S..

RB tree는 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)의 한 종류로, 검색, 삽입, 삭제 등의 동작을 최악의 경우에도 O(log n) 내에 처리할 수 있도록 설계되었다. RB tree는 각 노드가 빨강 또는 검정의 색깔을 가지며, root부터 leaf(NIL)까지의 모든 경로에 대해 블랙 노드의 수가 동일하게 유지되도록 규칙을 적용하여 균형을 맞춘다. RB tree를 사용하는 이유는 데이터의 삽입, 삭제, 검색 작업 시 '항상 균형 상태를 유지'함으로써, 트리의 높이가 최소한으로 유지되어 효율적인 시간 복잡도를 보장한다. Binary Search Tree란, 정렬된(ordered, or sorted) binary tree이며 노드는 2개의 서브트리를 가질 ..