본문 바로가기

전체 글

 (163)
알고리즘18-2 완전 정보 게임 완전 정보 게임 (NIM GAME) : 정보가 공개되어 있어 승부가 정해져 있지만 계산할 수 없음 불완전 정보 게임 ex) 화투 놀이, 포커, 스포츠베팅 Win : 상대방이 무슨 수를 써도 반드시 이기는 방법 (하나라도) 있음 / Lose : 내가 무슨 수를 써도 못이김 9개를 받으면 내가 무슨 짓을 하더라도 진다. 배스킨라빈스 31게임이랑 같은 듯 나머지 칸에서 찾는다. 마지막칸에서는 제한없음
알고리즘18 다이나믹 프로그래밍 마지막 금화모으기 둘 중에 큰 값을 골라서 (i,j)의 코인을 더한다. 8원을 거슬려주는 방법 중 1원 동전을 한개 쓰는 방법은 8-1=7원을 거슬러주는 방법 연속으로 일할 수 없다. critical idea : 끝나는 순서를 보면된다. 1 2 3: 15만원이 최대 4: 20이 최대 5: 30이 최대 6: 30 (T9를 가져가게되면 T5를 가져가게 되고 27만원보다 전날까지 일한 것이 더 비쌈) 7. 15+25=40 8. 8번째 끝나는 일이없음 9. (20+27)=47 (T3을 가져오면 42) 10. 49 선택하지않으면 전날까지 받은 돈과 같음 p(j) = 마지막 작업과 안겹치는 작업 중 마지막 작업 (☆) 끝나는 날짜로 sorting이 되어있기 때문에 시작날짜를 넣어 binary search n개 중 k개 고..
알고리즘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 결합 법칙이 성립하기 때문에 어떤 순서로..

티스토리툴바