Byeo

목차 개요 설명 코드 개요 정확성과 효율성을 동시에 체크하는 문제입니다. 무지와 어피치는 같이 택시를 합승해 어느 지점까지 이동한 뒤에, 각자 개인 택시를 이용하여 집으로 귀가합니다. 시점은 동일하고 중간 경유지까지 함께 간 뒤에 헤어져 각자의 목적지로 향하는 방식입니다. 따라서 직관적으로 (출발지 → 경유지), (경유지 → 무지의 집), (경유지 → 어피치의 집) 의 합이 최소가 되도록 하는 "경유지"를 구한 뒤, 비용을 계산하면 됩니다. $$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가지 ..

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

이 포스트는 [iovisor-bcc tutorial]을 참고하였습니다. 목차 Lesson 1. Hello world Lesson 2. sys_sync() Lesson 3. hello_fields.py Lesson 4. sync_timing.py Lesson 5. sync_count.py Lesson 6. disksnoop.py Lesson 1. Hello world bcc를 빌드 하면, examples/hello_world.py가 존재합니다. sudo ./examples/hello_world.py 위와 같이 실행하고 다른 session에서 process를 생성하는 명령어를 수행하면 아래와 같이 출력되는 것을 확인할 수 있습니다. ./a.out 은 간단히 fork를 하나 실행하는 프로그램입니다. 이 때 역..

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

Space & Tab 여타 editor가 그렇듯, vim도 tab은 여러 개의 space를 대략 8개정도로 묶어서 표기해줍니다. (환경마다 다를 수 있음) 그런데 tab이 너무 많이 쓰이는 코드의 경우, 다음처럼 가독성이 떨어지는 문제가 발생합니다. 이를 위해 다음 명령어를 통해 tab의 space 개수를 조절할 수 있습니다. set tabstop=4 다음은 기본적으로 tabstop이 8인 코드입니다. 사실 이 정도도 괜찮지만, tab depth가 더 많아지는 경우 가독성이 현저히 낮아질 수 있습니다. 여기서 tabstop을 4로 바꿔보면 위와 같이 가독성이 조금 더 향상된 걸 볼 수 있습니다. set softtabstop=4 tabstop은 시작 당시에 있던 tab에만 적용이 된다면, softtabst..

목차 개요 요약 개요 설명 코드 테스트 케이스 개요 요약 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..

목차 개요 설명 한계 코드 개요 해당 문제는 배열이 주어져 있을 때, 특정 부분의 구간 합을 구하는 문제입니다. 눈여겨 볼 것은 배열이 주어지고 난 뒤, 배열 값이 변하지 않는다는 사실입니다. 이 문제는 첫 index부터 마지막 index까지 부분합을 모두 계산한 뒤, 결과를 저장해서 빼기 연산으로 쉽게 풀 수 있습니다. 즉, DP 문제입니다. 설명 5 3 5 4 3 2 1 1 3 2 4 5 5 백준 예제로 방법을 간단하게 보겠습니다. 배열의 원소 5, 4, 3, 2, 1로 들어온 값을 arr에 저장해 둡시다. 그리고 0번 ~ i번 까지의 배열 합을 sum[i]에 저장해 놓도록 하죠. 처음 sum[0] 은 단순히 arr[0]이 되겠죠. 이제 다음부터 sum[1]은 arr[1] + sum[0], ... s..

목차 코드 해석 안되는 경우 (not working) vim을 사용하다 보면 이전에 편집했던 위치를 기억하는게 편한 경우가 많습니다. 특히, 작성한 코드가 길 때 매우 편해집니다. 코드 이를 위해서는 다음 코드를 ~/.vimrc 에 넣으면 됩니다. autocmd BufReadPost * \ if line("'\"") > 0 && line("'\"")