본문 바로가기

Algorithm

(35)

KMP 알고리즘 알고리즘 소개 KMP 알고리즘은 특정 문자열에서 특정 문자열의 패턴이 존재하는가를 판단할때 유용하다. ex) "AAABCCDEFSDFSWESSSAAWWSSW" 문자열에서 ABC 문자열이 존재하는지를 찾기 위해서는 일반적으로 찾기위해서 N*M 번 모든경우를 뒤저야한다. 하지만 KMP 알고리즘을 사용한다면 훨씬 빠르게 pattern을 찾을 수 있다. 여기서는 접미사와 접두사의 개념을 이해해야한다. 접두사 : 문자열의 앞쪽 접미사 : 문자열의 끝쪽 즉 찾을 문자열의 접두사와 접미사의 비교를 통해 반복적으로 일어나는 문자열의 길이와 위치를 알수 있으면 실제 문자열에서 찾을때 처음부터 다시 찾는것이아니라 반복적으로 일어난 패턴에대해서는 이미 같을 것이니깐 거기서부터찾는 것이다. ex) ABDABC 라는 무자열 이..

투 포인터 알고리즘 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 백준에 예제에서 한번 배워보자 투포인터 알고리즘이란 두개의 포인터지점을두어 특정 조건일때 rear값을 상승시키면서 중첩해가면서 계산하다가 답이아닌경우 front 증가시키면서 정답을 찾아가는 방법이다. 수들의합 2의 예제 2번으로 예시를 들겠다. 현재 구하는 M = 5라고 한다면 front =0 , rear = 0 을 가리키는 상태이다. 이때 sum = 1 이된다. 구할려..

알고리즘 공부할것들 1) 기초 - 완전 탐색(Brute-force Search) - 탐욕적 기법(Greedy) - 분할 정복(Divide and Conquer) - 이분 탐색(Binary Search) - BFS, DFS - 정렬 - 구현 2) 자료구조 - 리스트(List), 배열(Array) - 스택(Stack) - 큐(Queue), 데크(Dequeue) - 트리(Tree) 3) 초급 - 백트래킹(Backtracking) - 비트마스크(Bit Masking) - 구간 합 배열(Prefix Sum) - 우선순위 큐(Priority Queue) - 유니온 파인드(Union-Find) - 투 포인터 - 슬라이딩 윈도우(Sliding Window) - 그래프 최단 경로: 다익스트라 알고리즘(Dijkstra’s Algorithm)..

LCA(Lowest Common Ancestor) Tree는 deep를 가지는 자료구조이다. LCA는 직역하면 최소 공통 조상이라고 한다. 7과 5의 최소 공통 조상은 2 가될것이다. 문제를 푸는 방법은 7과 5의 deep중 깊은 deep를 위로 올리면서 같은 deep일때 써로를 비교해주는 O(N) 시간으로 문제를 해결 할수 있다. 하지만 만약 쿼리가 많은 문제에 대해서는 어떻게해야할까?? 같은 깊이를 빠르게 찾을 특별한 자료구조가 필요해보인다. 7번을 보도록 하겠다. 7번의 1번째 조상은 4 2 번째 조상은 2 이다. 이러한값을 배열에 미리 저장해둔다면 공통 조상을 찾는데 걸리는 시간은 O(longN)이 된다. 처음 배열을 만드는 비용 O(N*K) 가드는데 K는 log2 ( 최대N) 을 해서 나올수 있는 값이다. N가 100000이라면 2^20 > N..

LinkedList : java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 public class Linkedlist { static class Node{ Object data; Node link; public Node(Object data) { this.data = data; } public Node(Object data, Node link) { super(); this.data = data; this.link = link; } @Override publ..

파라메트릭 예정

JAVA : nextPermutation 다음순열 nextPermutation 구현의 아이디어 nextPermuation이란 [1,2,3,4,5] ->[1,2,3,5,4] ->[1,2,4,3,5] 처럼 현재의 상태에서 다음 순열을 찾는 알고리즘이다. 물론 조합 알고리즘을 이용해서 각각의 인덱스의 조합을 이용해서 찾아도 되지만 더빠른 넥스트 퍼뮤테이션을 사용해야 할때가 있다. 기본 순열 1 3 5 4 2 에 대해서 예를 들어보자! 아래와 같은 순열이 이어저있을 때 nextPermutation은 다음과 같은 4가지 조건을 확인 하면된다. 모든 탐색은 오른쪽에서 왼쪽으로 시작한다. 1. arr[i-1] < arr[i] 이 오른쪽에서 왼쪽으로 탐색하면서 제일처음 나오는 값을 찾는다. 2. 이제 i-1를 비교하면서 arr[i-1] < arr[j] 를 만족하는 값..

TreeSet : 트리에서 인덱스 번호 반환, 범위 값출력 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 package LineSweep; import java.util.TreeSet; public class TreesetTest { public static void main(String[] args) { TreeSet set = new TreeSet(); set.add(5); set.add(1); set.add(7); set.add(4); set.add(9); set.add(0); //TreeSet 의 인덱스번호를 반환하는 방법 System.out.println("인덱스 번호 반환"); System.out.println(set.headSet(1).size()); System..

이전 1 2 3 4 5 다음

티스토리툴바