2023.05.28~

11/25(토)에 있었던 2024 KAKAO WINTER INTERNSHIP 코딩테스트에 참여하고 싶었지만, ICPC 본선 일정과 겹쳐 아쉽게도 참여하지는 못했습니다. 문제가 궁금해서 프로그래머스에 문제가 올라오기만 기다리다 드디어 올라와서 빨리 풀어보고 왔습니다. :) (링크) 개인적으로 구현이 오래 걸려서인지, 문제 푸는데 시간이 2번>5번>3번>4번>1번 순으로 오래 걸렸습니다. (저는 2번이 가장 오래 걸렸네요...) 1. 가장 많이 받은 선물 선물을 주고받은 기록을 map이나 dictionary 등의 자료구조에 저장해준 후, 문제에서 설명한 규칙대로 선물을 주고받는 과정을 시뮬레이션해줍시다. (자기 자신에게 선물을 주는 입력은 주어지지 않으므로, 코드의 마지막 이중 for 문에서 딱히 예외처리는..

이번 글에서는, 아래의 네 가지 조건으로 만들어지는 다양한 상황에서 알맞은 방식으로 구간 합을 구하는 테크닉을 소개하려고 합니다. 1차원 공간 vs 2차원 공간 점 업데이트 vs 구간 업데이트 점 쿼리 vs 구간 쿼리 (← 특정 위치에 대한 개수만을 묻는가? vs 어떤 구간의 총합을 묻는가?) 오프라인 쿼리 vs 온라인 쿼리 (← 질문을 업데이트가 모두 끝나고 하는가? vs 업데이트 도중에 질문을 하는가?) 문제는 난이도 순이 아니지만, 순서대로 읽어보시면 더 쉽게 이해하실 수 있습니다. 3, 4, 8번 문제는 세그먼트 트리에 대한 사전 지식을 필요로합니다. 세그먼트 트리에 관한 좋은 글이 이미 많기 때문에, 관련 내용은 링크로 대체하겠습니다. https://blog.naver.com/kks227/220..

1. 문제 LV 4.1,2,3 떨어트리기 - 2023 KAKAO BLIND RECRUITMENT 2. 문제 풀이 제 생각에 이 문제는, 답이 될 수 없는 경우를 적절히 체크하는 것으로 완전탐색/시뮬레이션이 가능함을 관찰하는 게 핵심인 문제였습니다. 먼저 답이 될 수 없는 경우에 대해 생각해 봅시다. 어떤 노드 x+1에 쌓인 숫자의 합$(= target[x])$이 아닌, 노드 x에 쌓인 숫자의 개수를 $stacked[x]$라고 합시다. (어떤 노드 'x+1'인 이유는, 노드 번호는 1부터 시작하고 $target$의 index는 0부터 시작해서 그렇습니다.) 숫자의 크기가 1~3 사이이므로, 모든 x가 $stacked[x]

1. 문제 LV 4.미로 탈출 - 2021 카카오 채용연계형 인턴십 2. 문제 풀이 우선, 출발 방과 도착 방의 정보가 주어지고, 노드수 제한 $n O(roads * 2^{traps} * log(n))$ 가 되고, $roads b[y]&1)))swap(x,y); //방 x에서, trap발동 상태가 bit일 때, {도착지, 도착했을 때 trap발동 상태, 도착하는 비용}이 담겨있는 간선을 추가한다. graph[x][bit].push_back({y,b[y]>b[x]&1))^(b[y]>=0&&(bit>>b[y]&1)))swap(x,y); 간선이 뒤집히는 경우입니다. 여기서 b[x]>=0 은 'x번 방이 함정방인가?'를 의미하고, bit>>b[x]&1 는 'b[x]번째 trap(= x번 방의 trap)이 발동 ..