본문 바로가기

전체 글622

요세푸스 문제의 마지막 남은 사람을 수학적 귀납법으로 도출한 점화식으로 찾아보자 이 글의 작성 배경요세푸스 문제를 다양한 방법으로 풀어보면서 배열, 큐, 링크드 리스트, 세그먼트 트리 등 여러 알고리즘적 접근을 시도해 보았다. 각 방법에서 최적화를 시도했지만, 시간 복잡도는 여전히 \( O(n^2) \) 정도였고, 세그먼트 트리를 사용해도  \( O(n \log n) \) 이 최대였다. 조금 더 최적화할 방법이 뭔가 있을 것 같은데... 고민하다가 문제를 가상의 순환 구조로 해석하면 어떤 규칙이나 패턴이 존재하지 않을까 하는 의문이 생겼다. 그러던 중, 점화식 풀이법을 알게 되며 이 방식에 주목하게 되었다. 점화식을 활용한 풀이법은 흥미로웠지만, 문제는... 어려웠다. 😭 특히, 이 점화식을 어떻게 유도할 수 있는지, 그 논리적 근거와 직관이 어떻게 도출되는지, 그리고 실제로 이 .. 2024. 10. 13.
[백준] 기념품 (자바 풀이) https://www.acmicpc.net/problem/12873  📌 문제백준이는 BOJ 알고리즘 캠프 참가자 중 한 명에게 기념품을 주려고 한다. 하지만, 많은 참가자 중에서 어떤 사람을 뽑아서 기념품을 줘야하는지 고민이 되기 시작했다. 따라서, 백준이는 게임을 통해서 기념품을 받을 사람을 정하기로 결정했다. 게임이 시작하기 전에 모든 참가자 N명은 원을 이루어서 앉아있다. 다음, 1부터 N까지 번호가 적혀있는 티셔츠를 시계방향으로 입는다. 이 티셔츠는 게임에 사용되지 않으며, 게임을 쉽게 하기 위해서 입는 티셔츠이다. 게임은 단계로 이루어져 있으며, 첫 단계는 1단계이다. 각 단계가 시작될 때, 백준이는 어떤 참가자의 앞에 서있다. 그 다음, "하나"를 외친다. 그 다음, 시계 방향으로 다음 사.. 2024. 10. 12.
[백준] 앵무새 (자바 풀이 - 큐, 배열, 해시맵을 곁들인) https://www.acmicpc.net/problem/14713  📌 문제자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 이 섬에 사는 앵무새들은 놀라울 정도로 인간의 말을 흉내 내는 데 뛰어나다는 것이다. 그들은 서로 떨어져 섬을 탐험하기로 하였으며, 필요하다면 앵무새를 이용해 서로에게 연락하기로 약속하였다. 1개월 후, pps789는 섬의 비밀을 밝힐 결정적인 증거를 찾게 된다. 그는 이 세기의 대발견을 cseteram에게 공유하고자 하였으나, 그의 발견은 방대하여 앵무새 한 마리가 기억하기에는 너무 많은 양이었다. 그렇기 에 pps789는.. 2024. 10. 12.
[백준] 좋은 친구 (자바 풀이) https://www.acmicpc.net/problem/3078   📌 문제상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다.상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아.??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 말콤은 이 연구를 하기 위해서 6년동안 초등학교에서 선생님으로 위장 했었지. 하지만, 6년이라는 시간을 초등학교에서 보냈지만, 그 사람은 결국 결론을 얻지 못했어.상근: 근데???: 말콤이 어느 날 자신이 초등학생이 되어 학교를 활보하는 .. 2024. 10. 11.
모노토닉 스택(monotonic stack) 개념, 작동원리 + 예제 문제들 (주식 가격, 탑, 히스토그램에서 가장 큰 직사각형 찾기) 1. 모노토닉 스택이란?모노토닉 스택 개념모노토닉 스택(Monotonic Stack)은 원소들이 단조 증가하거나 단조 감소하는 순서를 유지하는 스택이다. 즉, 스택에 삽입되는 값들이 항상 특정한 순서를 따른다. 예를 들어, 단조 증가 스택은 스택에 있는 값들이 항상 오름차순(increasing)을 유지하도록 구성되며, 단조 감소 스택은 스택의 값들이 내림차순(decreasing)을 유지한다. 이 스택의 중요한 점은 특정 규칙을 만족시키기 위해 스택에서 값을 꺼내면서 문제를 해결한다는 점이다. 모노토닉 스택의 핵심은 배열을 한 번만 순회하면서 각 요소에 대해 문제의 요구 사항을 만족시키는 연산을 할 수 있다는 것이다. 이때 요구 사항은 일반적으로 다음 큰 수, 이전 작은 수 등을 찾는 데 사용된다. 이 과.. 2024. 10. 6.

티스토리툴바