9._.coding

편집 거리 문제, Edit Distance Problem은 하나의 문자열을 수정해 Insert/Delete/Copy(또는 Substitute)를 사용하여 최소한의 횟수/비용으로 다른 문자열로 변환하는 문제이다. 하나의 문자열을 최소 시행을 거쳐 다른 문자열로 변환하기 위해서는 copy라는 과정을 꼭 거쳐야 한다. algorithm을 alligator로 바꾸는 예제를 살펴보자. Insert/Delete/Copy를 적절히 사용하여 사진에서처럼 변환해주면, (회색은 아직 하지 않은 부분, 남색은 삽입, 빨간색은 삭제, 보라색은 복사) 14번의 시행으로 변환을 마칠 수 있다. 그렇다면, 이게 그냥 다 지우고 다시 쓰는 것과 무슨 차이가 있을까? Copy를 사용해 문자열을 변환했을 경우에는 14번의 시행인데, a..

LCS 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. LCS의 개념 : [알고리즘] 최장 공통 부분수열 / LCS - Longest Common Subsequences Longest Common Subsequence, ..

Longest Common Subsequence, 줄여서 LCS는 주어진 여러 수열의 공통 부분수열 중에서 가장 긴 수열을 찾는 문제이다. 아래 예시로, 수열 x와 y가 있다고 하자. x는 ABCBDAB, y는 BDCABA일 때, 이 둘의 공통 수열은 매우 다양하지만, 그 중에서 가장 긴 수열은 BCBA이다. 이처럼 다양한 공통 수열 중에서 가장 긴 것을 찾는 문제이다. 문제 해결을 위하여 테이블을 구성하고, 일치하는 문자가 있을 경우 더해주는 방식의 DP를 사용했다. DP, 동적 계획법에 대한 내용은 아래 링크에 자세하게 설명되어 있다. [알고리즘] Dynamic Programming (동적 계획법) 동적 계획법, Dynamic Programming(DP)는 최적화 이론의 한 종류로, 특정 값을 구하기..

T(n) = aT(a/b) + f(n)의 형식일 때 마스터 정리를 활용해 시간 복잡도를 간단하게 계산할 수 있다.

Application Architectures 1) 클라이언트-서버 구조 서버 : - 항상 네트워크에 연결되어 있으며, 이를 Always-on Host라고 한다. - 고정 IP 주소 (Permanent IP Adress)를 가진다. 클라이언트 : - 서버와 소통하면서 네트워크에 연결되었다 끊겼다 함. - Intermittently Connected - 동적 IP 주소를 가질 수 있으며, 바뀔 때 서버에게 알려주어야 한다. 2) P2P 구조 - 간헐적으로 연결되는 호스트인 peer가 서로 데이터 교환을 할 수 있는 구조. - 개별적으로 서비스를 요청 및 제공하며, 관리가 복잡하다. - 임의의 End System이 직접 소통함. (peer) - 자가 확장성(Self Scalability) 자체적으로 확장성이..

T(n)의 복잡도를 추정하기 위해, 즉 알고리즘의 시간복잡도를 모델링하기 위해서 재귀트리를 사용합니다. 재귀트리를 이용해 시간복잡도를 구하기 위해서는 점화식이 필요한데, 점화식을 다양한 높이의 재귀호출에서 발생할 비용을 나타내는 노드가 있는 트리 구조로 변환합니다. 시간 복잡도를 구하기 위해 높이와 층별 노드합을 구해야 하는데, 높이는 n층에서의 일반항을 구해 나타내며(필기 참조), 노드합은 하나의 깊이에서 노드를 모두 더해 나타냅니다. 계수가 같고 합이 일정한 경우 점화식이 T(n) = 2T(n/2) + cn의 꼴이므로 T(n)은 호출 시마다 2개의 T(n/2)를 호출합니다. 따라서 트리가 그림과 같이 그려지게 되고, 각 층의 노드합은 cn이 되며, 그러므로 O(nlogn)의 시간복잡도를 가지게 됩니다..

동적 계획법, Dynamic Programming(DP)는 최적화 이론의 한 종류로, 특정 값을 구하기 위해서 다른 범위의 값을 이용해 효율적으로 값을 구하는 알고리즘으로, 쉽게 말해 답을 재활용하는 알고리즘이다. 답을 구하기 위한 계산을 반복하는 구조, 즉 같은 답을 계속 내서 다른 값을 이용해야 하는 문제(대표적으로 피보나치 수열)에 매우 뛰어난 방법이다. 분할 정복 기법 - 큰 문제를 작은 문제로 쪼개어 풀이하는 알고리즘에서 값을 저장하는 로직이 추가되었다고 할 수도 있다. 가장 중요한 아이디어는 문제를 재계산(예를 들어 재귀적으로 풀이하는 기법)하지 않는 것이고, 이를 막기 위해 값을 기억하거나 테이블을 만들어 해결한다. 그러므로, 최종 목표를 달성하기 위한 단계를 한 번 씩만 풀게 된다는 것을 ..

Problem I have some (say, n) marbles (small glass balls) and I am going to buy some boxes to store them. The boxes are of two types: T ype 1: each box costs c1 Taka and can hold exactly n1 marbles T ype 2: each box costs c2 Taka and can hold exactly n2 marbles I want each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them. Since I find it difficult ..

Problem In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad’s back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley’s engagement falls through. Consider Dick’s back to be a plane with freckles at various (x, y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink..

Problem Problems that require minimum paths through some domain appear in many different areas of computer science. For example, one of the constraints in VLSI routing problems is minimizing wire length. The Traveling Salesperson Problem (TSP) — finding whether all the cities in a salesperson’s route can be visited exactly once with a specified limit on travel time — is one of the canonical exam..