1. 문자열 패턴 매칭 문자열 패턴 매칭은 주어진 문자열에서 특정 패턴이 어디에 위치하는지 찾는 알고리즘. 예를 들어, "나는 전선을 간다"라는 문자열에서 "전선"라는 패턴을 찾는 경우가 문자열 패턴 매칭의 한 예다. 검색 엔진, 텍스트 편집기, 데이터베이스 등에서 이용된다. 여러 가지 알고리즘들이 있으며, 각각의 알고리즘은 다른 상황에서 장점을 가짐.  문자열 패턴 매칭 알고리즘설명장점단점Brute force주어진 문자열을 처음부터 하나씩 검사하며 패턴과 일치하는지 확인구현이 간단하다문자열이 길 경우 비효율적이다라빈 카프해시 함수를 이용하여 패턴의 해시값과 문자열의 해시값을 비교평균적으로 빠른 검색 속도해시 충돌로 인해 오동작할 가능성이 있다KMP패턴 내에서의 반복을 찾아내어 검사 횟수를 줄임중복 검사..

1. 플로이드 워샬이란? 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘.시간복잡도 : O(N^3) Dijkstra와 달리 모든 노드 쌍에 대한 최단 거리를 구하고,음의 가중치를 가지는 그래프에서도 쓸 수 있다! 2. 구현 DP로 접근하기 위해 부분 문제를 정의해야 한다. s에서 e까지 가는 데 걸리는 최단거리는 (s->e) 또는 (s->m→e)이다.(s->m→e) = s에서 m까지 가는 데 걸리는 최단거리 + m에서 e까지 가는 데 걸리는 최단거리 int INF = 1000000; // 도달할 수 없음을 의미 (구체적인 값은 문제 따라서 다름)int[][] graph; // 그래프를 나타내는 2차원 배열int n; // 노드의 개수public void floydWarshall() { //..

1. LIS란? Longest Increasing Subsequence최장 증가 부분 수열어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수를 제거하여 부분 수열을 만든다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 뜻한다. 2. LIS의 길이 구하기 동적 계획법으로 최장증가수열의 길이를 구하는 방법에 대하여 알아보자.  최장 증가 부분 수열최장 증가 부분 수열 문제는 동적 계획법 으로 풀 수 있는 유명한 알고리즘 문제이다. 정의 어떤 임의의 수열이 주namu.wiki 설명 참고. 가. O(N^2) 시간복잡도는 O(N^2)이다.int lis(int[] arr) { int n = arr.length; int[] dp = new int[n]; // 배열의 i번째 요소를 마..

1. Knapsack Knapsack 문제는 조합 최적화 문제의 일종으로 주어진 물건들의 가치와 무게, 그리고 배낭의 총용량이 주어졌을 때, 배낭에 넣은 물건들의 가치의 합이 최대가 되도록 하는 물건들의 부분집합을 찾는 문제이다. 동적 계획법(Dynamic Programming)으로 풀 수 있다. 0-1 Knapsack: 각 물건을 배낭에 넣거나 넣지 않거나 두 가지 경우만 고려하는 문제.0-N Knapsack: 각 물건을 배낭에 여러 개 넣을 수 있는 문제입니다.Fractional Knapsack: 각 물건을 배낭에 일부분만 넣을 수 있는 문제입니다.: 무게 대비 가치가 높은 물건부터 배낭에 담는 탐욕 알고리즘(Greedy Algorithm)을 이용하여 풀 수 있다.  import java.io.Buf..

1. 제어 유니트의 기능 명령어들을 인출하여 해독하고 실행하는 과정이 순차적으로 발생되도록 하기 위해서 그 순간마다 적절한 제어 신호들이 생성되어 해당 하드웨어 모듈로 보 내져야 한다. Control Unit. (a.k.a CU)는 …컴퓨터 프로그램을 구성하고 있는 명령어들을 해독하고,그 결과에 따라 명령어 실행에 필요한 동작들을 수행시키기 위한 제어 신호들을 발생하는 장치이다. 즉, 명령어 사이클이 적절히 수행되도록 모든 동작들을 제어하는 장치. 가. 마이크로프로그램 각 사이클에서는 여러 개의 마이크로-연산들이 수행된다. CPU 클록 주기마다 서로 다른 마이크로-연산이 수행된다. 각 마이크로-연산이 실제 수행되기 위해서는 2진 비트들로 표현되어야 한다. 비트들로 이루어진 각 단어를 마이크로명령어(mic..

1. Property Shorthand// ES6 이전const id = "idid", name = "namename", age = 30;const user = { id: id, name: name, age: age,};console.log(user);// ES6 이후const id = "idid", name = "namename", age = 30;const user = { id, name, age,};console.log(user)객체를 정의할 때 객체의 key값과 value에 할당할 변수명이 같을 경우 value를 생략할 수 있다. 2. Concise Methodconst user = { // info: function () { ..

0. Basic Computer 아래 모든 설명은 Basic Computer를 기준으로 진행한다. Basic Computer: DEC. Corp사의 중형 컴퓨터 PDP-11을 지칭: 가장 기본적인 컴퓨터 구조: 현대 CPU와 동일한 설계 구조 1. 명령어 코드 (Instruction Codes) 컴퓨터의 동작은 레지스터 내에 저장된 데이터에 대한 마이크로 연산의 시퀀스에 의해 정의된다. 항목설명프로그램사용자가 원하는 연산과 피연산자가 처리되는 순서를 기술한 컴퓨터 명령어의 집합컴퓨터 명령어컴퓨터에 대한 일련의 마이크로 연산을 기술마이크로 연산레지스터에 저장된 데이터를 가지고 실행되는 동작. 하나의 클럭 펄스 동안에 실행되는 기본적인 동작. 여기서 컴퓨터 명령어는 컴퓨터에 대한 일련의 마이크로 연산을 기술..

1. Index 데이터베이스(DB)의 인덱스란 데이터 검색 속도를 높이기 위해 사용하는 기술이다. 또한 특정 항목들에 대하여 중복이 발생하지 않도록 관리하기 위해서 사용되기도 한다. 하지만, 인덱스는 별도의 공간을 차지하고, 데이터가 변경될 때마다 추가적인 연산이 발생한다. 인덱스를 사용할지 말지 신중하게 따져봐야 한다. 2. Index의 종류 인덱스는 몇 가지 조건에 따라서 생성된다. PK 존재 PK 없음 Clustered index PK Unique + NOT NULL Secondary key Unique Unique show index from table_name; 테이블의 index를 조회할 수 있다. 가. Clustered index 클러스터형 인덱스 : 데이터들을 일정 기준으로 정렬하는 인덱스..