알고리즘

• 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다.
  주로 컴퓨터용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법을 말한다.

• 간단하게 다시 말하면 어떠한 문제를 해결하기 위한 절차하고 볼 수 있다.

• 컴퓨터 분야에서 알고리즘을 표현하는 방법은 크게 두 가지

  • 의사코드(슈도코드, pseudocode)와 순서도
    

• APS과정
  APS과정의 목표 중의 하나는 보다 좋을 알고리즘을 이해하고 활용하는 것

• 무엇이 좋은 알고리즘인가?

1. 정확성 : 얼마나 정확하게 동작하는가
2. 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가
3. 메모리 사용량 : 얼마나 적은 메모리를 사용하는가
4. 단순성 : 얼마나 단순한가
5. 최적성 : 더 이상 개선할 여지없이 최적화되었는가

• 주어진 문제를 해결하기 위해 어떤 알고리즘을 사용해야 하는가?

• 알고리즘의 성능 분석 필요
  예)
  

• 알고리즘의 작업량을 표현할 때 시간복잡도로 표현한다.

• 시간복잡도

  • 실제 걸리는 시간을 측정
  • 실행되는 명령문의 개수를 계산

• 알고리즘의 성능
  

시간 복잡도 = 빅-오(O) 표기법

• 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시

• 계수는 생략하여 표시

• 예)
  

• 요소 수가 증가함에 따라 각기 다른 시간복잡도의 알고리즘은 아래와 같은 연산 수를 보인다.
  

배열

• 배열이란 무엇인가

  • 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조
  • 6개의 변수를 사용해야 하는 경우 이를 배열로 바꾸어 사용하는 예.
    

• 배열의 필요성

  • 프로그램 내에서 여러 개의 변수가 필요할 때, 일일히 다른 변수명을 이용하여 자료에 접근하는 것은 매우 비효율적인 수 있다.
  • 배열을 사용하면 하나의 선언

• 1차원 배열의 선언

  • 별도의 선언 방법이 없으면 변수에 처음 값을 할당할 때 생성
  • 이름: 프로그램에서 사용할 배열의 이름
    Arr = list(), Arr = [], Arr = [1, 2, 3], Arr = [0] * 10

정렬

대표적인 정렬 방식의 종류

• 버블 정렬

버블 정렬

2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값, 혹은 그 반대의 순서대로 재배열하는 것

• 정렬 과정

  • 첫 번째 원소부터 인접항 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다.
  • 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
  • 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 한다.

• 시간복잡도: O(n^2)

• [55, 7, 78, 12, 42]를 버블 정렬하는 과정(오름차순)

• 첫 번째 패스
  

• 두 번째 패스
  

• 세 번째 패스
  

• 네 번째 패스
  

• 정렬 끝
  

• 코드로 구현 (오름차순)