본문 바로가기

프로그래밍/Algorithm - 2

 (14)
14. Intractability 1. Introduction 우리는 앞서서 DFA(Deterministic Finite Automata)라는 기계를 배웠다. 이 기계는 매우 강력하여 수많은 계산을 위한 모델이 될 수 있다. DFA는 Tape와 Tape head를 가지는 추상화된 기계인데, Tape는 input을 저장하고, finite symbol들을 가지고 있다. Tape head는 Tape의 input을 하나씩 차례대로 읽어들인다. 그런데, 이보다 더 강력한 기계가 존재하는데 바로 Turing machine이다. Turing machine의 Tape는 input을 저장할 뿐만아니라, output, intermediate result 또한 저장한다. finite symbol들을 가진다. Tape head는 Tape의 input을 차례로..
13. Linear Programming 1. Brewer's problem Brewer's problem은, 맥주공장에서 한정된 자원을 가지고 어떻게 맥주와 에일을 생산해야 최대의 이익을 올릴 수 있는지 결정하는 문제이다. 자원은 이미 한정되어 있고, 맥주와 에일을 1개 생산하는 데는 특정 수치의 자원의 조합을 투입해야 한다. 예를 들어, 자원 X가 480, Y가 160, Z가 1190개가 있다고 해보자. 맥주 A를 만드는데는 X, Y, Z가 각각 5, 4, 35개가 필요하다. 에일 B를 만드는데는 X, Y, Z가 각각 15, 4, 20개가 필요하다. 맥주 A는 개당 13달러의 이윤을, 에일 B는 23달러의 이윤을 남기고, 이윤을 최대화 하고 싶다. 이를 A는 맥주 생산량, B는 에일 생산량 변수로 하여 방정식으로 표현하면 다음과 같다. 최대..
12. Reductions 1. Introduction Reduction이란 다음을 의미한다. If you can use an algorithm that solve Y to help solve X, Problem X reduces to problem Y 즉, 문제 X를 문제 Y를 푸는데 사용한 알고리즘을 활용해 해결할 수 있으면, 문제 Y로 축소된다고 보는 것이다. 우리는 문제 X에 대한 인스턴스를 문제 Y에 대한 인스턴스로 변환(preprocessing)하고, 알고리즘으로 해결한 후, 다시 결과를 변환(postprocessing)시킨다. 따라서 문제 X를 해결하는 총 비용은, 문제 Y를 해결하는 비용 + Reduction 비용이다. 예를 들어, N개의 item에 대한 중간값을 구한다고 해보자. Preprocessing없이, 바로..
11. Data Compression 1. Introduction Date compression을 통해 우리는 정보를 손실없이 유지하면서 저장공간과 데이터 전송시 시간을 줄일 수 있다. 많은 파일들은 redundancy를 가지고 있고, 이를 제거하는 것이 data compression의 핵심이다. Moore's law에 의해 우리는 이전보다 더욱 많은 저장공간과 빠른 속도를 가지게 되었지만, 그만큼 더 많은 데이터들이 생산되고 있다. 따라서, data compression이 여전히 매우 중요하다. 파일 압축, 이미지 압축, 커뮤니케이션 등 여러가지 영역에서 data compression이 응용되고 있다. Data compression과정은, bitstream B를 compress하여 C(B)를 만들고, 다시 expand하여 original ..
10. Regular Expressions 1. Regular Expressions(REs) Resular Expression은 특정한 문자열 집합을 표현한다. 이메일인지 여부, 올바른 전화번호인지 여부 등 입력값이 올바른 형태인지를 검증할 때 쓰인다. 집합의 요소가 무한할 경우 모든 문자열들을 저장해놓고 모든 케이스에 대해 비교를 하는것은 불가능하므로, Regular Expression은 유용하다. Regular Expression을 작성하기 위한 operation 종류는 다음과 같다. operation order example RE matches concatenattion 3 AABAAB AABAAB or 4 AA | BAAB AA, BAAB closure 2 AA*A AA, ABBBBBA parentheses 1 A(A|B)AAB AAAAB..
9. Substring Search 1. Introduction Substring search란 길이 N의 텍스트에서 길이 M인 패턴을 찾는 것이다. 스팸메일을 찾거나, 유저의 입력으로부터 URL이나 RSA키를 찾는 것, 웹 스크레이핑 등 여러가지 문제를 푸는데 응용된다. 2. Brute force Algorithm Brute force는 모든 경우에 수에 대해 하나씩 하나씩 검사하면서 패턴이 존재하는지 찾는 방법이다. 예를 들어, 입력값이 ABACAD이고, CAD인 패턴을 찾고싶다고 해보자. ABA, CAD를 비교한다. 일치하지 않으므로 다음으로 넘어간다. BAC, CAD를 비교한다. 일치하지 않으므로 다음으로 넘어간다. ACA, CAD를 비교한다. 일치하지 않으므로 다음으로 넘어간다. CAD, CAD를 비교한다. 일치하므로 찾은 것이다..
8. Tries 1. R-way tries Symbol table의 검색은 크게 red-black BST, hash table을 통하여 이루어 질 수 있었다. Hash table은 constant time의 검색/삽입/삭제를 지원하지만, ordered operation이 불가능하였고, red-black BST는 ordered operation이 가능하지만, logarithmic time의 검색/삽입/삭제가 이루어 졌다. 특별히 Symbol table의 Key가 String인 경우 우리는 character의 갯수가 R로 제한되어있다는 것을 이용하여 red-black BST보다 성능을 더 향상시키면서 ordered operation을 가능하게 할 수 있다. tries라는 이름은 retireval 로부터 나왔고, 우리는 tr..
7. String Sorts 1. Strings in Java String 는 Sequence of characters 이며, 굉장히 중요한 Abstraction이다. C언어에서 char은 8bit integer이고, 256개의 문자를 표현할 수 있으며, 7-bit ASCII를 지원한다. JAVA에서 char은 16bit unsigned integer이고, 16bit Unicode와 21bit Unicode 3.0을 지원한다. Java에서 Sting type은 immutable하고, 다음과 같이 구현된다. public final class String implements Comparable{ private char[] value; //문자들 privatee int offset; //첫번째 문자가 시작하는 지점 private int ..

티스토리툴바