2023.05.28~

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

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)이 발동 ..