KMP (Knuth-Morris-Pratt) 문자열 검색 알고리즘

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

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 14.
• textsms

그래프톤 정글 8기 - 5주차 시작 전 회고

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

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 14.
• textsms

알고리즘 리마인더 구현

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

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 13.
• textsms

C 언어 테스트 기반 개발 환경 구축기 (CLion & VSCode) Mac

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

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 12.
• textsms

크래프톤 정글 8기 - 32일차 TIL (포인터)

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

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 11.
• textsms

크래프톤 정글 8기 - TIL 31일차 (링크드 리스트 - C)

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

• format_list_bulleted 크래프톤 정글
• · 2025. 4. 10.
• textsms