Byeo

목차 개요 설명 코드 개요 시청자가 어떠한 패턴으로 영상을 감상하는지 정보가 주어질 때, 어느 구간에서 가장 좋은 광고 효과를 낼 수 있는지 찾아내는 문제입니다. 이 문제의 Key point는 00:00:00 ~ 99:59:59 의 시간을 하나의 배열 (0 ~ 359999)로 표현하고, $O(N)$의 복잡도로 결과를 찾아내는 것입니다. 사용자의 play time이 주어지면 0 부터 359999 사이의 값으로 환산 한 뒤, 각 배열 원소 (1초)마다 총 몇 명이 시청하는지 저장합니다. 이후, 광고 삽입 시간을 0부터 359999까지 차례로 조사하면서 총 시청 인원이 가장 많은 구간을 구하면 되겠습니다. 설명 다음과 같이 간단한 예제와 그림을 통해서 살펴보도록 하겠습니다. 재생 가능한 시간 0 : 00 ~ ..

목차 개요 설명 코드 개요 어떤 tree가 주어졌을 때, 임의의 node에서 자신 혹은 자식 노드들 중에서 하나만 선택하면서 그 선택의 비용의 최솟값은 얼마인가를 구하는 문제입니다. 이 문제는 Tree DP인데, 특정 노드를 선택하는 Tree DP 특징 중에 하나로는 자신의 노드가 선택 되었는지, 안되었는지 구분해서 구하는 문제가 많습니다. 각각의 배열을 dpYes (dpYes[i]의 값은 i번째 node의 child를 모두 계산을 끝낸 뒤, 자신이 선택 되었을 때 그 비용) dpNo (dpNo[i]의 값은 i번째 node의 child를 모두 계산을 끝낸 뒤, 자신이 선택되지 않았을 때 그 비용) 로 구분하여 구하면 되겠습니다. 이 때, dpYes는 자식들을 순회하면서 min(dpYes[child], d..

목차 개요 설명 코드 개요 정확성과 효율성을 동시에 체크하는 문제입니다. 무지와 어피치는 같이 택시를 합승해 어느 지점까지 이동한 뒤에, 각자 개인 택시를 이용하여 집으로 귀가합니다. 시점은 동일하고 중간 경유지까지 함께 간 뒤에 헤어져 각자의 목적지로 향하는 방식입니다. 따라서 직관적으로 (출발지 → 경유지), (경유지 → 무지의 집), (경유지 → 어피치의 집) 의 합이 최소가 되도록 하는 "경유지"를 구한 뒤, 비용을 계산하면 됩니다. $$Answer =min( d[S,\ l]\ +\ d[l, \ A]\ +\ d[l,\ B])$$ 여기서 $l$은 경유지 입니다. 플로이드 워셜을 사용하면 모든 시점 → 종점의 비용을 계산할 수 있습니다. 그러나 시간복잡도는 $O(V^3)$으로 상당한 시간복잡도를 지니..

목차 개요 설명 코드 개요 이 문제는 효율성까지 평가하는 문제입니다. 쿼리에 (코테 참여 언어, 지원 직군, 지원 경력, 선호하는 소울푸드)를 구분하여 입력 받고 있으며, 다음으로 점수를 입력 받아 해당 점수 이상의 사람이 몇 명 있는지 반환하는 문제입니다. 설명 제가 구현한 것은 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가지 ..

목차 개요 코드 설명 코드 개요 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..