소프트웨어 개발 프로세스

• 계획 → 오구 분석 → 설계 → 구현 → 테스트 → 배포 (→ 유지보수)
  • 분석한 요구사항을 만족하기 위한 설계 단계에서의 핵심이 알고리즘
  • 알고리즘을 구현하는 것이 코딩
  • 구현 후 테스트하며 문제를 발견하고 수정하는 것이 디버깅

알고리즘

• 특정 문제를 해결하기 위한 방법 또는 절차

• 알고리즘은 구체적으로 작성해야함

• 인간 짠 알고리즘을 컴퓨터에게 전달하기 위해 컴퓨터가 할 수 있는 언어로 표현하는 것이 프로그래밍

  • 그러나 프로그래밍에서만 사용되는 것은 아니다.

• 좋은 알고리즘 ?

  • 효율적 / 속도가 빠르고 / 알기 쉽고(직관적) / 정확한 / 재사용이 가능한것

• 왜 알고리즘을 공부해야 하는지 ?

  • 일을 효율적으로 수행하기 위해 / 문제에 적잡한 해결방법을 선택하기 위해 / 대용량 데이터를 효율적으로 다루기 위해 / 좋은 프로그램을 만들기 위해서/ 만들어진 프로그램의 좋고 나쁨을 판단하는 기준이 될 수 있다 / 코딩 기술을 향상 시키기 위해서

[9, 3, 2, 7, 5, 1, 4, 10, 6, 8]리스트(혹은 배열)이 있을때

• 크기가 작은 것 부터 정렬하려면 어떻게 해야 할까 ?
  • 여러가지 방법이 있을 수 있다.
    • 정렬 알고리즘이 될 수 있다.
• 정렬 : 정해진 규칙에 따라서 데이터 등의 순서를 맞춰주는 것 (오름차순 정렬)

파이썬으로 정렬 알고리즘

Interative Sorting(반복 정렬)

• 정렬 : 정해진 규칙에 따라 데이터 등의 순서를 맞춰 주는것

• 선택정렬(Selection Sort)

  • 최소값을 선택해 맨 앞에서부터 순서대로 나열
    • 기준노드 - 가장 앞에 있는 값부터 시작
    • 기준 노드 뒤로 가장 값이 작은 노드를 선택
    • 기준점과 최소값 노드 교환(swap)
    • 이 과정을 반복
    • 시간 복잡도 : 최선, 최악, 평균 O(N^2)

• 삽입 정렬(Insertion Sort)

  • 요소를 추출한 후, 앞에있는 값들과 비교해서 알맞은 자리에 삽입
    • 기준노드 - 두번째 노드부터 추출
    • 추출한 노드가 앞으로 이동하며 앞에있는 노드들의 값과 비교
    • 알맞는 위치에 삽입(swap 일어남)
    • 이과정을 반복
  • 시간복잡도
    • 최악/평균 : O(N^2)
    • 최선 : O(N)
      • 모두 정렬되어있는 경우