2023.05.28~

드디어 1024일에 걸친 마라톤이 끝이 났다. 사실 11단계 뱃지가 나올지도 몰라서 끝인지는 모르겠다.PS를 공부했던 절반 이상의 시간이 담겨있는 만큼, 그동안 여러모로 느낀 점을 돌아보려고 한다.시작스트릭이 처음 생긴 날은 2021년 7월 19일이었는데, 내가 유일하게 스트릭을 못 채운 날이기도 하다.그래서 더 기억에 남는데, 저 날은 내 생일이자 군대에서 처음 취사지원을 갔던 날이었다. 자대배치를 받은 지 얼마 안 돼서 싸지방 코딩에 적응하던 중이었고, 하루종일 설거지만 하니 힘들어서 '하루만 쉬어야지..' 했는데 하필 그날 스트릭 시스템이 도입되었다. 그래서 이 뱃지를 얻지 못했고, 7등으로 뱃지를 얻게 됐다.PS in 군대군대에서 문제를 푸는 건 어렵지 않지만, '하루도 빠지지 않고' 문제를 푸는..

어느덧 새싹 10단계 뱃지를 향한 여정도 얼마 남지 않은 가운데, 브실골 문제들만 풀며 스트릭을 연명하던 중 변화를 주기 위해 시작했던 혼자만의 챌린지가 드디어 끝났다. 끝나고 보니 몇몇 문제들은 난이도가 G1으로 내려가 있는데, 아무튼 풀 땐 P5였다. (다이아도 몇 개 풀었으니 쌤쌤이다) 주차별로 풀었던 문제들과 한 줄 평을 기록하고, 재밌는 문제들은 빨간색으로 추천했다. 1주차 (12/18 ~ 12/24) 즐거운 게임 (백준 15490, P5) 소방서의 고민 (백준 2180, P5) 이런 느낌의 문제가 플래티넘 그리디에서 자주 보이는 것 같다. 한 번쯤 경험해두면 좋을 듯. Similarity of Subtrees (백준 15533, P5) 태그를 안 보면 너무 어려운 문제. 처음 보는 유형인데 되..

이 글은 지극히 주관적인 내용이므로, 반박은 언제나 환영합니다! 비슷한 주제의 좋은 글이 있으니 같이 읽어보셔도 좋겠습니다. 슬슬 취업 시기가 다가오는 나이가 되어, 요즘 친구들에게 코딩테스트를 어떻게 준비해야 하는지 질문을 자주 받곤 합니다. 그런데 다들 궁금해하고 어려워하는 내용이 비슷해서, 이참에 구체적으로 생각을 정리해봤습니다. 많은 분에게 도움이 되었으면 좋겠습니다. 답변에 대한 제 나름의 이유도 적어두었으니, 여러분께 공감되는 답변만 참고하시면 좋을 것 같습니다. 1. 문제를 풀다 도저히 모르겠으면, 풀이를 보는 게 좋을까요? 아니면 끝까지 고민하는 게 좋을까요? 2-1. 풀이를 본다면, 얼마나 고민한 후에 보는 게 좋을까요? 2-2. 저는 풀이를 보기 싫어요. 힌트 정도만 보고 싶은데, 힌트..

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

마지막 목표로 삼았던 다이아 2티어를 드디어 달성했다. 다이아 3에서 약 9개월 정도 걸렸다. 원래 이번 여름방학에는 스프링을 제대로 공부해 볼 계획이었는데, 요즘 들어 알고리즘 대회나 기업 코테를 볼 일이 많았어서 연습한다는 명목으로 백준만 붙잡고 있었던 것 같다. (사실 다이아 문제들을 대회 중에 볼 실력은 아직 아니라서 연습이 됐는지는 잘 모르겠다.) 플래티넘 문제들은 레이팅을 거의 안 줘서 다이아 문제 위주로 고르다 보니, 아직 공부하지 않은 다이아급 알고리즘 기본 문제들이 너무 많았다. 하지만 지금 해봐야 당장 대회에서 응용하기도 힘들 것 같아서, 오히려 잘 알려진 알고리즘들만 사용하는 다이아 문제들을 골라서 풀었다. (쫄아서 그런 거 아님. 아무튼 아님.) 덕분에 구현력도 좋아지고, 기존에 흐..

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

이번 글은 특정 알고리즘에 대한 설명이라기보다는, 수학/정수론 문제를 풀 때 꽤나 자주, 유용하게 쓰이는 여러 가지 비트연산들에 대해 설명하고자 합니다. 들어가기에 앞서, 비트 연산자 &(and), |(or), ^(xor), ~(not), (right shift)에 대해 알고 계시면 좋습니다. 간단한 예로, n개 버튼 중 어떤 m개의 버튼을 눌러보는 모든 경우의 수를 시도해보아야 하는 상황에 대해 생각해 봅시다. 백준 N과 M 시리즈 풀이처럼, 아래와 같이 재귀함수로 구현할 수 있습니다. 더보기 #include using namespace std; bool button[20];//0~n-1, n=0;i--)printf("%d",button[i]);//n번째 버튼부터 순서대로 출력. printf("\n")..

1. 알고리즘 설명 삼분 탐색은 어떤 unimodal한 그래프에서, 최댓값 or 최솟값을 $log$ 시간 안에 찾아주는 알고리즘입니다. 이때 unimodal이란, uni(하나의) + mode(봉우리)라는 뜻으로, 이차함수 그래프처럼 봉우리가 하나인 그래프를 의미합니다. (bimodal은 'W'모양의 그래프처럼 봉우리가 두 개, multimodal은 봉우리가 여러 개인 경우입니다) 이분 탐색과 비교하자면, 이분 탐색은 함수의 값이 '/', '\'모양처럼 쭉 단조 증가 or 단조 감소하는 경우에만 사용할 수 있고, 탐색하려는 구간의 길이가 $n$일 때, 매 탐색 과정에서 구간이 1/2 크기로 줄어들기 때문에 시간복잡도는 $log_2(n)$입니다. 삼분 탐색은 함수의 값이 'V'모양처럼 쭉 단조 증가하다가, ..

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