[Introduction To Algorithms] CH1. 알고리즘의 역할

요약 혹은 연습문제를 기록합니다.

1.1 알고리즘

알고리즘이란, 입출력 문제를 해결하기 위한 잘 정의된 계산 절차

1. "정렬" 또는 "두 점 사이의 최단 경로" 문제 중 이런 문제가 발생하는 현실의 예

- 정렬 : 도서관 책이 저자순으로 정렬됨.

- 두 점 사이의 최단 경로 : 카카오 네비를 켜서 목적지까지 최단 경로를 확인함.

2. 현실에서 속도 외에 효율성을 평가할 만한 다른 척도로 무엇이 있는지

이때 속도라 함은, 최적의 해를 구하기까지의 기간일텐데

문제 측면에서 정말 적절한 문제 추상화가 이루어졌는지, 쓸모있는 문제인지?

(좀 더 고민 필요)

3. 예전에 본 적있는 자료구조 중 하나를 골라 그것의 장점과 한계를 각각 논하라.

스택 - 자체적으로 순서의 의미를 갖고 있음 / 찾고자하는 데이터가 맨 처음에 있다면, O(n)의 시간이 걸림.

4. 최단 경로 문제와 순회 판매원 문제는 어떻게 비슷한가? 그리고 어떻게 다른가?

- 최단 경로 문제 : 두 점 사이의 최단거리로 최적해가 존재함

- 순회 판매원 문제 : N개의 점 사이의 전체 이동 거리를 줄이는 해를 찾아야하며, 근사 알고리즘만 존재

5. 현실의 문제 중 최적해만 의미가 있는 문제를 제시하라. 반대로 최적은 아니지만 "근접한" 해를 구해도 충분한 문제를 제시하라.

- 최적해만 의미가 있는 문제 : 사내에서 김씨 성을 가진 사람을 찾기. 정답이 있음.

- 근접한해 : (모르겠음)

6. 문제를 풀기 전에 모든 정보를 미리 얻을 수 있는 경우도 있지만, 정보를 미리 얻을 수 없고 시간이 지나서야 얻을 수 있는 경우도 있는 실제 문제의 예

식당 웨이팅, AWS 서버 증설처럼 게스트가 방문의 주체가 되어 겪기 전까지는 그 정보를 미리 알 수 없음.

한정된 시간, 공간 측면에서 효율적인 알고리즘이 필요함.

1. 응용 프로그램 수준에서 알고리즘이 필요한 프로그램의 예를 들어라. 그리고 이용된 알고리즘 기능에 대해 논하라.

구글 검색 엔진, (논의 필요)

2. 동일한 기계에서 삽입정렬과 병합 정렬 구현결과를 비교한다고 가정하자. n개의 입력에 대해 삽입정렬은 8n^2번을 병합 정렬은 64nlgn번을 계산하고 각각 종료한다. n 값이 몇일때 삽입정렬이 병합정렬보다 빠를까?

n = 1, (삽입정렬) 8, (병합정렬) 0

n = 2, (삽입정렬) 32, (병합정렬) 128

헷갈리는데, 계산수가 적을수록 빠르다. 값이 더 작을때

계수에 의해 이 문제에 대해서는 n>=2 범위에서 삽입정렬이 빠르다.

3. 동일한 기계에서 수행 시간이 100n^2인 알고리즘이 수행 시간이 2^n 인 알고리즘보다 빨라지는 n의 최솟값은?

(재검토) n=0 일때밖에 없는데?? 항상 후자 알고리즘이 빠른뎅..

[종합문제] 수행시간비교

다음 표에서 각 f(n) 함수가 t 시간에 풀 수 있는 문제의 최대 크기 n을 구하라. 이때 각 알고리즘은 f(n) 마이크로초가 걸린다고 가정한다.

(테이블 채우는건 패스) 위로 올라갈수록 시간복잡도가 큰, 계산수가 많은 알고리즘