MODE::CREATIVE

KMP 알고리즘 이란주어진 텍스트 문자열에서 특정 패턴 문자열이 등장하는 위치를 효율적으로 찾는 데 사용됩니다. KMP 알고리즘은 패턴 매칭의 각 단계에서 이미 비교된 정보를 활용하여 불필요한 비교를 줄임으로써 검색 속도를 높이는 방식으로 작동합니다.KMP 알고리즘 구현 코드public class KMP { // KMP 알고리즘을 사용하여 패턴을 검색하는 메서드 public static void KMPSearch(String pattern, String text) { int M = pattern.length(); int N = text.length(); // 부분 일치 테이블을 생성합니다. int[] lps = new in..

프로그램 개요l   본 프로그램은 EBNF로 문법이 정의되는 언어를 위한 Recursive-Descent Parser를 C/C++, Java, Python으로 각각 구현한 프로그램임, 프로그램은 아래의 EBNF문법을 모두 구현함https://github.com/Lee-min-gue/study/tree/2cdd07996137c7e6db9bca71875fd754e658a05f/programming_language/my%20recursive%20descent%20parser프로그램 주요 로직사용자 입력 처리:프로그램 실행 시 사용자의 입력을 한 줄씩 받습니다.사용자가 'exit'을 입력할 때까지 계속해서 입력을 받습니다.전역 변수 및 함수:전역 변수로는 pos (커서의 위치)와 token (토큰)이 있습니다...

용어lexeme(어휘소): 문장에서 가장 작은 단위의 의미구조Token: lexeme의 종류언어의 일반적인 정의Recognizers입력 문자열을 읽고 언어의 어느 부분에 속하는지 확인컴파일러의 syntax analysisGenerators언어의 문장을 생성함Generator와 비교함으로써 특정 문장의 구문법이 맞는지 확인할 수 있음Context-Free Grammars (CFG)Terminal 심볼 집합: T작성법이 문법 규칙에 의해 정해져 있지 않음, 구문적 변수 역할, 왼쪽에 위치 가능Nonterminal 심볼 집합: N작성법이 문법 규칙에 의해 정해져 있음, 오른쪽에만 존재시작 심볼: S(N에 속함)CFG의 유도입력된 문장이 문법에 맞는지 검사하는것을 유도라고 한다.유도가 가능하다면 문법에 맞는 스..

프로그래밍 언어 평가 요소 프로그래밍 언어 평가는 언어의 기능, 사용 편의성, 신뢰성 등을 종합적으로 고려하여 이루어집니다. 주요 평가 요소는 다음과 같습니다.1. 가독성 (Readability)프로그램을 얼마나 쉽게 읽고 이해할 수 있는지명확하고 간결한 문법, 자연스러운 표현 방식, 적절한 주석 사용 등이 중요예시: Python, Java2. 작성 용이성 (Writability)프로그램을 얼마나 쉽게 작성할 수 있는지간결하고 명확한 코드 작성을 가능하게 하는 표현력, 다양한 기능 제공 등이 중요예시: Python, JavaScript3. 신뢰성 (Reliability)프로그램이 예상대로 정확하게 작동하는지타입 검사, 예외 처리, 메모리 관리 등을 통한 신뢰성 확보가 중요예시: Java, C++프로그래밍..

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.참고교재: 쉽게 배우는 알고리즘(문병로)선택 알고리즘 1.선형 시간 선택 알고리즘(QuickSelect)2.최악의 경우 선형 시간 선택 알고리즘 최악의 경우 선형 시간 선택 알고리즘앞서 주어진 리스트에서 k번째로 작은(또는 큰) 요소를 찾는 선택 알고리즘을 구현했습니다.하지만 최악의 경우, 선택한 기준 원소가 항상 최솟값이나 최댓값이 되어, 분할이 매우 불균형하게 이루어지면 재귀 호출이 깊어져 Θ(n²) 시간이 걸립니다. 이를 해결하기 위해서 Median of Medians 알고리즘을 적용해 Θ(n)의 시간 복잡도를 보장할 수 있습니다. Median of Medians 알고리즘 단계그룹화:주어진 배열을 5개씩의 그룹으로 나눕니다. 마지막 ..

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.참고교재: 쉽게 배우는 알고리즘(문병로)선택 알고리즘 1.선형 시간 선택 알고리즘(QuickSelect)2.최악의 경우 선형 시간 선택 알고리즘 선택 알고리즘이란  선택 알고리즘은 주어진 리스트에서 k번째로 작은(또는 큰) 요소를 찾는 알고리즘을 의미합니다. 이 알고리즘은 다양한 방법으로 구현될 수 있습니다. 선형 시간 선택 알고리즘은 최악의 경우에도 O(n)의 시간 복잡도를 가지는 알고리즘입니다. 이 알고리즘의 대표적인 예는 QuickSelect입니다. QuickSelect는 QuickSort 알고리즘을 기반으로 하며, 분할-정복 방식을 사용합니다. 피벗을 선정하고 이를 기준으로 리스트를 두 부분으로 나눈 후, k가 어느 부분에 있는지에 ..