KMP 알고리즘이란? KMP 알고리즘은 Knuth, Morris, Pratt 세 사람이 만든 알고리즘으로, 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘 중 하나이다. 그렇다면 문자열 검색 알고리즘이란 뭘까? 위 사진은 웹 사이트에서 Ctrl+F 를 눌러 특정 문자열을 검색한 결과이다. 문자열 검색 알고리즘이란 말 그대로 문자열에서 특정 패턴을 찾아내는 알고리즘이다. KMP 알고리즘은 문자열에서 특정 패턴을 효율적으로 찾을 수 있다. 살펴볼 문자열의 길이가 N, 찾고 싶은 패턴의 길이가 M이라면 O(N+M)의 시간 복잡도를 가지는 매우 효율적인 알고리즘이다. KMP 알고리즘이 얼마나 효율적인지 알기 전에, 모든 문자열을 일일이 비교하는 경우를 살펴보자. 모든 문자열을 일일이 비교하는 경우(브루트..
스위치란? 네트워크에서 스위치란 소규모 비즈니스 네트워크 안에서 컴퓨터, 프린터 등 모든 디바이스를 서로 연결해주어 자원을 쉽게 공유할 수 있도록 하는 장치이다. 스위치는 L2(데이터 링크 계층)에 속하는 장치이다. 즉, MAC 주소를 기반으로 디바이스 위치를 파악하고 통신한다. 스위치는 브로드캐스트 도메인을 구분할 수 없다. 스위치는 ARP 등을 통해 불명확한 목적지를 가진 데이터를 처리할 때 모든 포트로 데이터를 퍼뜨리는 브로드캐스트를 한다. 참고) [네트워크] MAC주소와 ARP(Address Resolution Protocol)란? | MAC 주소의 필요성 MAC 주소란? IP 주소는 네트워크 계층(Network Layer)에서 사용되는 주소다. 반면 MAC 주소는 데이터 링크 계층(Data Li..
Index란? Index는 테이블에서 데이터의 위치를 가리키는 자료구조이다. Index가 없다면 원하는 데이터를 찾기 위해서 테이블 전체를 뒤져야 할 것이다. 이러한 Index는 크게 Clustered Index와 Non-Clustered Index 두 가지로 나눌 수 있다. 참고) [DB] 인덱스(index)란? 인덱스 자료구조 인덱스(index)란? 인덱스란 데이터베이스 테이블의 검색 속도를 향상하기 위한 자료구조라고 할 수 있다. 책의 색인(index)을 보면 해당 내용이 어디에 있는지 알 수 있듯이 데이터의 인덱스를 참조 code-lab1.tistory.com Clustered Index란? clustered Index는 row의 물리적 정렬 순서를 설정하는 index 유형이다. clustered..
오버로딩(Overloading)이란? 오버로딩은 같은 클래스 내에 여러 개의 같은 이름의 메서드를 정의하는 것이다. 이때 메서드의 이름은 같지만 매개변수(parameter)의 개수나 타입이 달라야 한다. return 값만 다른 것은 오버로딩이라고 볼 수 없다. 예를 들어 아래와 같이 Food 클래스 내에 여러 가지의 eat 메서드를 정의할 수 있다. public class Food{ void eat(Noodle noodle){ System.out.println("후루룩"); } void eat(Pizza pizza){ System.out.prinln("냠냠"); } void eat(Noodle noodle, Ramen ramen){ System.out.prinln("호로록~"); } } 같은 메서드 명이..
투 포인터 알고리즘(Two-Pointers Algorithm)이란? 투 포인터 알고리즘은 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘을 뜻한다. 보통 l(left), r(right)나 s(start), e(end) 같은 식으로 포인터의 이름을 붙인다. 투 포인터 알고리즘을 설명하기 위해 하나의 알고리즘 문제를 소개하겠다. https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 백준에서 풀어볼 수..
정규화란? 정규화는 이상현상(Anomaly)이 있는 릴레이션을 분해하여 이상현상을 없애는 과정이다. 이상현상이 존재하는 릴레이션을 분해하여 여러 개의 릴레이션을 생성하게 된다. 이를 단계별로 구분하여 정규형이 높아질수록 이상현상은 줄어들게 된다. 이전 포스팅에서 1NF, 2NF, 3NF, BCNF까지 다뤄보았다. [DB] 정규화(Normalization)란? 정규화 예시, 1NF, 2NF, 3NF, BCNF 정규화(Normalization)란? 정규화는 이상현상이 있는 릴레이션을 분해하여 이상현상을 없애는 과정이다. 이상현상이 존재하는 릴레이션을 분해하여 여러 개의 릴레이션을 생성하게 된다. 이를 단계 code-lab1.tistory.com 이번엔 제 4정규형(4NF)과 제5 정규형(5NF)에 대해 알아..
OLTP(Online Transaction Processing)란? OLTP란 트랜잭션 지향 애플리케이션을 손쉽게 관리할 수 있도록 도와주는 정보 시스템의 한 계열로서, 일반적으로 데이터 기입 및 트랜잭션 처리를 위해 존재한다. -위키백과- OLTP는 동시에 발생하는 다수의 트랜잭션을 실행하는 데이터 처리 유형이다. OLTP는 쿼리를 실행하고, 데이터 무결성을 유지하는 것을 목표로 한다. 예를 들어 은행의 ATM 기계는 OLTP 과정을 거친다. ATM 기계로 돈을 통장에 입금한다고 하자. 가장 먼저 카드를 삽입하면 ATM이 카드 정보를 인식한다. 카드를 인식했으면 돈을 기계에 넣는다. ATM은 돈을 세면서 잘못된 돈은 없는지 확인한다. 확인이 끝나면 돈을 보관하고 통장에 돈을 입금한다. 이러한 과정 중 ..
프림 알고리즘(Prim`s Algorithm)이란? 프림 알고리즘은 크루스칼 알고리즘과 더불어 최소 신장 트리를 찾는 대표적인 알고리즘 중 하나이다. 크루스칼 알고리즘과 최소 신장 트리에 대해 잘 모른다면 이전 게시물을 보고 오자. 참고) [알고리즘] 크루스칼 알고리즘(Kruskal Algorithm)이란? 크루스칼 알고리즘 C++ 구현, 최소 신장 트리(Mi 최소 신장 트리(Minimum Spanning Tree)란? 크루스칼 알고리즘에 대해 알아보기 위해선 우선 최소 신장 트리에 대해 알아야 한다. 우선, 신장 트리(Spanning Tree)란 무방향(Undirected) 그래프의 최소 연결 부 code-lab1.tistory.com 프림 알고리즘 과정 프림 알고리즘의 과정은 아래와 같이 간단한 편이..
최소 신장 트리(Minimum Spanning Tree)란? 크루스칼 알고리즘에 대해 알아보기 위해선 우선 최소 신장 트리에 대해 알아야 한다. 우선, 신장 트리(Spanning Tree)란 무방향(Undirected) 그래프의 최소 연결 부분 그래프이다. 좀 더 쉽게 설명하자면 N개의 정점을 가지는 그래프 중 최소 간선의 수인 N-1개의 간선으로 연결된 그래프를 뜻한다. N개의 정점이 N-1개의 간선으로 연결되어 있으면 이것은 필연적으로 트리 형태를 이루게 되기 때문에 신장 트리라고 불린다. [그림 1]을 보면 5개의 정점을 가진 그래프를 4개의 간선만을 사용해 연결하면 신장 트리가 되는 것을 볼 수 있다. 신장 트리는 하나의 그래프에서 여러 개가 나올 수 있다. 최소 신장 트리는 이러한 신장 트리들 ..
데이터베이스 트리거(Trigger)란? 데이터베이스 트리거는 테이블에 대한 이벤트에 반응해 자동으로 실행되는 작업을 의미한다. 트리거는 INSERT, DELETE, UPDATE 같은 DML(데이터 조작 언어)의 데이터 상태 관리를 자동화하는데 사용된다. 트리거(Trigger)는 말 그대로 방아쇠이다. 방아쇠를 당기면 총에서 총알이 발사되듯, 트리거가 실행되면 일련의 작업을 수행하게 된다. 트리거 유형 트리거는 크게 행 트리거와 문장 트리거가 존재한다. 행 트리거 : 테이블 안의 영향을 받은 행 각각에 대해 실행된다. 변경 전 또는 변경 후의 행은 OLD, NEW라는 가상 줄 변수를 사용하여 읽을 수 있다. 문장 트리거 : INSERT, UPDATE, DELETE 문에 대해 한 번만 실행된다. 또한 트리거..