알고리즘 (54) 썸네일형 리스트형 알고리즘17-2 최장 공통 부분 서열(LCS) longest common subsequence subsequence는 떨어져 있을 수 있다. substring는 연속되어야 한다. -> substring은 subsequence if 1 뒤에 두개가 같으면 앞의 LCS+1이 전체의 LCS이다. (편집 길이와 같은 이야기) if 2 만약 마지막 글자가 다르다면 마지막 하나를 뺴고 LCS를 구한 것이 답 if 3 반대로 두 번쨰의 마지막 글자가 안들어간다면 빼고 구한 것이 답 1. 둘 중 하나의 길이가 0이면 0 2. 마지막 글자가 같으면 +1 3. 마지막 글자가 다르면 둘중에 큰 것 편집 길이와 같지만 change가 없다는 것이 차이. match이므로 insert/delete만 있다. 다른 설명 shortcut을 만들어둔다. 14 (대각선을 한번도 안탔을.. 알고리즘17 근사문자열매칭과 거리함수 KMP: 정확히 똑같은 것을 찾는다. 근사문자열 매칭 검색엔진의 유사어 추천 기능 거리함수 비슷하다는 정의는 여러개 있다. 정의가 복잡할 수록 현실과 가깝다. - 해밍거리 change ababc abbc 같은 자리끼리 비교한다. 다른 정도가 3 (스코어가 클 수록 먼 것) 옛날 통신에서 글자가 밀리는 일은 없지만 글자가 바뀔 수는 있다면 의미 있는 방법 - 편집거리 change,insert,delete 글자가 추가/삭제되어 올 수도 있음. abc def 와 def abc는 매우 달라진다. - 가중편집거리 change,insert,delete a가 s가 되는 것과 a가 p가 되는 것에 대한 가중치가 다르다. 오타 커버 가능 - 기타 block단위 편집거리 한 문자열을 다른 문자열로 변경하기 위해 필요한 편.. 알고리즘 16-2 이전 내용을 코딩하자. 외부 변수에 배열 입력: edge weight 아무것도 못거치는 건 weight값 넣어줌 (k=n-1까지는 이미 갖고 있는정보이므로 업데이트 순서는 상관없고 k만 새로 추가되어 업데이트) 위의 세 값을 이용해서 다른 층(밑의 그림)의 값을 정한다. k번째 줄은 i,j가 바뀌는 경우에 재사용..(?) 인터넷에서는 D가 2차원 배열이다. => 바로 아래 층만 사용해서 답을 구하므로 메모리 줄이기 가능 k=0,2,4...일때 0번 배열에 k=1,2,3...일때 1번 배열에 번갈아가면서 저장하겠다! 스탠다드 작전. 메모리 n층을 안쓰고 2층만 쓰도록 바꿈! 책에서는 3차원 배열이 아예 없음! 원래 다른 층을 사용했지만 두 배열을 같은 배열로 구현해야 한다. k를 계산할 때 k-1에 있는 .. 알고리즘16-1 모든 쌍의 shortest (길이만 구하기. 실제 path까지 구하는 것은 조금 어려우니 skip) 그래프에서 source가 정해지면 다른 노드로 가는 shortest path구하기 노드가 n개 있다면 출력할 값이 n^2개 1번에서 2번으로 가는 shortest path 2번에서 1번으로 가는 shortest path는 undirect냐 direct냐 에 따라 다르지만 undirect graph로 설명하겠다 => 같다 입력과 바로 매치가 안되서 어렵다. * Dijkstra로 다 돌리면 시간이 O((m+n) log n) 보통 m>n이기 때문에 O(m logn)라고 표현 가능 (m: edge갯수 , n:node갯수) 모든 쌍의 Shortest Path구하기는 source node를 정하기 위해 이 과정을 n.. 알고리즘15-2 연속된 subarray중에 합이 제일 큰 것을 찾아라. (+/- 섞여 있음) 2~8까지가 정답. O(n^3) : 쉬움 연속된 모든 subarray 경우를 다 해본다. n개 중 점 2개를 찍는 방법 O(n^2) : Prefix Sum n^2개의 영역을 잡는 것은 같다. 하지만 합을 계산할 때 앞을 보고 계산하는 것이 아니라 미리 계산해둔 결과의 차를 이용한다. * 답으로 zero개의 배열을 허용할 것인가? 에 따라서 답이 다르다. 최소 하나를 포함해야 한다면 -1이 정답이지만 크기가 0인 배열을 허용한다면 정답은 0임. 풀이는 비슷하지만 전혀 다른 문제가 된다. O(n) : zero허용한다고 가정 모든 자리에서 끝나는 가장 좋은 답(가장 합이 큰 것 찾기) 사이즈 0 허용하므로 칸이 아니라 경계에서 끝난다.. 알고리즘15 집에서 학교까지 갈 수 있는 거리 계산 가로8 세로5 = 13C5 지나갈 수 있는 길 분리 8x5 4x7x3 (이해x) 5x8 하지만 이건 사람이 풀 수 있게 되어있다. 모든 위치에 대한 방법의 갯수를 구하기 칸마다 주어진 입력 값으로 계산하기 떄문에 역시 어렵지 않다. 추천 시스템 등..페이스북에서 함께 아는 친구도 Path Counting사용! 네모들은 매트릭스 일정 범위 내의 값을 계산한다. (동그라미는 계산 값) 이전 시간에 나온 식 다시 설명하겠음 M1 x M2 x M3 x ... x Mn 을 계산하는 최적 cost는? => 너무 많다. 마지막 곱하기를 기준으로 생각하자. (어느 것을 마지막으로 곱할 것인가? ) M1 x M2 x M3 x ... x Mn 결합 법칙이 성립하기 때문에 어떤 순서로.. 14-2 15-1 추가된 내용 전형적인 동적 프로그래밍 문제 일하면 받는 돈이 써있다. 단, 연속된 날은 일할 수 없다. 마지막 날이 일할 수도, 안할 수도 있다. 마지막날에 일하는 날 중 제일 좋은 답이 있을 것이고 마지막날에 일 안하는 날 중 제일 좋은 답이 있을 것이다. 마지막 전날은 마지막 날에 영향을 받는다. 마지막 날을 제외하고 가장 좋은 답을 구하기 둘 중 하나는 제일 좋은 답일 것이다. 앞에서부터 계산해두면 뒤에서 사용할 수 있다. 인덱스0: 그 날 일을 안하는 것중에 제일 좋은 것 인덱스1: 그 날 일을 하는 것중에 제일 좋은 것 배열 생성하고 첫 날 일을 할 때&안할 때의 초기값을 넣어준다. day2부터 계산한다.{ 그 날 일을 안할 때 = MAX(그 전날 일 할때 , 그 전날 일 안할때) 그 .. 14 Dynamic Programming Dynamic Programming 굉장히 어려운 문제가 쉽게 풀리게 해준다. 어떨 때 사용할 수 있는지, 어떻게 동작하는지를 알기 위해 큰 틀을 보겠다. 기본적으로 재귀 재귀는 독립적으로 실행할 수 있어야 한다. 전체 문제가 있고 잘라서 자른 문제가 전체인 것처럼 동작한다. 머지소트는 왼쪽 배열이 오른쪽배열의 영향을 받지 않는다. 하지만 그래프와 같은 경우는 영향을 받을 수 밖에 없다 완전히 독립적으로 잘라서 재귀로 적용하기 힘들다. 독립적인 부분문제의 답으로 전체의 답을 만든다는 점에서 분할정복과 비슷하지만 재사용에서 다르다. 피보나치에서 F(n)의 값은 변하지 않는다. F(6) = F(5) + F(4) F(7) = F(6) + F(5) 여러 곳에서 쓰이지만 F(5)의 값은 같다. By Recursi.. 이전 1 2 3 4 5 6 7 다음
