알고리즘 유형과 예제 [ w. 알고리즘 스터디 시작 ]

스터디

• 스터디 목표
  • 알고리즘, 자료구조 학습을 통한 생각의 확장성
  • 주 정해진 백준 문제 풀이 및 블로그 글 작성
• 스터디 구성원
  • 총원: 2명

 

 

알고리즘 유형

브루트 포스 (Brute Force)

모든 경우의 수를 탐색하여 결과를 찾는 방법.

전체 탐색을 하며, 원하는 답을 찾아나가는 방식인데 예제가 더 이해하기 쉬울 수 있을 것 같다.

# 탐색 리스트에서 3을 찾고 싶음
arr = [1, 2, 3, 4]

# 정답에 대한 선언( 예시 )
answer = 2

# 브루트 포스
for num in arr:
    if num == answer:
        print("Answer is"+answer)
        break

 

 

DFS (Depth First Search)

트리나 그래프를 탐색하는 방법.

깊이를 우선으로 하며 부모 노드로 부터 자식을 방문하여 탐색하여 정답을 찾는 방법.

# 트리 예시
nodeList = {
    "a": ["b", "c"],
    "b": ["c", "e"],
    "c": ["f", "d"],
    "d": [],
}

# 탐색한 리스트
visitedList = []

# DFS 
def findDfs(root_node):

    # 방문한 노드 리스트에 추가
    visitedList.append(root_node)

    # 순회하며 방문
    for word in nodeList[root_node]:
        if word not in visitedList:
        	# 없을시 재귀
            findDfs(word)
            

# 시작 노드 A부터 탐색 시작
findDfs("a")

print(visitedList)
# 출력값 ["a","b","c","f","d"]

 

BFS (Breadth First Search)

트리나 그래프를 탐색하는 방법

너비를 우선으로 하며 부모 노드로부터 자식 노드들을 동시에 방문하는 방식으로 탐색하는 것이다.

탐색할 항목이 큐에 쌓이기에, 모든 노드를 탐색이 가능하다.

# BFS로 트리 탐색하기

# 트리 예시
tree = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["G"],
    "F": [],
    "G": [],
}

# 방문한 노드 리스트
visitedList = []

# 큐
queue = []

# BFS 
def findBfs(root_node):
    # 큐에 노드 삽입
    queue.append(root_node)

    # 큐가 빌 때까지 반복
		# 두번째 방문시, 큐:"B","C" 이다. 
		# B 처리 이후, 큐: "C","D","E" 이다. 
		# C 처리 이후, 큐:: "D","E", "F" 이다.
		# D 에서는 node가 없어 큐에 추가 되지 않으며, E 방문 이후 "G"가 추가 된다.
		# "G" 에서는 자식노드가 없어서 종료.
    while queue:
        # 큐에서 노드 추출
				# 방문리스트에 추가
        node = queue.pop(0)
        visitedList.append(node)

        # 순회하며 큐에 삽입
        for next_node in tree[node]:
            if next_node not in visitedList:
                queue.append(next_node)

# 시작 노드 A부터 탐색 시작
findBfs("A")

# 방문한 노드 리스트 확인
print(visitedList) # ["A", "B", "C", "D", "E", "F", "G"]

 

DP (Dynamic Programming)

복잡한 문제를 간단한 문제로 나누어 해결하는 방법.

1. 부분 문제들을 해결

2. 전체 문제를 해결 

3. 가장 최적의 해를 찾기

 

예를 들어, 주어진 숫자 배열에서 연속된 숫자들의 최대 합을 구하는 문제에 대한 코드

# DP로 최대 합 구하기

# 숫자 배열
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

# 연속된 숫자들의 최대 합
max_sum = 0

# 배열의 각 원소를 하나하나 확인하며 실제로 구현해 최대 합 구하기
for i in range(len(arr)):
    max_sum = max(max_sum + arr[i], arr[i])

# 최대 합 확인
print(max_sum) # 6

#arr[i] | max_sum + arr[i] | max(max_sum + arr[i], arr[i]) | max_sum
#-2    | 0 + (-2)        | max(0 + (-2), -2)               | -2
#1     | -2 + 1          | max(-2 + 1, 1)                  | 1
#-3    | 1 + (-3)        | max(1 + (-3), -3)               | 1
#4     | 1 + 4           | max(1 + 4, 4)                   | 5
#-1    | 5 + (-1)        | max(5 + (-1), -1)               | 4
#2     | 4 + 2           | max(4 + 2, 2)                   | 6
#1     | 6 + 1           | max(6 + 1, 1)                   | 6
#-5    | 6 + (-5)        | max(6 + (-5), -5)               | 1
#4     | 1 + 4           | max(1 + 4, 4)                   | 5

 

그리디 (Greedy)

최적해를 구하기 위해 여러 단계로 나뉘어진 문제를 해결하는 방법.

단계마다 매번 "최적의 결정"을 하는 것이 최종적인 최적해를 찾을 때의 베스트 방법이 된다.

 

예시: 거스름돈을 줄 때 가장 적은 동전을 지급하는 코드

# 사용 가능한 동전의 종류
# 동전을 큰 것 부터 거슬러 주기 위한 sorting
# 사용한 동전의 최소 개수
# 만들어야 하는 금액
coins = [500,100,50,10]
coins.sort(reverse=True)

min_count = 0
amount = 1350

for coin in coins:
	temp = amount//coin
	count += temp 
	amount %= coin

print(count)