📚알고리즘

📚배열(Array1)

📗알고리즘

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

📙배열과 정렬

• 배열
  : 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조
• 배열의 필요성
  • 여러개의 변수가 필요할 때 이를 일일이 변수로 지정하여 접근하는 것은 비효율적
  • 다수의 변수로 하기 힘든 작업을 배열을 통해 쉽게 처리 가능
• 정렬
  : 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값(오름차순:ascending) 혹은 그 반대의 순서대로 (내림차순, descending) 재배열하는 것
  : 정렬에서 키란 자료를 정렬하는 기준이 되는 특정 값을 뜻한다.
• 대표적인 정렬 방식의 종류
  • 버블정렬, Bubble Sort
  • 카운팅 정렬, Counting Sort
  • 선택 정렬, Selection Sort
  • 퀵 정렬, Quick Sort
  • 삽입 정렬, Insertion Sort
  • 병합 정렬, Merge Sort

📒버블 정렬(Bubble Sort)

• 버블 정렬
  : 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
  • 정렬 과정
  1. 첫 번째 원소부터 인접한 원소끼리 계속 자리를
  2. 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
  3. 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 한다.
• 시간 복잡도 : O(N**2), 비교와 교환 방식의 알고리즘 기법이다.

arr = [55, 7, 78, 12, 42]
N = len(arr)
for i in range(N-1, 0, -1):
    for j in range(i):
        if arr[j] >= arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]

print(arr)

📘카운팅 정렬(Counting Sort)

• 카운팅 정렬
  : 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형시간에 정렬하는 효율적인 알고리즘
  • 제한 사항
    : 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능
    : 각 항목의 발생회수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문이다.
    : 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.
  • 시간 복잡도
    : O(n + k), n이 비교적 작을 때만 가능하다.
    : 비교환 방식 알고리즘 기법이다.

arr = [0,4,1,3,1,2,4,1]
arr_leng = len(arr)
maxV = max(arr)
count_arr = [0]*(maxV + 1)

for i in arr:
    count_arr[i] += 1
for i in range(1,len(count_arr)):
    count_arr[i] += count_arr[i-1]

temp_arr = [0]*(len(arr))

for i in range(len(arr)-1, -1, -1):
    count_arr[arr[i]] -= 1
    temp_arr[count_arr[arr[i]]] = arr[i]

print(temp_arr)

📕완전검색

• 완전검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다.
• Brute-force 혹은 generate-and-test기법이라고도 한다.
• 모든 경우의 수를 테스트한 후, 최종 해법을 도출한다.
• 일반적으로 경우의 수가 상대적으로 작을 때 유용한다.
• 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다.

순열(Permutation)

• 서로 다른 것들 중에서 몇 개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열 : nPr
• nPr = n (n-1) (n-2) ... (n-r+1)

def permutation(arr, r):
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generate(chosen, used):
        if len(chosen) == r:
            print(chosen)
            return

        for i in range(len(arr)):
            if not used[i]: # used[i]가 0인 경우
                chosen.append(arr[i])
                used[i] = 1
                generate(chosen, used)
                used[i] = 0
                chosen.pop()
    generate([], used)

permutation('ABCD', 2)

• 출처 : https://shoark7.github.io/programming/algorithm/Permutations-and-Combinations

조합(Combination)

• 조합은 같은 n개 중에서 r을 뽑되, 순서를 고려하지 않는다.

def combination(arr, r):
    arr = sorted(arr)

    def generate(chosen):
        if len(chosen) == r:
            print(chosen)
            return

        start = arr.index(chosen[-1]) + 1 if chosen else 0
        for nxt in range(start, len(arr)):
            chosen.append(arr[nxt])
            generate(chosen)
            chosen.pop()

    generate([])

combination('ABCD', 2)

• 출처 : https://shoark7.github.io/programming/algorithm/Permutations-and-Combinations

📔그리디 (Greedy Algorithm)

• 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법이다.
• 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
• 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장으 없다.