본문 바로가기

전체 글54

트라이(Trie) 자료구조 구현 (문자열 검색과 자동완성) 우리가 구글이나 네이버 검색창에 '코딩'이라는 두 글자만 입력하더라도 하단에 '코딩 테스트', '코딩 학원', '코딩 기초' 등 수많은 연관 검색어가 0.1초도 안 되어 쏟아져 나옵니다. 데이터베이스에 저장된 수억 개의 검색어 데이터 속에서 어떻게 이렇게 찰나의 순간에 특정 문자로 시작하는 단어들만 쏙쏙 뽑아올 수 있는 것일까요? 만약 단순한 배열이나 해시 테이블(Hash Table)을 사용했다면 이렇게 부분 일치(Prefix) 기반의 자동완성 기능을 구현하는 것은 불가능에 가깝습니다. 오직 문자열의, 문자열에 의한, 문자열을 위한 고속 탐색 전용 자료구조인 트라이(Trie)가 존재하기에 가능한 일입니다. 코딩 테스트 문자열 파트의 최종 보스격인 트라이의 동작 원리와 메모리 트레이드오프(Trade-off.. 2026. 2. 20.
투 포인터(Two Pointers) 알고리즘 개념 맛보기 배열을 다루는 코딩 테스트 문제에서 "시간 초과(Time Limit Exceeded)"를 해결하는 구세주 같은 알고리즘이 있습니다. 바로 투 포인터(Two Pointers)입니다. 이름 그대로 '두 개의 포인터(화살표)'를 사용하여 배열을 훑는 기법입니다. 보통 이중 반복문(For문 안에 For문)을 써서 $O(N^2)$이 걸리는 문제를, 단 한 번의 스캔인 $O(N)$으로 끝내버리는 마법 같은 최적화 기술입니다. 오늘은 투 포인터의 핵심 원리를 직관적인 예시를 통해 알아보겠습니다.1. 투 포인터란 무엇인가?우리가 책을 읽을 때 보통 손가락 하나로 글자를 짚어가며 읽습니다. 하지만 투 포인터는 왼손 검지와 오른손 검지, 두 개의 손가락을 동시에 사용하여 데이터를 가리키는 방식입니다. 이 두 개의 포인터가.. 2026. 2. 20.
소수 구하기: 에라토스테네스의 체 원리 알고리즘 문제나 수학 관련 코딩 테스트에서 빠지지 않고 등장하는 주제가 바로 '소수(Prime Number)'입니다. 소수란 1과 자기 자신만으로 나누어떨어지는 1보다 큰 양의 정수를 말합니다(예: 2, 3, 5, 7, 11...). 숫자 하나가 소수인지 판별하는 건 쉽지만, "1부터 100만까지의 숫자 중 소수를 모두 출력하라"는 문제가 나오면 이야기가 달라집니다. 이때 무식하게 반복문을 돌리면 '시간 초과'의 늪에 빠지게 됩니다. 오늘은 고대 그리스 수학자의 지혜가 담긴, 가장 빠르고 효율적인 소수 판별 알고리즘인 에라토스테네스의 체를 알아보겠습니다.1. 왜 기본적인 방법은 느릴까? (Brute Force)가장 단순한 방법은 2부터 N까지 모든 숫자에 대해, 1과 자기 자신 외의 약수가 있는지 일일이.. 2026. 2. 19.
변수와 메모리 구조 기초 (RAM과 주소) 프로그래밍을 처음 배울 때 `a = 10`이라고 적으면, 우리는 단순히 "a라는 변수에 10을 넣었다"라고 이해합니다. 하지만 컴퓨터 내부, 특히 하드웨어 레벨에서는 이 한 줄의 코드를 실행하기 위해 분주한 움직임이 일어납니다. 개발자가 단순히 코드를 짜는 사람(Coder)을 넘어 원리를 이해하는 엔지니어(Engineer)가 되기 위해서는, 내가 선언한 변수가 물리적인 메모리(RAM) 어디에, 어떤 형태로 저장되는지를 이해해야 합니다. 이것이 포인터(Pointer)의 개념이자, 자바나 파이썬의 참조(Reference) 개념을 이해하는 출발점이기 때문입니다.1. 변수(Variable)란 무엇인가?변수는 흔히 '데이터를 담는 상자'에 비유됩니다. 하지만 컴퓨터 구조적인 관점에서 보면 조금 더 구체적인 정의가.. 2026. 2. 18.
아스키 코드 vs 유니코드 차이점 (문자 표현) 개발을 하다 보면 한글이 깨져서 `` 같은 물음표나 `믜??` 같은 외계어로 나오는 현상을 한 번쯤 겪어보셨을 겁니다. 이를 '인코딩(Encoding) 문제'라고 합니다. 컴퓨터는 0과 1밖에 모르는 계산기인데, 도대체 어떻게 '가', 'A', '💖' 같은 문자를 화면에 보여주는 걸까요? 그 비밀은 바로 문자와 숫자를 1:1로 매칭시켜 놓은 약속(Code)에 있습니다. 오늘은 문자 인코딩의 역사이자 표준인 아스키(ASCII)와 유니코드(Unicode)의 탄생 배경과 결정적인 차이를 알아보겠습니다.1. 아스키 코드 (ASCII): 미국 중심의 1세대 표준1960년대, 컴퓨터 통신을 위해 미국 표준 협회(ANSI)는 문자를 숫자로 표현하는 표준을 만들었습니다. 이것이 ASCII(American Standa.. 2026. 2. 17.
2진수, 10진수, 16진수 진법 변환 기초 컴퓨터 공부를 시작하면 가장 먼저 마주치는 외계어가 바로 `0`과 `1`로만 이루어진 세상, 그리고 `0x`로 시작하는 알 수 없는 숫자들입니다. 우리는 평생 손가락 10개를 이용해 숫자를 세는 10진수에 익숙해져 있지만, 컴퓨터는 전기가 통하고(1) 안 통하고(0)의 두 가지 상태만 알 수 있는 기계입니다. 따라서 개발자가 되려면 컴퓨터의 언어인 2진수와, 이를 보기 좋게 줄여놓은 16진수에 익숙해져야 합니다. 오늘은 이 진법들이 왜 필요하며, 서로 어떻게 변환하는지 그 원리를 완벽하게 정리해 드립니다.1. 진법(Base)이란 무엇인가?진법은 '자릿수가 올라가는 기준'입니다. - 10진수 (Decimal): 0부터 9까지 10개의 숫자를 사용합니다. 9 다음은 자릿수를 올려 10이 됩니다. - 2진수 .. 2026. 2. 16.

티스토리툴바