크래프톤 정글 8기 - 36일차 TILBoyer-Moore 문자열 검색 알고리즘 정리Boyer–Moore 알고리즘은 문자열 검색 알고리즘 중에서도 가장 빠르고 실용적인 알고리즘 중 하나다. 이 글에서는 Boyer-Moore 알고리즘의 기본 개념, 핵심 규칙(Bad Character Rule, Good Suffix Rule), 그리고 실제 탐색 방식에 대해 정리한다.1. Boyer-Moore 알고리즘의 핵심 아이디어"비교는 오른쪽 끝부터 시작하며, 실패하면 패턴을 최대한 멀리 점프시킨다."일반적인 문자열 검색은 왼쪽부터 비교하지만,Boyer–Moore는 오른쪽부터 왼쪽으로 비교한다.실패 시, 두 가지 규칙 중 더 먼 쪽으로 점프하여 검색 속도를 높인다.보이어-무어 알고리즘에서는 한국어로 "건너뛰기 표(sk..

크래프톤 정글 8기 - 35일 차 TILKMP (Knuth-Morris-Pratt) 문자열 검색 알고리즘 정리문자열 검색 알고리즘 중 하나인 KMP 알고리즘은 텍스트에서 특정 패턴이 존재하는지 빠르게 찾아내기 위한 알고리즘이다. 이 글에서는 KMP 알고리즘의 동작 원리와 핵심 개념인 LPS(Longest Prefix Suffix) 배열을 중심으로 정리하였다.1. KMP 알고리즘의 핵심 아이디어"문자열 검색 중 일치하지 않으면, 이미 비교한 정보를 활용해 중복 비교를 피한다"일반적인 완전 탐색은 실패하면 항상 패턴의 처음부터 다시 시작하지만, KMP는 패턴 내의 반복 구조를 이용해 비교 위치를 점프할 수 있다. 이로 인해 최악의 시간복잡도가 O(n + m)으로 매우 효율적이다.2. LPS (Longest ..

📝 주간 학습 회고 (TWL) - 2025년 04월 5주차정글 입소 35일 차 5주 차 시작 전 4주차 회고 및 5주차 목표 설정🎯 이번 주 목표C 언어 학습링크드 리스트, 큐, 스택 구현 처음부터 수행하기알고리즘 문제 풀이 멈추지 않기📚 학습한 내용포인터, 구조체크래프톤 정글 8기 - 32일 차 TIL (포인터)링크드리스트 - C크래프톤 정글 8기 - TIL 31일 차 (링크드 리스트 - C)💡 새롭게 알게 된 것내부 단편화, 외부 단편화🔍 어려웠던 점 / 해결 방법어려웠던 점해결 방법c언어로 자료구조의 직접 구현처음부터 직접 구현하며 구조 이해5주차 진입 후 어떤 것부터 해야할지 막막했다.주위에서 어떻게 하겠다는 것을 주워 듣고 우선순위 판단🛠️ 만든 것 / 작업한 것C 언어 테스트 기반 ..

안녕하세요 크래프톤 정글 8기 진행 중인 고웅입니다. 4월 10일 크래프톤 정글 알고리즘 주간이 끝나고 C 프로그래밍을 시작한 5주 차입니다. 4주간 알고리즘 문제를 풀기 위해 많은 노력을 들였고 나름대로 많은 성장이 있었다고 생각합니다. 하지만 5주 차부터 시작되는 C프로그래밍은 과거 대멸종과 같이 한 순간에 모든 관심사와 중요도를 뒤엎을 정도의 대 격변이었습니다. 그리고 그런 대격변에서도 알고리즘 감각은 계속 유지할 수 있어야 한다고 생각이 들었습니다. 그래서 알고리즘 리마인더를 구현해 봤습니다.알고리즘 리마인더?이름은 거창하게 있어보이게 지었지만 간단하게 말해서 그냥 알고리즘 문제를 복습할 수 있도록 체크하는 체크리스트?입니다. 근데 자동화 요소를 곁들인...새로운 문제를 푸는 것도 중요하지만 무작..

안녕하세요! 크래프톤 정글 8기 진행 중인 고웅입니다. 크래프톤 정글 5주 차가 시작되며 본격적으로 C 언어 학습 및 자료구조 구현이 진행되고 있는데 정글에서 제공해 준 과제를 구현하고 있는데 테스트 케이스를 직접 터미널 입력으로 테스트하는 것이 불편하기도 했고 자료구조를 처음부터 전부 구현하는 것이 아니라 특정 함수의 기능만 구현하다 보니 오히려 구현 의도나 방법이 잘 생각나지 않고 이해가 되지 않는 것 같아 처음부터 구현을 할 수 있었으면 하는 바람이 있었습니다. 그래서 이 글에서는 제가 C 언어로 구축했던 테스트 기반 개발 환경을 소개합니다. Clion과 VSCode 두가지 IDE에서 테스트를 진행했으며 맥북에서는 테스트를 했으나 윈도우의 경우는 다를 수 있습니다. C에서도 테스트 주도 개발(TDD..

TIL - 2025.04.11 (금요일)📝 오늘 배운 것 (c - 포인터)포인터란?포인터는 "주소값을 저장하는 변수"이다.즉, 어떤 데이터가 메모리 어딘가에 저장되어 있을 텐데, 포인터는 그 "메모리 주소"를 기억하는 변수​.왜 포인터가 필요할까?그보다 c를 처음 입문할 때 들었던 생각이 "왜 주소라는 것을 직접 다뤄야 할까?"였다. 그도 그럴 것이 파이썬으로 주로 코딩에 입문을 하고는 하는데 파이썬은 그냥 하고 싶은 대로 하면 되었다. 하지만 c를 배우며 포인터를 만나면 그 개념부터 혼동이 된다. 나 또한 지금도 포인터가 혼동된다.이 어지러운 포인터를 이해를 위해서 그나마 주소로 설명하는 것이 유용하다.포인터는 집 주소?한번 생각해보자 변수 : 집 안에 살고 있는 사람포인터 : 그 집의 주소int a..

TIL - 2025.04.10 (목요일)📝 오늘 배운 것: C로 구현하는 링크드 리스트4월 10일, 크래프톤 정글에 입소한 지 벌써 1달이 되었다.1~4주 차까지는 알고리즘 위주로 학습했고, 이제부터는 C 언어로 자료구조를 구현하거나 문제를 풀어보는 활동을 4주간 진행할 예정이다.링크드 리스트란?링크드 리스트(Linked List)는 데이터를 순차적으로 저장하는 자료구조로, 각 요소가 포인터를 통해 다음 요소와 연결되어 있다.배열과는 달리 메모리상에서 연속된 공간에 있지 않으며, 노드(Node)라는 단위로 구성된다.노드는 보통 두 가지 요소를 가진다:데이터(Data): 실제 저장 값포인터(Next): 다음 노드의 주소 (또는 참조)[1 | ●] → [2 | ●] → [3 | null]🔹 링크드 리스트..

TIL - 2025.04.09 (수요일)📝 오늘 푼 문제 (백준 13869 Dating On-Line)문제외국어 문제로 번역해서 풀겠습니다.알렉스는 완벽한 파트너를 찾기 위해 온라인 데이트 시스템에 가입했습니다. 이 시스템은 각 회원이 N가지 활동에 대한 만족도를 0점에서 100점까지 점수로 매기는 양식을 작성하도록 요구합니다. 이 정보를 잠재적인 데이트 상대에게 제공하기 위해 시스템은 "방사형 다이어그램"이라는 특수한 다각형으로 구성된 프로필을 생성합니다.N개의 활동에 대한 방사형 다이어그램은 평면에 N개의 점을 표시하여 그립니다. 수직 방향에서 시작하여 시계 방향으로 i번째 점은 구성원이 지정한 i번째 활동을 나타내며, 다이어그램 중심에서 S i 만큼 떨어진 거리입니다. 여기서 S i는 구성원이 해..

📘 3.11 Floating-Point Code부동소수점 연산은 일반적인 정수 연산과는 달리 복잡한 구조와 특별한 규칙을 따릅니다. 이 절의 도입부에서는 다음과 같은 핵심 요소들을 설명한다:1. 부동소수점 아키텍처란?부동소수점 아키텍처는 다음 네 가지 측면에서 프로그램이 부동소수점 데이터를 어떻게 다루는지를 규정한다:저장 및 접근 방법: 대부분 레지스터를 사용해 저장하고 접근함.작동하는 명령어 세트: 특정 명령어들이 부동소수점 데이터를 처리함.함수 호출 시 인자 및 반환값 처리 규칙: 예를 들어, 부동소수점 인자는 %xmm0~%xmm7에 저장됨.레지스터 저장 규칙: 어떤 레지스터가 caller-saved 또는 callee-saved인지 규정.2. 역사적 배경x86-64에서 부동소수점 연산은 SIMD (..

📦 3.10 머신 수준 프로그램에서 제어와 데이터 결합하기Combining Control and Data in Machine-Level Programs이 장에서는 제어 흐름(control flow)과 데이터 구조(data structures)가 머신 수준에서 어떻게 상호작용하며 동작하는지를 탐구한다. 지금까지는 이를 별도로 배웠지만, 실제 프로그램에서는 두 요소가 복잡하게 얽혀 있다.주요 주제:포인터(pointer)의 심화 이해 – C 언어에서 가장 강력하면서도 혼란스러운 개념 중 하나.gdb 디버거 사용법 – 머신 수준 프로그램의 실행 과정을 자세히 들여다보는 도구.버퍼 오버플로우 – 보안 취약점의 주요 원인 중 하나.스택 프레임의 크기가 실행마다 달라지는 경우의 구현 방식.🧠 3.10.1 포인터 ..