[TIL] 프로그래머스 - 타겟 넘버 (bfs/dfs) / 정렬 알고리즘 (1) - 이론

[Today I Learned]

#  프로그래머스 - 타겟 넘버

문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.각 숫자는 1 이상 50 이하인 자연수입니다.타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

@solution.py

아이디어는 제대로 떠올렸는데,  익숙하지 않은 재귀를 계속 사용하려다보니 코드가 점점 지저분해져서 결국 구글링했다.

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    def dfs(idx, result):
        if idx == n:
            if result == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
    dfs(0,0)
    return answer

 

#  정렬

- 정렬 : 데이터를 특정한 기준에 따라 순서대로 나열하는 것

 

1. 선택 정렬

- 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
- 정렬되지 않은 데이터가 1개 남았을 때는 처리할 필요 X
- 매번 탐색 범위만큼 데이터를 확인해야 (이중 반복문으로 구현)

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)): # 가장 작은 원소의 인덱스
	min_index = i 
    
    for j in range(i+1, len(array)):
    	if array[min_index] > array[j]:
        	min_index = j
    
    array[i], array[min_index] = array[min_index], array[i] # 스와프
    
print(array)

 

- 시간 복잡도 : O(N^2)

 

2. 삽입 정렬

- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
- 구현 난이도가 높은 편이지만, 일반적으로 선택 정렬에 비해 더 효율적으로 동작함

- 첫번째 데이터는 그 자체로 정렬이 되어 있다고 판단하고, 두번째 데이터가 어떤 위치로 들어갈지 판단함. (첫번째 데이터의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재)
- 그 다음 데이터부터는 정렬된 데이터들의 사이 중 어디로 들어갈지 판단

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)):
	for j in range(i, 0, -1):
		if array[j] < array[j-1]:
			array[j], array[j-1] = array[j-1], array[j]
		else:
			break

print(array)

 

- 시간복잡도 : O(N^2)
- 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작함. (이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행한다면?)

 

3. 퀵 정렬

- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
- 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
- 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot)으로 설정

- (첫번째 데이터를 피벗으로 가정) 피벗 제외, 왼쪽에서부터 피벗보다 큰 데이터를 선택하고, 오른쪽에서부터 피벗보다 작은 데이터를 선택, 두 데이터의 위치를 서로 변경

 

- 피벗보다 큰 데이터로 선택된 데이터가 피벗보다 작은 데이터로 선택된 데이터보다 오른쪽에 위치하는 경우 피벗과 작은 데이터의 위치를 서로 변경 >> 분할

 

 

- 왼쪽 /오른쪽 데이터 묶음 정렬에 대해 다시 퀵 정렬 수행. (재귀적)
- 수행할때마다 범위가 점점 좁아짐.

- 평균적으로 O(NlogN)의 시간 복잡도 (최악의 경우 O(N^2))
ex. 이미 정렬된 배열에 대해 첫 번째 원소를 피벗으로 삼고, 퀵 정렬을 수행한다면?

# 일반적인 방식

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array, start, end):
	if start >= end: # 원소가 1개인 경우 종료
    	return
        
    pivot = start
    left = start + 1
    right = end
    
    while (left<=right):
    	while(left<=end and array[left]<=array[pivot]):
        	left += 1
            
        while(right>start and array[right]>=array[pivot]):
        	right -= 1
            
        if (left > right):
        	array[right], array[pivot] = array[pivot], array[right]
        else:
        	array[left], array[right] = array[right], array[left]
            
   quick_sort(array, start, right-1)
   quick_sort(array, right+1, end)
   
quick_sort(array,0,len(array)-1)

# 파이썬의 장점을 살린 방식

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array, start, end):
	
    if len(array) <= 1:
    	return array
        
    pivot = array[0]
    tail = array[1:]
    
    left_side = [x for x in tail if x<=pivot]
    right_side = [x for x in tail if x > pivot]
    
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
    
quick_sort(array)

 

4. 계수 정렬

- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
- 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K) 보장

- 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트 생성
- 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴
- 결과적으로 최종 리스트에는 각 데이터가 몇 번씩 등장했는지 그 횟수가 기록됨 > 리스트의 첫번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스 출력

 

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7,5,9,0,3,1,7,9]

count = [0] * (max(array) + 1)

for i in ragne(len(array)):
	count[array[i]] += 1
    
for i in range(len(count)):
	for j in range(count[i]):
		print(i, end=' ')

 

- 때에 따라서 심각한 비효율성 초래. (eg. 0과 999,999 단 2개만 존재하는 경우)
- 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적

 

5. 정렬 알고리즘 비교

 

-----

내일은 어쩌다보니(?) 코딩테스트를 경험 삼아 한번 쳐보기로 했다.
보다시피,,, 아마 그냥 구경만 하다 올듯,,ㅎㅎ