Tech/Coding113 오토마타(Automata)와 UML(Unified Modeling Language) "오토마타(Automata)"와 "UML(Unified Modeling Language)"은 모두 시스템을 모델링하거나 표현할 때 사용되는 도구이지만, 사용하는 분야와 목적이 다릅니다. 아래에 두 개념을 상세히 설명하고, 각각의 용도 및 차이점도 함께 소개드릴게요.1. 오토마타 (Automata)● 개념오토마타는 형식 언어 이론(Formal Language Theory)의 일부로, 수학적으로 추상화된 계산 모델입니다. 어떤 입력에 대해 상태 전이(State Transition)를 하며 작동하는 기계 모델을 의미합니다. 대표적인 오토마타로는 다음이 있습니다.DFA (Deterministic Finite Automaton): 결정적 유한 오토마타NFA (Non-deterministic Finite Autom.. 2025. 5. 9. Suffix Automaton과 KMP 비교 이해 suffix automaton과 KMP 알고리즘은 문자열 검색 및 문자열 구조 분석에 사용되는 도구이지만, 목적, 구조, 적용 범위에서 차이가 있습니다. 아래에 그 차이점을 자세히 설명드리겠습니다.📌 1. 개념 및 목적항목 Suffix Automaton (접미사 자동자) KMP 알고리즘목적문자열의 모든 부분 문자열을 빠르게 처리하거나 분석 (예: 부분 문자열 존재 여부, 갯수, 중복 등)패턴 검색: 텍스트에서 주어진 패턴이 등장하는 위치를 빠르게 찾음구조DFA(Deterministic Finite Automaton)를 최소화한 형태의 유한 상태 기계실패 함수(failure function)를 사용하는 상태 기반 검색 알고리즘입력하나의 문자열(기반 문자열 S)패턴 문자열 P와 텍스트 문자열 T🔍 2. .. 2025. 5. 6. FSM과 DFA, NFA의 개념과 차이 graph TD %% 노드 정의 FSM["🧠 FSM(Finite State Machine)"] DFA["🔵 DFA(Deterministic Finite Automaton)"] NFA["🟢 NFA(Non-deterministic Finite Automaton)"] Mealy["🟡 Mealy Machine"] Moore["🟠 Moore Machine"] DFA_Desc["📘 설명:결정적, 예측 가능"] NFA_Desc["📗 설명:비결정성, ε-전이 가능"] Mealy_Desc["📒 출력:전이와 함께 발생"] Moore_Desc["📙 출력:상태 기반 발생"] %% 관계 연결 FSM --> DFA FSM --> NFA FSM --> Mealy FSM --> Moore .. 2025. 5. 5. KMP 알고리즘을 DFA(오토마타) 관점에서 이해하기 문자열 검색 알고리즘인 KMP (Knuth-Morris-Pratt)는 단순한 비교가 아니라, 오토마타(DFA)처럼 상태를 가지며 동작하는 구조로도 이해할 수 있습니다. 이 글에서는 최대한 쉽게 그 원리를 풀어보겠습니다.🔍 1. KMP는 뭘 하려는 걸까?문자열 T에서 특정 패턴 P를 효율적으로 찾기 위한 알고리즘입니다.단순 비교는 느릴 수 있으니, 이미 매칭된 정보를 활용해서 뒤로 돌아가지 않고 매칭하는 것이 핵심입니다.🤖 2. 오토마타처럼 동작한다고?KMP는 다음과 같은 구조를 가집니다:상태(State): 지금까지 맞은 패턴 접두사의 길이입력(Input): 텍스트에서 들어오는 문자전이 함수(Transition): 다음 상태로 이동하거나 실패 시 fallback예를 들어 상태 3이면, 패턴 P의 처음 .. 2025. 5. 5. 전이 기반 탐색(Transition-based Search) 💡 개념 정의전이 기반 탐색이란, 오토마톤(automaton)의 상태(state) 간 전이(transition)를 따라가며 입력 문자열을 탐색하거나 일치 여부를 판별하는 방식입니다. 여기서 전이란, 현재 상태에서 특정 문자를 읽었을 때 이동해야 할 다음 상태를 정의하는 규칙이며, 일반적으로 딕셔너리(또는 해시맵) 형태로 구현됩니다.⚙️ 동작 방식초기 상태에서 입력 문자열의 첫 문자를 읽습니다.해당 문자가 정의된 전이를 통해 다음 상태로 이동합니다.이후 문자를 하나씩 처리하면서 상태를 전이해 갑니다.마지막 상태까지 도달했을 때 특정 조건(예: 문자열 일치, 패턴 발견 등)을 확인합니다.이 과정은 상태 간 전이만으로 이루어지므로 인덱스 기반 비교 없이도 효율적인 탐색이 가능합니다.🆚 배열 기반 탐색과의 .. 2025. 5. 5. Suffix Automaton과 Suffix Array 문자열에서 부분 문자열 또는 접미사에 대한 정보를 효율적으로 처리하는 두 가지 데이터 구조인 Suffix Automaton과 Suffix Array를 소개합니다.목차Suffix의 정의Suffix ArraySuffix Automaton (SAM)두 구조의 비교응용 예시요약1. Suffix란?Suffix(접미사)는 문자열의 접미 부분을 의미합니다."apple"의 접미사는 다음과 같습니다:순서접미사1e2le3ple4pple5apple2. Suffix Array개념Suffix Array는 문자열의 모든 접미사를 정렬한 후, 각 접미사의 시작 위치 인덱스를 저장하는 배열입니다. 이 구조는 Suffix Tree의 대안으로 제안되었습니다.예시"banana"의 경우:접미사 목록: banana, anana, nana, .. 2025. 5. 5. 스피드스택 정렬 대결 1학년 딸과 놀아주다가 아이스크림에서 파는 스피드스택으로 놀았는데 재미있다고 자꾸 하자고 그래서 룰을 정리해 보았습다.🧠 게임 목적1번부터 12번까지의 숫자가 적힌 컵을 정해진 방향으로 빠르게 정렬하는 것이 목표입니다.방향은 오름차순(1→12) 또는 내림차순(12→1)으로 사전에 합의할 수 있습니다.변형 규칙으로, 어느 방향이든 정렬이 완성되면 성공으로 인정하는 방식도 가능합니다.👥 참가자2명 또는 2팀이 참여합니다.각자 1세트(1~12번)의 컵을 가지고 플레이하며, 시작 전에 두 세트를 섞어 사용합니다.🎲 게임 준비 및 진행 순서컵을 섞는다: 서로의 컵을 합쳐 무작위로 섞습니다.자리 바꾸기: 자리를 바꾸어 서로 상대방이 섞은 컵을 정렬하게 됩니다.공격 순서 결정: 가위바위보를 통해 공격자를 정합니.. 2025. 5. 4. io.BytesIO(open(0, 'rb').read()).readline과 io.BufferedReader(io.FileIO(0), 1 << 18).readline ✅ 두 방식 비교 요약항목BytesIO(open(0, 'rb').read()).readlineBufferedReader(FileIO(0), 1입력 전략전체 stdin을 한 번에 메모리로 읽음버퍼 크기 지정하고 파일 스트림에서 읽음버퍼링메모리 상의 전체 스트림지정한 크기만큼 OS로부터 읽어옴속도매우 빠름 (작거나 중간 크기 입력에 유리)매우 빠름 (큰 입력에 특히 유리)메모리 사용량전체 입력을 한 번에 로드버퍼만큼만 로드 (메모리 효율↑)I/O 유연성제한적 (전체 메모리 기반)유연함 (부분 읽기 등 지원)일반적인 추천중소형 입력초대형 입력 (10⁶~10⁷줄 이상) 📌 어느 쪽이 더 빠른가?소형~중형 입력 (수 MB 이하):BytesIO(open(0, 'rb').read()).readline이 더 빠릅니다.. 2025. 5. 3. 10413 반복되는 부분 문자열 https://www.acmicpc.net/problem/10413 반복되는 부분 문자열시간 제한메모리 제한5 초256 MB문제문자열 분석은 DNA와 단백질 분자의 연구를 진행하기 위해 생물학과 화학 분야에서 종종 사용된다. 문자열 분석을 하는 데 있어, 긴 문자열에서 얼마나 많은 부분 문자열이 (적어도 두 번) 반복되는지 찾아내는 것이 중요한 문제이다.이 문제에서 최대 100 000개의 알파벳 문자열이 주어지면, 여러분은 그 문자열 중 모든 반복되는 부분 문자열의 개수를 찾아야 한다. 이때, 두 번 이상 등장하는 모든 유일한 부분 문자열을 세어야 한다. 예를 들어, 주어지는 문자열이 aabaab이면 반복되는 부분 문자열은 총 5개가 있다: "a", "aa", "aab", "ab", "b". 또, 주어지.. 2025. 5. 3. 2263번 (트리의 순회) 2263번 (트리의 순회) 2025. 5. 3. 15486번 퇴사 2 15486번 (퇴사 2)시간 제한메모리 제한2 초512 MB문제상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일Ti3511242Pi1020102015402001일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금.. 2025. 5. 3. 3356번 (라디오 전송) https://www.acmicpc.net/problem/3356 2025. 5. 3. 29768-펠린드롬 이름 https://www.acmicpc.net/problem/29768팰린드롬 이름성공시간 제한메모리 제한1 초1024 MB문제팰린드롬의 마법사 엣지는 오늘도 팰린드롬을 찾고 있었다. 그러던 도중 팰린드롬을 좋아하는 사람들이 모이는 축제를 만들고 싶어졌다. 축제의 이름의 길이는 \(N\)이고 이름은 서로 다른 영어 알파벳 소문자 \(K\)가지로 이루어져 있어야 한다. 마법사 엣지는 축제 이름의 조건을 만족하면서 서로 다른 부분 문자열 중 팰린드롬의 개수가 가장 많은 문자열을 축제의 이름으로 정한다. 문제에 사용된 단어의 의미는 예제 아래에 위치한 노트를 참고하자.마법사 엣지를 위해 축제의 이름을 하나 만들어주자. 축제의 이름으로 정할 수 있는 이름이 여러 개라면, 사전순으로 가장 앞선 이름을 만든다.입력첫째.. 2025. 5. 3. 출력 버퍼 두둥. 위 코드에는 무슨 일이 있는걸까?import osr = list(map(bytearray,(b'WBBBBBBBBW' for _ in range(10))))print('원래상태')for c in r: os.write(1,c+b'\n')for i in range(10): for j in range(10): r[i][j] = 153 - r[i][j]print('반전 후')for c in r: os.write(1,c+b'\n') import osimport sysr = list(map(bytearray, (b'WBBBBBBBBW' for _ in range(10))))print('원래상태')sys.stdout.flush() # 버퍼 강제 비움for c in r: os... 2025. 4. 29. 토글 코드 트릭 솔브닥 스트릭을 연명하기 위해 문자열 브론즈 문제를 풀다가 고안한 토글 코드를 살펴보고 활용법을 이야기해 보겠다.신용카드 판별시간 제한메모리 제한1 초128 MB문제신용카드는 총 16자리의 숫자로 구성되어 있다. 언뜻 보기에는 무작위로 된 숫자로 구성되어 있는 것 같이 보이지만 그 속에는 하나의 수학적 비밀이 숨겨져 있다. 그중 하나가 카드 번호가 유효 한지 유효하지 않은 지 검사하는 Luhn 공식이다. 그 공식은 다음과 같다.1. 신용카드의 16자리 숫자에서 맨 우측 수부터 세어 홀수 번째 수는 그대로 두고, 짝수 번째 수를 2배로 만든다.2. 2배로 만든 짝수 번째 수가 10 이상인 경우, 각 자리의 숫자를 더하고 그 수로 대체한다.3. 이와 같이 얻은 모든 자리의 수를 더한다.4. 그 합이 10으로.. 2025. 4. 29. 이전 1 2 3 4 5 ··· 8 다음
