너무 뻔한 이야기 일 수도 있지만, 올해 들어서 이해했기에 글로 남겨봅니다. PS를 꾸준히 풀다가 보면, 히스토그램이라는 문제를 한 번쯤은 들어봤을 수 있습니다. 플레 5 기준으로 사실상 제일 많이 풀린 문제이기도 하고 종만북, 바킹독 문제 모음집 등에서도 볼 수 있는 만큼 매우 유명한 문제이며 풀이도 여러 방법이 있습니다.  분할 정복, 세그먼트 트리 등등의 여러 방법도 있지만 그래도 제일 유명한 풀이는 스택 풀이입니다. Monotone Stack 테크닉을 통해서 스택에 필요한 정보들만 남겨서 푸는 방법인데, 이렇게 풀면 O(N)으로 풀 수 있다고 알려져 있습니다. 그런데, 저는 이 문제를 풀면서 왜 이게 O(N)인지가 궁금했습니다. 일단 제 구현 상에서 핵심 아이디어 코드만 따서 보면 이렇게 됩니다...

제가 지금까지 PS 문제를 풀 때 깨달은 유용한 팁들을 한 번 공유해보고자 합니다. 들어가기 앞서서, 여기에 적은 내용들은 전부 지극히 저의 주관적인 생각들입니다. 따라서 제 생각이 틀렸을 수 있으니 참고만 하시면 좋습니다. 그리고 피드백은 언제나 환영이니 댓글로 마음껏 해주시면 감사하겠습니다 :) 1. 시간 제한은 1초에 1억(10^8)번 연산이 가능하다고 생각하는게 편합니다. 저는 '1초 = 1억번의 연산'이라는 가정을 세우고 가능한 시간복잡도를 계산해봅니다. 주로 정해의 시간복잡도에 따른 연산 횟수를 계산해보면 이 공식이 맞는 것 같습니다. 물론 연산이 간단한가 어려운가에 따라서나 붙는 상수에 따라서 1초에 가능한 연산의 횟수가 커질 수 있긴 합니다. (그래서 저도 계산을 해보았을 때, 1억번을 '..

작년 한 해는 많이 놀았던 것 같습니다. 군대에서 전역을 하고 6개월 동안 집에서 계속 PS를 하고, 교회 신앙생활이랑 요리도 배우고 좀 쉬어가는 느낌이었습니다. (물론 2년간 뺑이친 걸 생각하면 좀 더 놀고 싶어서 한 학기 더 휴학할 예정이긴 하지만요.) 그러다보니 올해는 PS 관련된 활동을 많이 했었기도 했고 PS가 많은 영향을 끼쳤던 것 같습니다. 이번 글에서는 이에 대해서 회고를 해보고자 합니다. PS는 제가 군 생활을 하면서 후임 덕분에 시작했었는데요. 당시에는 그냥 '사무실 근무시간 녹이기 위해서 해볼까? 코테도 준비할겸 같이하지 뭐' 이런 생각으로 PS를 시작했던 것 같습니다. 저는 군대가기 전에는 학부연구생으로 2년 동안 AI만 공부했었는지라 PS에 대해서는 하나도 몰랐었습니다. 그리고 '..

지난 주 화요일 2023년 12월 19일에 HSAT 시험을 보았습니다. 해당 시험에 대해서는 우연히 알게 되었는데, 이걸 통과하면 현대자동차, 기아, 현대모비스, 현대오토에버, 현대차증권, 현대엔지비 SW 분야 지원 시, 코딩테스트 면제 혜택이 있다고 합니다. 아직 졸업하기엔 시간이 남았지만 어느정도 준비는 해야하기도 해서 가벼운 마음으로 보았습니다. 그리고 어제 결과가 떴습니다. 다른 후기들을 보면 주로 2주 정도 걸린다고 했는데, 1주 정도나 빨리 떠서 깜짝 놀랐습니다. 그래서 그런지 아직 문제들은 안 올라와서 어떤 문제였는지는 함부로 설명하긴 어려울 것 같네요... 다만 올라오면 다시 리뷰하도록 하겠습니다!

제가 지금까지 PS를 공부하면서 문제들을 볼 때 어느 과정들을 거쳐서 풀었는 지를 공유하면서, 겸사겸사 팁들도 공유하려 합니다. 코딩테스트는 제가 주로 풀어본 문제들과는 약간 다른 양상이 있지만(좀 더 구현 위주의 문제들이 나오는 것 같습니다.) 그래도 제가 드리는 팁들은 어느정도 먹힐거라 생각합니다. 문제 푸는 순서 제가 문제를 푸는 순서는 주로 다음과 같습니다. 1. 문제에서 요구하는 바 및 제한 사항들 확인하기. 2. 요구하는 것 및 문제 형태를 보고 어느 문제인지 짐작하기. 3. 제한 사항을 보고 시간 제한내로 풀리는 시간복잡도를 계산해보기 4. 2번 및 3번에서 생각한 것들을 토대로 문제를 풀 수 있는 알고리즘을 떠올리기. 5. 구현하고 문제 없는지 재점검하기. 6. 틀렸으면 코드에 대한 반례을..

제가 쓰는 C++ PS 템플릿을 공유합니다. 사실 그렇게 특별한 뭔가는 없습니다. 그냥 #include , PBDS, Fast I/O 담겨져 있는 정도만 있습니다. (Fast I/O도 따로 함수가 구현된 그런건 아니고 그냥 stdio랑 연동 끊기, cin과 cout 연동 끊기만 해두었어요.) 제가 매크로도 잘 사용을 안해서 long long을 ll로 매크로 해둔 것 빼고는 없기도 합니다. //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") // Compiler Optimization Options #include #define ll long long using namespace ..