다양한 알고리즘 기법 / 단순하게 문제풀기

다양한 알고리즘 기법

• 동적 프로그래밍 (= 동적 계획법)
  • 최적화를 위한 문제해결 기법 중 하나
  • 컴퓨터에서 의미하는 프로그래밍이 아님
  • 다음 단계로 진행하기 위하여 계획한다(기억하며 풀기)
  • 주어진 문제를 해결하기 위한 과정을 여러단계로 나눈 후 하나의 단계에서 다음 단계로 진행하며 나타나는 정보를 이용해 해결함.

분할정복 알고리즘	동적 프로그래밍	그리디 알고리즘	동적 프로그래밍
분할되는 작은 문제. 서로 독립적 하위문제 해결 → 결과 통합 → 전체 해결	나누어진 문제 서로 독립적 X 분할된 하위 문제 간 중복 부분 존재 O	부분 문제별 최적해 모여 전체 해결 부분 최적해 =/= 전체 최적해	부분 문제별 최적해 → 다음 최적해 주어진 문제 최적 해  = 이전 부분 최적 해

 

• 문제해결 단계
  1. 문제를 부분 문제로 나누기
  2. 최소 단위의 문제부터 해결하여 답 구한 뒤 저장하기
  3. 저장된 부분 문제의 답 이용, 점차적으로 상위 문제의 답 구해 전체 문제 해결하기

 

• 되추적 기법
  • 문제해결과정에서 막히면 돌아가서 다시 답 찾는 기법
  • 다양한 선택 O → 하나 선택하여 문제 해결에 접근
  • 진행 불가능 → 전 단계로 되돌아가 다른 선택으로 문제 해결
  • 적절한 해결안 찾을 때까지 다양한 선택을 적용
    • 어떤 선택 해야할지 충분한 정보X
    • 각 단계마다 새로운 선택 요구
    • 한개 이상의 복수개 방식으로 문제해결 답 적용 가능

  • 

    
    
  • 예시
    • 미로 찾기
    • N-Queen (NxN체스판 N개의 여왕을 배치하는 문제)

** 서로의 위치를 방해하지 않아야하며 한 열, 줄, 대각선에 여왕이 하나씩 배치되어있어야함

 

• 분기 한정 기법
  • 최적의 해를 구하는 알고리즘 (되추적 기법과 구별)
  • 되추적을 적용하기에는 선택할 수 있는 경우의 수가 너무 많을 때 사용함
  • 선택의 단계에서 한계치를 적용해 선택할지 아닐지 결정함
  • 한계치가 지금까지의 최적결과보다 좋지 않을 경우 더 이상 분기 시도하지 않음.

