2023.05.28~

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

이번 글에서는, 아래의 네 가지 조건으로 만들어지는 다양한 상황에서 알맞은 방식으로 구간 합을 구하는 테크닉을 소개하려고 합니다. 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'모양처럼 쭉 단조 증가하다가, ..