본문 바로가기

전체 글624

충돌 없는 완벽한 해싱이 존재한다고 ? (퍼펙트 해싱 개념 및 사례, 최적화 방법에 대해서) 이 글의 탄생 배경, 이 글에 대해서코딩 스터디 중 해싱 챕터에서 시간 복잡도를 주제로 이야기할 때였다. 해싱하면 연상되는 이미지는 당연히 "빠르다"였고 나는 당연스럽게 O(1)이지! 라고 생각하며 대화를 이어나갔는데, 한 멤버가 질문했다."어... 해싱도 최악의 경우는 O(n) 아니에요?"어라, 순간 멈칫했다. 사실 해싱에서 최악의 경우는 O(n)이라는 걸 깜빡하고 있었다! 자바에서 해싱을 사용할 때는 충돌 문제를 자동으로 처리해주고, 또 key-value 스토어로서 레디스와 같은 저장소를 사용할 때, 단순히 "빠르다"는 이미지에만 노출되어 있다 보니 당연히 해싱은 O(1)이라고 생각했던 것이다. 문득 기억을 환기시키며 깨달았다. 앗,,, 해싱은 충돌이 없다면 O(1)이지만, 충돌이 발생하면 O(n)이.. 2024. 11. 2.
GPT 복붙만으로 프로그램을 만들 수 있을까? (feat. AI 시대의 개발자, 기묘한 질문들, 그리고 낯설고도 친절한 어떤 존재에 대해서) 이 글에 대해서이 글은 두 가지 파트로 구성됩니다. 첫 번째 파트에서는 ChatGPT를 이용해 단순한 복사 붙여 넣기 만으로 파이썬 프로그램을 만든 실험을 소개합니다. 전투 시뮬레이션 게임에 대한 전문 지식도 파이썬으로 게임을 만들어 본 경험도 없지만, 코드 한 줄 작성하지 않고 GPT만으로 프로그램을 구현하는 과정을 상세히 작성해 보았습니다. 두 번째 파트에서는, 이 과정을 통해 느낀 점과 AI 시대의 개발자라는 주제로 조금 더 깊이 있는 회고와 성찰을 담았습니다. 단순히 AI로 프로그램을 만드는 것을 넘어, AI 시대에 ‘개발자’란 어떤 의미가 있는지, 그 미래에 대해 최근 생각하는 개인적인 견해를 정리해 보았습니다.☘️ PART 1. GPT 복붙만으로 프로그램을 만들 수 있을까?사건의 발단노앤써라는.. 2024. 10. 26.
요세푸스 문제의 마지막 남은 사람을 수학적 귀납법으로 도출한 점화식으로 찾아보자 이 글의 작성 배경요세푸스 문제를 다양한 방법으로 풀어보면서 배열, 큐, 링크드 리스트, 세그먼트 트리 등 여러 알고리즘적 접근을 시도해 보았다. 각 방법에서 최적화를 시도했지만, 시간 복잡도는 여전히 \( 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.