전체보기96 Introduction to Computational Complexity theory of a Problem: The sorting Algorithm Problem 이전까지는 주어진 문제를 해결하는 알고리즘 분석에 중점을 뒀었다. 즉 문제 자체의 속성보다는 특정 알고리즘의 속성에 초점을 맟췄었다. 예를 들어 순차 탐색 알고리즘의 시간 복잡도를 분석할 때 시간 복잡도는 \(\theta(n)\)이다. 이것은 당연히 탐색 문제에 \(\theta(n)\) 알고리즘이 필요하다는 의미가 아니다. \(T(n)=n\) 함수는 탐색 문제의 속성이 아닌 문제에 대한 탐색 알고리즘의 속성이다. 이 장에서는 계산 복잡도 이론(computational complexity theory)이라는 이론적인 컴퓨터 과학 분야에 대해 알아볼 것이다. 알고리즘 분석에서는 문제를 해결하기 위해 특정 알고리즘이 필요로 하는 리소스 양을 분석하는데 전념했지만 계산 복잡성 이론은 동일한 문제를 해결하는데 사.. 2021. 12. 13. Branch and Bound Method (분기 한정법) 이번에 알아볼 알고리즘 기법은 분기 한정법(Branch and Bound Method)이다. 이 글에서는 최적화 문제를 해결하기 위한 분기 한정 방법, 비슷한 기법인 역추적 기법과의 차이점을 알아볼 것이다. 그리고 어떤 문제가 분기 한정법을 사용하기에 적절한 문제인지 식별해보고, 이전 부터 계속 해왔던 0/1 배낭 문제를 해당 기법을 이용하여 해결해 볼 것이다. Introduction to Branch and Bound 역추적 알고리즘과 마찬가지로 분기 한정 알고리즘도 상태 공간을 사용하여 조합 문제를 해결한다. 그러나 분기 한정법은 방문할 다음 노드가 런타임 중에 결정되고 입력 인스턴스마다 다르기 때문에 트리 탐색 순서를 미리 결정하지 않는다. 또한 역추적 알고리즘은 최적화/비최적화 문제를 모두 해결할.. 2021. 11. 30. I/O Systems and Operations 이번에는 입출력 시스템&입출력 작업에 대해 알아볼 것이다. 다음과 같은 순서로 구성된다. An Overview of I/O Subsystem and Operations Stream Model: I/O functions, Standard streams Buffering: Block buffering vs. Line buffering vs. Unbuffered Pipes File I/O: File pointer, File Attributes Device I/O: Device Drivers, Block devices vs. Charater devices vs. Network devices I/O (Input/Output) 입출력은 컴퓨터의 주요 역할이다. 다른 작업인 컴퓨팅/처리는 부차적인 역할이다. 컴퓨터 .. 2021. 11. 29. Backtracking Algorithm Design Method (백트래킹 알고리즘) 이번에는 백트래킹 알고리즘에 대해 알아보자. 이 글에서 알아볼 것은 다음과 같다. 백트래킹 기술 설명 백트래킹 기법이 문제 해결에 적절한 접근 방식인지 판단 주어진 문제에 대한 상태 공간 트리 정의 주어진 문제에 대한 상태 공간 트리의 노드가 유망(promising)하거나 비유망(non-promising)한 경우 정의 상태 공간 트리를 제거하는 알고리즘 생성 주어진 문제를 해결하기 위해 백트래킹 기법을 적용하는 알고리즘 생성 여기서 상태 공간 트리(state-space-tree)란 문제 해결의 중간 상태를 각각 한 노드로 나타낸 트리이다. ※ P, NP Problem 백트래킹을 살펴보기 전에 P, NP에 대해 간단히 짚고 넘어가자. 이제 막 알고리즘에 대해 배우고 있는 입장에서 명확히 이해하기 어려운 개.. 2021. 11. 22. 이전 1 ··· 14 15 16 17 18 19 20 ··· 24 다음
