Algorithm_01

알고리즘

• 알고리즘 무엇인가?
  • 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다.
  • 주로 컴퓨터 용오러 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법이다.
  • 간단하게 말하면 어떠한 문제를 해결하기 위한 절차라고 볼 수 있다.
• 표현 방법
  • 의사코드(슈도코드)
  • 순서도
• 좋은 알고리즘이란?
  • 정확성 : 얼마나 정확하게 동작하는가
  • 작업량 : 얼마나 적은 연산으로 웒는 결과를 얻어내는가
  • 메모리 사용량 : 얼마나 적은 메모리를 사용하는가
  • 단순성 : 얼마나 단순한가
  • 최적성 : 더 이상 개선할 여지없이 최적화되었는가
• 시간 복잡도
  • 실제 걸리는 시간을 측정
  • 실행되는 명령문의 개수를 계산
  • 빅-오 표기법(Nig-O Notation)
  • 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시
  • 계수는 생략하여 표시

배열

• 배열이란 무엇인가?
  • 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조
  • 6개의 변수를 사용해야 하는 경우, 이를 배열로 바꾸어 사용하는 예
• 배열의 필요성
  • 프로그램 내에서 여러 개의 변수가 필요할 때, 일일이 다른 변수명을 이용하여 자료에 접근하는 것은 매우 비효율적
  • 배열을 사용하면 하나의 선언을 통해서 둘 이상의 변수를 선언할 수 있다.
  • 단순히 다수의 변수 선언을 의미하는 것이 아니라, 다수의 변수로는 하기 힘든 작업을 배열을 활용해 쉽게 할 수 있다.
• 1차원 배열의 선언
  • 별도의 선언 방법이 없으면 변수에 처음 값을 할당할 때 생성
  • 이름 : 프로그램에서 사용할 배열의 이름
• 1차원 배열의 접근
  • Arr[0] = 10
  • Arr[idx] = 20

정렬

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

• 키

  • 자료를 정렬하는 기준이 되는 특정 값

• 대표적인 정렬 방식의 종류

  • 버블 정렬
  • 카운팅 정렬
  • 선택 정렬
  • 퀵 정렬
  • 삽입 정렬
  • 병합 정렬

• 버블 정렬

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

    def BubbleSort(a, N) : # 정렬할 List, N 원소수
      for i in range(N-1,0,-1): # 범위의 끝 위치
        for j in range(0, i): # 비교할 왼쪽 원소
          if a[j] > a[j+1]:
            a[j],a[j+1] = a[j+1],a[j]

• 카운팅 정렬

  • 항목들의 순서를 경정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘

  • 제한사항

    • 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능 : 각 항목의 발생회수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문
    • 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.

  • 시간 복잡도

    • O(n + k) : n은 리스트 길이, k는 정수의 최대값

    def Counting_sort(data, temp, k)
    # data[] -- 입력 배열
    # temp[] -- 정렬된 배열
    # counts[] -- 카운트 배열
      counts = [0] * (k+1)
      for i in range(0, len(data)):
        counts[data[i]] += 1
      for i in range(1, k+1):
        counts[i] += counts[i-1]
    
      for i in range(len(temp)-1, -1, -1):
        counts[data[i]] -= 1
        temp[counts[data[i]]] = data[i]