1.1 알고리즘

1.1 알고리즘

 

• 다량의 데이터 : 정보를 많이 얻을 수록 시간, 장비, 자금, 인적자원 등이 소요된다. 알고리즘 기술은 이러한 자원을 효율적으로 절약해준다.
• 빠른 서비스 제공 : 테이터가 전송되는 경로를 찾거나, 특정 정보가 있는 페이지를 빨리 검색하는 문제 등을 해결해준다.
• 보안 : 개인정보 공개키 암호화, 전자 서명 등의 핵심 기술은 수치 알로리즘과 정수론 등을 기반으로 만들어 졌다.
• 기업 기대 수익 극대화 : 석유회사 어디에 유정을 뜷어햐 하는지 결정, 정치 입후보자의 승리 가능성 높은 캠페인 예측, 최소 비용이 드는 승무원 스케줄 관리 및 배치, 추가 장비 배치할 위치 결정.

현실세계에서 알고리즘으로 최상의 해를 구하는건 불가능에 가깝다.

하지만 최적의 해를 찾는데는 효율적이라 할 수 있다.

 

📌 추후 공부할 내용들

• 최장 공통 부분 수열(longest common subsequence)
• 위상 정렬(topological sorting)
• 블록 덮게(convex hull)
• NP-완비 문제

 

📌 병렬성

컴퓨터 칩의 전력 밀도 한계(클럭 속도 증가로 인해 칩이 전력밀도 높아져 열에너지에 의해 칩이 융해될 위험이 생김)로 인해 시간당 계산 성능을 늘리기위해 컴퓨터 코어를 늘리기됨.

• 멀티 코어(cpu 여러개, parallel computer) - 무어의 법칙
• 멀티 프로세서
• 멀티 스레드 알고리즘(multithreaded algorithm)

 

📌 더 공부해볼 내용

동시성과 병렬성(컴퓨터 역사의 성능 개선)

동시성을 사용해 시스템을 보다 빠르게 동작할 수 있게 하였고

병렬성을 사용해 컴퓨터 시스템을 다양한 수준으로 추상화해 활용 가능해졌다.

---

📌 연습문제

1.1-1 

정렬 : 맛집 대기표, 은행 대기표, 대학교 예비번호 등의 대기자 목록

블록 덮개 찾기 : 재개발 구역 추척, 지도에 호우주의보 단계 설정 등에 쓰이는 듯 하다.

 

1.1-2

비용, 시간, 공간

 

1.1-3.

배열

장점 : 정보를 찾기 수월함. index로 접근 가능

단점 : 공간을 늘리기 쉽지 않음. 데이터 이동이 어려움.

한계 : 새로운 데이터 삽입, 추가, 변형 등에 한계가 있음 (복사 개념을 설명해주는 게 좋을듯)

 

1.1-4

최단 경로 문제와 순회 판매원 문제 둘다 모든 경우의 수를 고려해 최적의 케이스를 찾는다는 점에 공통점이 있다.

차이점으로는 최단 경로 문제는 비용보다는 시간, 거리에 가중치를 두고 있다. 반면, 순회 판매원 문제는 비용에 가중치를 두고 있고 다시 시작점으로 돌아와야 한다는 점에서 차이가 있다.

 

1.1-5.

최적해는 가장 가능성이 높은 즉, 확률이 높은 해를 찾는 것 같다.

최적해는 아니지만 근접한 해로는 수많은 지원자 들 중에 같이 일할 동료를 뽑는 케이스, 알리바이가 충분치 않아 범인으로 몰린 케이스 등 있다.

---

📌 오답 정리

 

1.1-3. 

배열 : 크기를 변경할 때 복사를 많이 해야 하는 한계가 있음.

 

1.1-4.

최단 경로 문제, 순회 판매원 문제

공통점 : 꼭지점, 가중치 및 최소 거리 기반으로 한 그래프 문제

차이점 : 최단경로 문제는 두 꼭지점 사이의 가장 짧은 경로만 고려한 문제인 반면, 순회 판매원 문제는 비용 최소화, 많은 꼭지점을 포함하고 시작한 위치에서 끝내야 하는 문제이다.

 

1.1-5.

테러 용의자를 추척한다고 가정하면, 최적해는 잘못된 결정을 용납할 수 없으므로 최적해 적용이 적절하기 않다.

하지만, 한 사람이 리스트에 있는지 등과 같은 대략적인 정보만 있으면 되는 문제, 운전 최단 경로 해결적 등은 최적해를 적용해도 크게 나쁘지 않다.

 

📌 참고한 책

"Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.