[중간고사] 0. Introduction

예상문제 - 기본 개념

 

문제: 답을 찾기 위해 제기된 질문

ex) 리스트 S의 n개의 숫자를 오름차순으로 정렬하십시오.

 

매개변수: 문제의 설명에서 특정 값을 할당받지 않은 변수, 주로 문제의 입력

 

인스턴스: 입력 매개변수에 값이 할당된 특정 지정

ex) S = [10, 7, 11, 5, 13, 8], n = 6 // 길이가 6인 S의 배열에 값 할당

 

해결책: 문제에 대한 답변

ex) [10, 7, 11, 5, 13, 8] → [5, 7, 8, 10, 11, 13]

 

해결책

· 문제를 해결하는 단계별 절차

· 컴퓨터 프로그램의 아이디어

· 언어(C++, 파스칼, 파이썬)나 환경(Mac, Windows, Linux 등)에 관계없이 항상 동일

· 흥미로운 알고리즘은 일반적으로 지정된 문제를 해결해야함(구체화된 일반적 문제)

  · 입력: 작동해야 하는 인스턴스의 집합 ex) a1, a2 ... an의 N개의 숫자

  · 출력: 출력이 가져야 하는 원하는 속성 ex) 입력의 순열(재배열)

 

예상문제 -  반례(counter example)를 찾아보는 문제

 

ex) The set cover problem is as follows: given a set of subsets S1, ..., Sm of the universal set U = {1, ..., n}, find the smallest subset of subsets T ⊂ S such that ∪ti∈T ti =U. Example: there are the following subsets, S1 = {1, 3, 5}, S2 ={2, 4}, S3 = {1, 4}, and S4 = {2, 5}. The set cover would then be S1 and S2. Find a counterexample for the following algorithm: Select the largest subset for the cover, and then delete all its elements from the universal set. Repeat by adding the subset containing the largest number of uncovered elements until all are covered.

 

1. 커버로 가장 큰 부분집합을 선택한 후, 해당 부분집합의 모든 요소를 전체 집합에서 제거

2. 모든 요소가 커버될 때까지 커버되지 않은 요소가 가장 많은 부분집합을 추가로 선택하여 반복

 

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} S1 = {1, 2} S2 = {2, 3, 4, 5} S3 = {6, 7, 8, 9, 10, 11, 12, 13} S4 = {1, 3, 5, 7, 9, 11, 13} S5 = {2, 4, 6, 7, 10, 12, 13}

set cover = {S3, S2, S1} 그러나 최적으로 볼 수 없는 이유는 {S4, S5}일 때가 최적이기 때문이다.