세그먼트 트리4 2019 카카오 개발자 겨울 인턴십 코딩 테스트 (연습) 2020년 카카오 인턴쉽 코딩 테스트를 하기 전 연습을 위해 19년 겨울 인턴쉽 코딩 테스트를 연습하기로 했다. 그래서 4시간 시간을 재고 5문제를 쭉 풀어보았다. 시간 내에 5문제를 모두 풀 수 있었지만 5번에서 실수도 하고 O(N)의 풀이가 있었는데 생각해내지 못해 O(NlgN)으로 풀었다. 그래서 끝나고 더 알아봐서 풀게 되었고 여기에 3가지의 풀이를 적어놓았다. 1번 크레인 인형 뽑기 게임 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 더보기 N x N 크기의 정사각 격자가 있다. 각 격자 칸에는 다양한 1 x 1 크기의 인형이 격자의 가장 아래 .. 2020. 5. 1. 1395 스위치 with Lazy Propagation Lazy Propagation으로 구간 합 구하기 2를 풀고 바로 다음 문제로 넘어갔다. 처음에는 모두 꺼져있고 구간이 주어질 때 키고 끄고를 반복하여 구간 내 켜져있는 스위치의 개수를 출력하는 문제이다. 스위치를 두 번 키면 결국 같은 상태가 된다. 따라서 홀수일때만 노드의 값을 변경해주면 된다. 처음 그냥 구간내 개수로 변경하면 되겠지 했다가 다른 구간에서 변경이 되는 경우도 있으므로 구간 개수에서 현재 노드의 값을 빼줘야하는 것을 뒤늦게 알게 되었다. void update_lazy(int idx, int l, int r) { if (lazy[idx] != 0) { if (lazy[idx] % 2) seg[idx] = (r * 1LL - l + 1) - seg[idx]; if (l != r) { la.. 2020. 4. 2. 10999 구간 합 구하기 2 with Lazy Propagation 2차원 세그먼트 트리까지 공부를 하고 Lazy Propagation을 배우게 되었다. 직역하면 게으른 전파라는 소리이다. 이것을 쓰는 이유는 구간 전체를 변경할 때 빠르게 구하기 위해서이다. 기존 세그먼트 트리에서 Update를 할 때 한 점을 갱신한다. 왼쪽 오른쪽 구간을 나누고 구간 안에 속해있으면 탐색을 안 하기 위해서 세그먼트 트리를 쓰는 것인데 구간 전체를 변경하게 된다면 결국 각각의 점을 들어가서 변경을 해야 한다. 이러한 비효율적인 일을 막기 위해서 변경은 나중에 방문을 할 경우 한 번에 하고 변경되는 값을 따른 배열에 모아놓는 것이다. 자세한 구현법은 코드와 함께 정리하겠다. 1. 먼저 세그먼트 트리와 똑같은 크기의 Lazy 배열을 만든다. 2. 그리고 기본적인 세그먼트 트리와 똑같이 구현.. 2020. 4. 2. 12899번 데이터 구조 세그먼트 트리를 응용한 문제이다. 이제 막 세그먼트 트리를 공부해서 처음엔 추가하는 것도 어려웠다. 추가하는 것은 set을 써도 가능하지만 세그먼트 트리를 공부하기 위한 것이니까 안 하고 고민을 해봤다. 그냥 세그먼트 트리에서 미리 다 만들어져 있다고 가정하고 일반적으로 Update 하듯이 값을 수정해주면 되었다. 그리고 값을 수정한 뒤 X번째로 작은 수를 찾아야 하는데 이 방법을 몰라서 세그먼트 트리를 다시 공부하였다. 결국 방법은 트리 구조에서 마지막번째 레벨의 노드가 1~2000000까지 있게 만들었으므로 K번째 노드가 수 K를 나타내는 것으로 나타낼 수 있다. 그래서 각 노드의 값을 그 수의 개수로 입력하고 세그먼트 트리로 개수들의 합을 저장한다. K 번째 수는 결국 왼쪽에 K개가 있으면 그 노드.. 2020. 4. 2. 이전 1 다음
