Byeo

목차 개요 설명 코드 개요 이 문제는 효율성까지 평가하는 문제입니다. 쿼리에 (코테 참여 언어, 지원 직군, 지원 경력, 선호하는 소울푸드)를 구분하여 입력 받고 있으며, 다음으로 점수를 입력 받아 해당 점수 이상의 사람이 몇 명 있는지 반환하는 문제입니다. 설명 제가 구현한 것은 segment tree를 활용한 것입니다. 점수를 제외한 항목들을 살펴보면 총 24개(322*2)의 조합이 나오게 되는데, 이 조합들 각각에 segment tree를 이용해 점수를 log N 타임에 구할 수 있도록 하였습니다. Query중에 '-'와 같은 wildcard는 해당하는 조합의 segment tree들을 조사한 뒤에 합하면 될 것입니다. 예를 들어, ('python', -, 'senior', 'pizza', 100)..

목차 개요 풀이 코드 개요 카카오 2021년 블라인드 채용 2번 문제 메뉴 리뉴얼입니다. 위와 같은 표가 있을 때, 가장 가능성이 높은 세트 메뉴들을 정하는 건데요. 가령, 2개의 메뉴로 이루어진 세트 메뉴를 구성하고 싶을 때, {A, C} 세트는 1번, 2번, 4번, 6번 손님이 주문한 이력이 있으므로 세트 메뉴 구성하기에 좋습니다. 뿐만 아니라, 3개, 4개의 메뉴로 이루어진 세트 메뉴도 다음과 같이 정리해 볼 수 있습니다. 이처럼, 손님들의 주문 이력과 코스 내 메뉴 개수를 입력으로 받아 가장 좋은 세트 메뉴를 구성하여 리턴 하는 것이 이 문제입니다. 풀이 이 문제는 수의 범위가 크지 않고 효율성을 체크하지 않습니다. 최대 20명의 손님이 이력을 남겨주셨고, 한 손님 당 남긴 주문 이력은 10가지 ..

목차 개요 설명 요약 코드 개요 이 문제는 2차원 좌표계에서 어느 직선상의 출발점에서 도착점까지 걸어서 혹은 점프로 가장 빠르게 도착하는 방법을 찾는 문제입니다. 가장 주의해야 할 점은 2차원 상에서 아무렇게 움직일 수 있다는 점입니다. 따라서 점프가 직선상에서만 국한된 것이 아닌, 직선에서 외부로 잠시 나갔다가 다시 도착점으로 점프하는게 최소 비용일 수 있습니다. 그래서 이 문제는 다음과 같이 케이스를 나눠서 풀면 됩니다. 1) 전부 걸어서 가는 경우 2) 처음부터 끝까지 점프해서 도착점에 딱 도착하는 경우 3) 도착점에서 가장 가까운 지점까지 점프한 뒤, 남은 거리는 걸어서 가는 경우 4) 도착점을 넘어서까지 점프를 한 뒤, 남은 거리는 걸어서 가는 경우 위 4가지를 모두 고려해서 계산한 뒤, 최솟값..

목차 개요 코드 설명 코드 개요 2021년 카카오 Blind 채용 첫 문제입니다. 첫 문제답게 간단히 구현하면 되는 문제인데, 최적화 여지를 생각하다가 오히려 한 군데에서 예외를 발생 시켜 버렸었네요. 정규식을 활용한 파이썬 풀이는 [이 포스트] 를 참고하시면 좋을 듯 합니다. 코드 설명 Step 1: 대문자를 소문자로 변경 Python 에서는 기본으로 string type에 lowercase()라는 메서드를 제공해주는데 반해, C++에서는 찾지 못했습니다. 그러나 그 구현이 간단하므로 단순히 for문 돌면서 직접 변경해줬습니다. //step 1 if(tmp >= 'A' && tmp = 'a' && tmp ='0' && tmp 0 && answer[answer.length()-1] == '.' && tm..

목차 개요 요약 개요 설명 코드 테스트 케이스 개요 요약 y좌표가 높은 별부터 시작해서 아래로 sweeping을 합니다. 특정 별 A를 기준으로 좌상단에 별의 개수 $N$, 우상단에 별의 개수 $M$을 각각 segment tree를 통해 구한 후, 곱합니다. $N*M$이 별 A를 기준으로 그릴 수 있는 별자리 개수입니다. $N*M$은 별 A만을 기준으로 삼았을 때입니다. 이를 모든 별에 대해 구해 누적하면 됩니다. 같은 y좌표를 지닌 별들 간에는 별자리를 그릴 수 없습니다. 따라서 같은 y좌표를 가진 별자리들을 batching해서 처리하여야 합니다. 개요 이 문제는 [boj 5419 - 북서풍]을 푸셨다면 쉽게 응용할 수 있습니다. 마찬가지로 이번에는 위에서 아래 방향으로 훑어가면서 등장하는 별들의 x좌..