통 채우기 문제
- 가장 적은 수의 통(bin)을 사용하여 정해진 용량의 통 안에 주어진 n 개의 물건을 채우는 문제 - 통의 크기를 넘는 물건은 통 안에 넘을 수 없음. (= 물건 크기 < 통 용량) 통 안에 물건이 들어갈 여유가 있어야함.
순서에 의존하여 풀기!  연습 [7, 5, 6, 4, 2, 3, 7, 5] 통 용량 10
최소적합	다음 적합	최선적합	최악적합	최소적합 감소순
처음부터 살펴보며 가장 먼저 만나는 여유가 있는 통에 넣기	직전 물건 넣은 통에 여유가 있으면 거기 넣고, 없으면 새 통에 넣기	기존 통 중 물건을 넣으면 남는 용량이 제일 적은 곳에 넣기	기존 통 중 물건을 넣으면 남는 용량이 제일 큰 곳에 넣기	정렬 후 순서대로 넣기 정렬 시 [7 7 6 5 5 4 3 2]
1) 7  → 통1 (3남음) 2) 5  →  통2 (5남음) 3) 6  →  통 3 (4남음) 4) 4  → 통2 (1남음)  5) 2  →  통1 (1남음) 6) 3  → 통2 (2남음) 7) 7  → 통4 (3남음) 8)  5  →   통5 (5남음)	1) 7  → 통1 (3남음) 2) 5  →  통2 (5남음) 3) 6  →  통 3 (4남음) 4) 4  → 통3 (0남음)  5) 2  →  통4 (6남음) 6) 3  → 통4 (3남음) 7) 7  → 통5 (3남음) 8)  5  →   통6 (2남음)	1) 7  → 통1 (3남음) 2) 5  →  통2 (5남음) 3) 6  →  통 3 (4남음) 4) 4  → 통2 (1남음)  5) 2  →  통1 (1남음) 6) 3  → 통2 (2남음) 7) 7  → 통4 (3남음) 8)  5  →   통5 (5남음)	1) 7  → 통1 (3남음) 2) 5  →  통2 (5남음) 3) 6  →  통 3 (4남음) 4) 4  → 통2 (1남음)  5) 2  →  통1 (1남음) 6) 3  → 통2 (2남음) 7) 7  → 통4 (3남음) 8)  5  →   통5 (5남음)	1) 7  → 통1 (3남음) 2) 5  →  통2 (5남음) 3) 6  →  통 3 (4남음) 4) 4  → 통2 (1남음)  5) 2  →  통1 (1남음) 6) 3  → 통2 (2남음) 7) 7  → 통4 (3남음) 8)  5  →   통5 (5남음)

 

 

단순하게 문제풀기

• 단순하게 문제풀기
  • Brute forcde (계산노가다?)
  • 특별한 전략이 있는 것X 
  • 문제해결 방법이 막막할때 주로 적용
  • 가능한 모든 경우를 시도(완전탐색) 후 다양한 답 중 가장 적절한 답 선택
  • 처리해야할 문제 구조화기 → 구조화된 자료 대상으로 모든 경우 적용 → 모든 경우를 검토한 후 해결책 선택

 

• 패턴 매칭
  • 문자열이 찾고자 하는 패턴을 포함하고 있는지 문자열의 왼쪽에서부터 한칸씩 이동하며 패턴 비교

STRING 을 찾으려면?

 

• 버블정렬
  • 앞에서부터 하나씩 값을 비교하면서 뒤로 이동하는 정렬 방식
  • 가장 큰 값을 맨 끝에 위치시키기 위해 두 인접 값을 비교해 큰 값이 뒤에 오도록 반복 교체하는 작업 수행
  • 버블 정렬 예시 ([7, 2, 3, 1, 5])
  • 단계현재 배열 상태비교 & 교환 설명

    초기	7 2 3 1 5	초기 상태
    ①	2 7 3 1 5	7 > 2 → 교환
    ②	2 3 7 1 5	7 > 3 → 교환
    ③	2 3 1 7 5	7 > 1 → 교환
    ④	2 3 1 5 7	7 > 5 → 교환 (최종 위치로 이동)
    ⑤	2 1 3 5 7	3 > 1 → 교환
    ⑥	1 2 3 5 7	2 > 1 → 교환 (정렬 완료)

// python 코드
def bubble_sort(a):
    for i in range(len(a) - 1):
        for j in range(len(a) - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

print(bubble_sort([90, 10, 20, 21]))

 

• 순차탐색
  
  • 처음부터 끝까지 하나 하나 차례대로 비교하며 찾고자 하는 값을 탐색하는 방식
  • 자료가 정렬되지 않은 상태에서 특정 자료 값을 찾는 경우 적절
  • 순차 탐색 예시 (값 46 찾기)

인덱스	0	1	2	3	4	5
값	3	5	10	12	46	53
일치 유무	X	X	X	X	O	X

 

총 비교 횟수 5회, 결과값 : index 4

// python 코드
def sequential_search(target, a):
    index = 0
    while index < len(a):
        if a[index] == target:
            return index
        index += 1
    return -1

print(sequential_search(3, [7, 6, 5, 4, 3, 2, 1]))