[알고리즘 기초] 01_배열 1 (Array 1) / Python

[알고리즘 기초] 01_배열 1 (Array 1) / Python

[알고리즘 기초] 01_배열 1 (Array 1) / Python

1. 배열

• 프로그램 내에서 여러개의 변수가 필요할때 사용.
• 하나의 선언으로 둘 이상의 변수를 선언 할 수 있다.

 

 

- 완전탐색

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

 

 

- 순열 (Permutation)

• 서로 다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것
• nPr
  • nPr = n * (n-1) * (n-2) * ... * (n-r+1)
  • nPn = n * (n-1) * ... * 2 * 1 = n! - Factorial

# {1, 2, 3}을 포함하는 모든 순열을 출력
for i1 in range(1, 4):
    for i2 in range(1, 4):
        if i2 != i1 :
            for i3 in range(1, 4):
                if i3 != i1 an i3 != i2 :
                    print(i1, i2, i3)

 

 

 

- 탐욕 (Greedy) 알고리즘

1. 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합 (solution set)에 추가한다.
2. 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지를 확인한다. 문제의 제약 조건을 위반하지 않는지를 검사한다.
3. 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지 확인한다.

완전탐색이 아닌 그리디한 방법으로 해결하면 좋음, but 완전한 해결이 아닐 수 있다.

 

 

 

 

2. 정렬

- 정렬 기준

• 오름차순(ascending) : 작은 ~ 큰
• 내림차순(descending) : 큰~작은

 

 

- 대표적 정렬 방식의 종류

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

 

 

- 버블 정렬 (Bubble Sort)

• 인접한 두 개의 원소를 비교하여 자리를 계속 교환하는 방식
• 과정
  • 첫번째 원소부터 인접한 원소끼리 자리를 계속 교환하면서 마지막 자리까지 이동한다.
  • 한단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
  • 교환하며 자리를 이동하는 모습이 거품 모양과 같다고하여 버블 정렬이라고 한다.
• 시간복잡도
  • O(n^2)

<<버블정렬 ex>>
4 3 2 1	| 3 2 1 4 | 2 1 3 4 | 1 2 3 4
3 4 2 1	| 2 3 1 4 | 1 2 3 4 |
3 2 4 1	| 2 1 3 4 |         |
3 2 1 4	|         |         |

 

 

 

- 카운팅 정렬

#  Counting 정렬

#nums = list(map(int,input()))
nums = [1, 1, 2, 3, 1, 1]
print(nums)
# [1, 1, 2, 3, 1, 1]

c = [0] * len(nums)
result = [0]*len(nums)
for n in nums:
    c[n] += 1

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

print(c)
# [0, 4, 5, 6, 6, 6]

for num in range(len(nums)-1, -1, -1):
    result[c[nums[num]]-1] = nums[num]
    c[nums[num]] -= 1

print(result)
#[1, 1, 1, 2, 3]