자료구조/자료구조 이론 (14) 썸네일형 리스트형 편집거리 알고리즘 점화식 1. 문자열의 해당 위치 값이 같을때 => D_ij = D_(i-1)(j-1) 대부분의 DP테이블은 2차원이 기본이다. str1을 몇번 수정하면 str2로 만들 수 있을까? str1[1] == str2[1] 이면 edit이 필요없다. 그래서 i-1, j-1의 위치의 값을 그대로 넣는다. 2. 해당 위치 값이 다를때 =>추가가 됐거나, Delete됐거나, Edit됐거나 편집거리 최소인 거리 추적하기 왼쪽, 왼쪽 위, 위쪽 으로부터 왔는지 저장해야한다. => 값을 누가 바꿨는가를 보고 봄ㄴ서 찾는 것이다. 왼쪽인 경우 삭제 왼쪽 위 edit 위쪽인 경우 단어 추가 --> 헷갈리니까 책에 있는 표 보지말자 그냥 아래 블로그 표 보자 hsp1116.tistory.com/41 편집 거리 알고리즘(Leven.. 최장 증가 부분 수열 LIS 찾기 Brute-froce 접근 부분집합중에 오름차순인 것중에 가장 길이가 긴 것을 찾는다 2^n의 시간복잡도라서 풀수 없을 수 있다. DP접근방법 n-1 에서 n의 상태가 되는 것을 찾아보자(주의할점은 꼭 n-1만 생각할 필요는 절대 없다. n-2, n-3 까지 더 멀리 있을 수도 있다) LIS table의 성격은 LIS(i)는 i번째 원소를 가장 끝 값으로 하는 연속된 숫자 최대 개수!!! 제발 DP에서 i번째 테이블의 값을 정의를 분명히해야한다 앞에서 부분집합을 가지고 1. i번째 숫자가 LIS(i)에 포함되는 경우 LIS(i)란? LIS(i)_ = 1+ maxLIS(j) j가 i보다 작으면서 aj 한번 구현해보는 것 중요할것같다. 모든 쌍 최단 경로 Brute- force 접근 방법으론 시간 복잡도가 O(n!)이므로 풀 수 없다. DP접근적으로 다익스트라 알고리즘을 n-1번 돌리는 것과 시간복잡도가 동일하다 O(n^3) 플로이드 알고리즘은 매우 간단하여 다익스트라 알고리즘을 사용하는 것보다 효율적이다!!! D_ij(직접가는 거리) 와 D_ik + D_kj(경유해서 가는 거리) 중에 짧은 거리를 선택하면 된다. 3중 for루프 + Dijkstra의 거리갱신 알고리즘 불필요한 연산을 피하기 위해서 경유지, 출발지, 도착지는 같으면 안된다 -> 이런 처리를 하지 않아도 최단거리는 구하는데 문제없다. 워샬 플로이드 알고리즘 수행과정 simuliation 1번 정점을 경유해서 간다고 하면 (k=1) 최단거리가 바뀐다. 2번 정점을 경유해서 간다고하면 최단거리.. Femwocl Tree 구간합을 빠르게 구하고 싶은데 Segment Tree의 진화형-> Segment Tree의 Left child만 저장하는 구조라고 생각하면 된다. 장점 1. Segment Tree에 비해 메모리 사용량이 준다. 구현 power of 2는 현재까지의 모든 구간합을 의미하고 홀수 인덱스는 실제 값을 의미한다. 짝수인덱스는 바로 직전 홀수 인덱스+ 짝수인덱스의 합 기본연산 update(p, v) : p인덱스 위치의 값에 v를 더한다 query(r): 1, r구간에 대한 질의 query(l, r) : l, r구간에 대한 질의 Bit연산을 잘활용하는 게 좋다 ex) pSum[7]을 구하려면 7 = 111이므로 => tree[111] + tree[110] + tree[100] 을 더하면된다. -> 연산은 오른쪽 끝.. 4월 6일 수업 Segment tree =>적절하게 전처리(하위 노드들의 합) 을 유지하여 계산을 가속화 하기 위한 트리 => 항상 균형 잡힌 이진트리 일차원배열로 표현(완전 이진 트리로 푷ㄴ) segmenttree를 만드는 방법은 2^h+1의 최대노드로 만들면 된다. 귀찮으면 4n으로 잡아도괜찮다. 담당구간을 가지고 Search를 하고 연산을 하는 판단을 하게 된다. segment tree의 합을 구하는 알고리즘 -> 해당 node의 담당 구간을 start, end라고 하고 합을 구해야하는 구간을 left, right라고하자. 노드가 담당하는 구간의 경우는 총 4가지가 있다. 1. left, right, start, end가 겹치지 않는 경우 -> 더이상 탐색할 필요가 없다 찾고자하는 노드가 없는 것이다. 2. left, right가 sta.. [알고리즘] 문자열 심화 문자열을 어떻게 핸들링할 것인가. C: delimited Java: length controll 방식 C의 장점은 문자열의 sub string을 핸들링할때 발현된다! (특히, Suffix array) 컴퓨터에서의 문자표현: 정수화해서 저장하고 사람이 원할때 화면에 표현해주는 것이다. 2차 대전 당시에 컴퓨터는 덩치가 크고 연산속돡 느리고 가격이 고가, 각 지역마다 영어를 표현하는 코드값이 다 다랐다. 국방성에서 네트워크라는 것을 보급해서 컴퓨터가 연결되었는데 지역 컴퓨터가 연결되었다. 이때 코드체계가 달라서 해석이 안된다. 그래서 나온게 1967년에 표준 ASCII코드를 만들었다. 총 7bit 인코딩으로 0~32의 출력 불가능한 제어문자와 33~ 126까지의 ASCII문자들로 구성된다. 최소한 프로그래머.. Back tracking 구조를 따라서 만들자! 부분집합을 출력하는 코드 #include using namespace std; const int N = 5; const int CANDIDATE = 2;// 선택 후보 (포함이냐 불포함이냐) int src[]{ 6,2,3,8,4,5,1 }; void process_solution(int a[], int k, int n) { cout DFS,BFS 구현(같은 알고리즘사용하지만 서로 최적임) #include #define GRAPH_SIZE 7 using namespace std; int stack[100]; int top = -1; int visit[GRAPH_SIZE + 1]{ 0, }; int fromTo[GRAPH_SIZE + 1][GRAPH_SIZE + 1]{ 0, }; int queue[100]{ 0, }; int qstart = -1; int qend = -1; void enqueue(int v) { queue[++qend] = v; } int dequeue() { return queue[++qstart]; } int isQEmpty(){ return(qstart == qend); } void push(int v) { stack[++top] = v; } int pop() { re.. 이전 1 2 다음