'자료구조 & 알고리즘' 카테고리의 글 목록 (9 Page)

자료구조 & 알고리즘/BOJ2023. 11. 29. 00:38[Java] 백준 16916번 문제 (부분 문자열)

문제설명 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static public boolean KMP(String str, String pattern) { int LPS[] = new int[pattern.length()]; //LPS 배열 생성 int index = 0; //IDX, 찾을 문자열의 비교 인덱스를 뜻하기도 하며, 접두사와 접미사가 같을 때 최대 길이를 뜻하기도 함 for (int i = 1; i < pattern.length(); i++) //LPS배열의 값을 입력 { if (pattern.charAt(i) == pattern.charAt(index)) LPS[i] = ++i..

자료구조 & 알고리즘/BOJ2023. 11. 29. 00:36[Java] 백준 1786번 문제(찾기)

문제설명 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; public class Main { static public ArrayList KMP(String str, String pattern) { ArrayList idxList = new ArrayList(); //찾는 문자열을 발견시 해당 문자열의 시작 인덱스를 저장하는 리스트 int LPS[] = new int[pattern.length()]; //LPS 배열 생성 int index = 0; //IDX, 찾을 문자열의 비교 인덱스를 뜻하기도 하며, 접두사와 접미사가 같을 때 최대 길이를 뜻하기도 함 for (int i = 1..

자료구조 & 알고리즘/알고리즘2023. 11. 28. 00:54[Java]KMP 문자열 탐색 알고리즘

KMP 알고리즘이란 이 알고리즘을 만든 Knuth, Morris, Prett 이렇게 3명의 앞 글자를 하나씩 따서 명명하여 KMP 알고리즘이라고 한다. KMP 문자열 탐색 알고리즘의 시간 복잡도는 O(N+M)이다.(전체 문자열 길이 = N, 찾는 문자열 길이 = M) LPS 배열 계산 O(M) + 매칭 O(N) KMP 알고리즘의 핵심 아이디어 IDX 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Text A B C D A B D A B C D A B E A B C D Pattern A B C D A B E 위 표에서 text와 pattern 모두 0, 1번째 인덱스와 4, 5번째 인덱스의 값이 동일하다는 것을 알 수 있다. 즉, 앞에서 2개 뒤에서 2개가 같다는 것을 알 ..

자료구조 & 알고리즘/알고리즘2023. 11. 25. 22:14[Java] 라빈-카프 문자열 탐색 알고리즘

https://coding-food-court.tistory.com/216 위 글에 있는 내용과 그림을 참고하였습니다. 다만, 코드에 오류가 있어서 수정하였습니다. 길이가 M인 전체 문자열에서 길이가 N인 문자열을 찾는다고 하면 시간 복잡도 O(M*N)인 알고리즘이다. 이렇게도 풀수는 있지만 시간 복잡도가 상당하다. 라빈-카프 문자열 탐색 알고리즘을 사용하면 시간 복잡도가 O(N)으로 감소한다. 라빈-카프의 원리 찾는 패턴의 길이만큼을 전체 문자열과 찾는 문자열의 해시 코드로 비교한다. 만약 전체 문자열과 찾는 문자열의 해시 코드가 일치한다면 하나씩 비교해가면서 정말로 맞는지 확인한다. 이렇게 한 번더 비교하는 이유는 해시 충돌때문이다. 해시 충돌 A = 0, B = 1, C = 2라고 하고 해시함수가 ..

자료구조 & 알고리즘/BOJ2023. 11. 25. 00:55[Java] 백준 1212번 문제 (8진수 2진수)

문제설명 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); String input = br.readLine(); String[] arr = {"000","001","010","011","100","101","110","111"}; for(int i = 0; i < input.length(); ..

자료구조 & 알고리즘/BOJ2023. 11. 17. 19:13[Java] 백준 1991번 문제 (트리 순회)

문제설명 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static StringBuilder sb = new StringBuilder(); static Node root = new Node(null, null, null); //루트노드 static class Node //노드 클래스 { String value; //현재 노드의 값을 저장 Node left; //왼쪽 자식 노드의 레퍼런스를 저장 Node right; //오른쪽 자식 노드의 레퍼런스를 저장 Node(String value, Node left, Node right) { ..

자료구조 & 알고리즘/BOJ2023. 11. 17. 04:58[Java] 백준 2606번 문제 (바이러스)

문제설명 소스코드 DFS풀이(스택) import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public class Main { static int N; //vertex static int M; //edge static int V; //첫 탐색 static boolean visited[]; //방문 표시 static int vertex[][]; //인접 행렬 static int count = 0; //감염된 컴퓨터 수 static void DFS(int V) //첫 탐색 위치를 매개변수로 받음 { Stack stack = new Stack();..

자료구조 & 알고리즘/BOJ2023. 11. 17. 04:17[Java] 백준 1260번 문제 (DFS와 BFS)

문제설명 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; import java.util.StringTokenizer; public class Main { static int N; //vertex static int M; //edge static int V; //첫 탐색 static boolean visited[]; //방문 표시 static int vertex[][]; //인접 행렬 static StringBuilder sb = new StringBuilder(); static void DFS..

1 ···6 7 8 9 10 11 12 ···34

티스토리툴바