목차 개요 요약 개요 설명 코드 개요 요약 문제를 풀기위한 key point는 크게 다음과 같습니다. 북서풍을 타고 이동할 수 있는 섬의 쌍을 구하기 위해서는 각 섬마다 자신보다 왼쪽이면서 위에 있는 섬의 개수를 구해서 더하면 됩니다. 섬의 개수가 방대해서 일일이 구하기에는 시간복잡도가 큽니다. 따라서 sweeping과 segment tree를 활용하여 한 방향으로 섬 하나하나 sweep해가야 합니다. 이 과정에서 조건을 만족하는 섬의 개수를 segment tree를 통해 빠르게 알아냄과 동시에 자신을 segment tree에 등록하면 됩니다. Segment tree에 좌표를 사용하기에는 범위가 너무 넓습니다. 따라서 좌표 압축을 한 번 수행해서 20억 개의 원소가 아닌 75,000개의 원소 만으로도 해..

목차 개요 개요 3줄 요약 설명 코드 개요 이 문제는 [boj 2170 - 선 긋기]의 응용입니다. 다만 이를 어떻게 응용해야 할지 생각이 필요한 문제지요. 힌트는 "1) 수상택시가 N명의 모든 인원을 수용할 수 있고, 2) 0에서 출발해서 M까지는 무조건 가야 한다"입니다. 이를 곰곰이 생각해보면 모든 인원을 수용할 수 있으므로, 정방향 승객은 마치 일상의 버스처럼 시점에서 출발하여 승객의 출발점에 도착하면 태워주고, 승객의 목적지에 도착하면 내려주기만 하면 됩니다. 그 이후 종점에서 운행을 종료하죠. 즉, 정방향 승객은 어차피 수상 택시가 가는길이므로 고려할 필요가 없습니다. 이제 역방향을 생각해봐야 합니다. 10 → 5로 가는 승객의 경우 어떻게 하면 좋을까요? 일단 불가피하게 10에 도착한 후 태..

목차 개요 설명 일반화 코드 개요 스위핑 (Sweeping)은 "쓸다" 를 의미합니다. 스위핑 알고리즘 이란 말 그대로 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것이라고 보시면 됩니다. 이 알고리즘은 특정한 자료구조나 구체적인 코드가 있는 것은 아닙니다. 단지, 한쪽 방향에서 시작해서 다른 방향으로 차근차근 해결해 나가는 기법입니다. 이러한 특성 때문에, 보통 좌표와 관련있는 문제가 많이 보이는 듯 합니다. boj 2170 - 선 긋기 이 문제는 일직선상에 여러 길이의 선을 그어, 최종적으로 마지막에 그려져 있는 선의 길이를 구하는 문제입니다. 이 선끼리는 겹칠 수 있기 때문에 그린 길이의 총 합보다 그려져 있는 길이가 작거나 같을 수 밖에 없습니다. 여기서, 그릴 수 있는 좌표의 범..

목차 개요 설명 코드 개요 이 문제는 k 번째 원소를 효율적으로 찾는 문제입니다. 이는 segment tree를 사용하여 구할 수 있습니다. 이 문제는 [boj 12899-데이터 구조]와 굉장히 유사하므로 이를 참고하시면 됩니다. k 번째 원소를 segment tree를 이용해 효율적으로 찾는 방법은 [boj 12899-데이터 구조]를 참고하세요. 이 포스트에서는 k를 어떻게 계산해야 할 지에 대해서만 다루겠습니다. 설명 요세푸스 문제는 수열에서 일정한 간격으로 점프해 가면서 숫자들을 하나씩 빼낸 수열입니다. 백준의 예제 N = 7, K = 3의 경우에는 아래 그림을 보면 이해 하실 수 있으리라 생각합니다. 원소를 지우고 나면, 그 원소부터 다시 k개 만큼 뒤로 이동한 뒤에 또 그 원소를 지웁니다. 만약..

목차 개요 설명 코드 개요 해당 문제는 Segment Tree를 변형하여 사용하는 문제입니다. 이 문제에서 Segment Tree는 기존에 알던 부분 합, 부분 곱, 최소값, 최대값 등을 사용하는 것이 아니라 현재까지 어떤 query들이 어떤 구간에 영향을 주는 지를 저장하기 위해 사용합니다. 즉, 1 a b c 의 query가 들어오면, a ~ b 구간에 c라는 값을 더해야 합니다. 그런데 일일이 a, a+1, a+2, ..., b-1, b 까지 더하는 과정은 시간 소요가 크므로, a ~ b 구간을 담당하는 segment tree node에 일단 저장을 해놓습니다. 다음 2 a 의 query가 들어오면, root node부터 leaf node까지 내려가면서 그 동안 저장되어 있던 segment node..