알고리즘 강의 1주차

알고리즘 첫걸음 ~ 알고리즘을 배우기 위한 준비

• 순차탐색의 개념 
  • 10개의 숫자 중 가장 큰 숫자를 찾는 방법 - 첫번째 숫자와 두번째 숫자를 비교하여 더 큰 수를 저장  > 저장된 값과 다음 값을 비교해가며 찾는 방법
• 이진탐색
  • 오름차순으로 정렬된 숫자들을 반으로 나누어 비교하고, 또 반으로 나누어 탐색
• 그리디 알고리즘
  • 거스름돈 문제 730원을 거슬러 줄 때 가장 이상적인 동전 갯수 => 6개
• 한붓그리기 문제
• 가짜 동전 찾기 문제

 

• 가장 오래된 알고리즘
  • 최대공약수 알고리즘
• 알고리즘 표현 방법
  • 자연어
  • 순서도 Flow Chart
  • 의사 코드 Pseudo Code  (일반적으로 사용)
  • 컴퓨터 프로그래밍 언어 

• 알고리즘 분류
  • 문제 해결 방식에 따른 분류
    • 분할정복 알고리즘 - 주어진 문제를 나눌 수 없을 때까지 나누어 답을 얻는 방법
    • 그리디 알고리즘 - 탐욕알고리즘이라고 불리우며, 최적화 문제를 해결하는 방법, 가능한 방법중 가장 좋은 방법을 찾는다
    • 동적 계획 알고리즘 - 최적화 문제 해결, 입력 크기
    • 근사 알고리즘 - 원래 답이 되는 해의 가장 근사한 값을 찾는 방법. 다항식의 시간복잡도를 가진다
    • 백트래킹 기법 - 역추적기법. 막혔을때 역으로 탐색
    • 분기 한정 기법 - 백트래킹기법의 단점을 보완한 탐색 기법
  • 문제에 기반한 분류
    • 정렬 알고리즘 - 10개의 임의의 정수가 무작위로 섞여있을때 오름,내림 차순으로 정렬
    • 그래프 알고리즘 - 정점과 간선들의 집합을 이용, 최단 경로 탐색 등
    • 기하 알고리즘 - 점, 선, 면과 같은 기하학 객체로 이루어진 문제를 해결
  • 특정환경에 따른 분류
    • 병렬 알고리즘 - 여러개의 컴퓨터를 네트워크로 연결하여 여러가지 작업을 동시에 처리하는 알고리즘
    • 분산 알고리즘 - 여러대의 컴퓨터를 이용하여 한가지 작업을 동시에 처리
    • 양자 알고리즘 - 양자학 컴퓨터를 이용
  • 기타 알고리즘 분류  - 패턴 인식
    • 확률개념이 사용되는 랜덤 알고리즘 - 난수 발생, 확률 분포 이용
    • 유전자 알고리즘 - 다윈의 진화론, 적자생존의 개념, 최적화문제 해결하는데에 적용
    • 신경망 알고리즘 - 인간의 정보처리 방식을 모델링
    • 기계 학습 알고리즘 - 머신러닝 알고리즘
    • 군집화 알고리즘 - 클러스터링 알고리즘
  • 알고리즘의 효율성 - 일반적으로 시간 복잡도 사용
    • 시간복잡도 - 알고리즘의 수행 시간
      • 기본적인 연산 횟수를 입력크기에 대한 함수로 표현
      • 순차 탐색 시간복잡도 (n-1)
    • 공간복잡도 - 사용되는 메모리 공간의 크기
  • 복잡도 분석 방법
    • 최악 경우 분석 - 최소한의 성능 보장
    • 평균 경우 분석 - 대체적인 성능
    • 최선 경우 분석 - 운이 좋은경우 낼수있는 성능 *유용하지않음
  • 복잡도의 점근적 표기 
    • 시간/공간 복잡도는 입력크기에 대한 함수로 표기. 점근적 표기
    • 점근 표기법 - '자세하게'의 반대말. 알고리즘의 수행시간을 대략적으로 표현
    • 입력크기 n이 무한대로 커질 때의 복잡도를 간단히 표기
      • O (빅오) - 최악의 경우 수행시간  
        • 가장 많이 사용하는 알고리즘 성능 표기법
        • O(n^2)  빅오의 엔제곱
      • 오메가 - 최소한의 수행시간
      • 세타 - 빅오와 오메가 모두 만족