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..

0. 문제 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 1. 문제 이해 2. 제출 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; /** * BOJ12891 */ public class Main { static int ret; static int[] cond, cn..

0. 문제 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 1. 문제 이해 메모리 제한 448MB. (java8 기준) 주어지는 x의 크기가 1 ≤ x ≤ 20라서 int 32비트로 부분집합을 충분히 표현할 수 있다. 비트 연산으로 풀기. 2. 제출 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ11723 { static int S = 0;..

0. 문제 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 1. 시간초과 import java.io.BufferedReader; import java.io.InputStreamReader; //시간 초과 public class BOJ2023 { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuffer ..

1. Stack import java.util.Stack; Stack stack = new Stack(); push() : 삽입 pop() : 삭제 peek() : 조회 isEmpty() : 비었? size() : 크기 Stack underflow와 overflow를 조심하자. 2. Queue import java.util.Queue; Queue queue = new ArrayDeque(); // //또는 Queue queue = new LinkedList(); Java의 java.util.Queue는 interface다. 구현체로는 대표적으로 ArrayDeque 또는 LinkedList를 사용한다. 대부분의 상황에선 LinkedList보다는 ArrayDeque를 사용하자. ArrayDeque 양쪽 끝에..