인아웃

DFS(Depth-First Search)

깊이를 우선하여 탐색하는 방법으로 하나의 경로를 끝까지 탐색한 후, 돌아와서 다른 경로를 탐색한다.

스택(Stack)이나 재귀 함수를 사용하여 구현할 수 있다.

장점

1. 구현이 비교적 간단하다 (스택, 재귀 함수를 사용하여 구현)
2. 메모리 사용량이 적다. DFS는 스택을 사용하여 탐색 경로를 저장하므로, 메모리 적은 편이다. (탐색 경로에 대한 정보만 필요)
3. 최단 경로를 찾을 때 유용하다. 탐색 중에 목표 지점에 도달하면 탐색을 종료할 수 있기 때문

단점

1. 무한 루프의 위험성 :  그래프에 순환 경로가 있는 경우, DFS는 순환 경로를 계속해서 탐색하여 무한 루프에 빠질 수 있다.
2. 최단 경로가 아닐 수 있다 : DFS는 깊이 우선으로 탐색하므로, 첫 번째로 발견한 해답이 최단 경로가 아닐 수도 있다.
3. 탐색 시간이 길 수 있다 : 그래프가 깊거나 가지가 많은 경우, DFS는 탐색 시간이 길어질 수 있다.

BFS(Breadth-First Search)

너비를 우선하여 탐색하는 방법으로 한 단계씩 진행하면서 해당 단계의 모든 노드를 탐색한다.

큐(Queue)를 사용하여 구현할 수 있다.

장점

1. 최단 경로를 찾을 수 있다 : 너비를 우선으로 탐색하므로, 시작점에서 가까운 노드부터 탐색하여 최단 경로를 찾을 수 있다.
2. 구현이 비교적 간단하다. (큐(Queue)를 사용하여 구현)
3. 한 단계씩 진행하면서 모든 이웃 노드를 탐색한 후에야 다음 단계로 진행한다. 단계별 정보를 활용하여 문제를 해결할 수 있다.

단점

1. 메모리 사용량이 크게 증가할 수 있다 : BFS는 모든 이웃 노드를 큐에 저장해야 하므로, 탐색하는 그래프의 크기가 커질수록 큐의 크기도 커지고 메모리 사용량이 증가할 수 있다.
2. 그래프가 깊거나 가지가 많은 경우 계산 시간이 길어질 수 있다.
3. 그래프의 순환 구조에서 무한 루프에 빠질 수 있다.

이분 탐색(Binary Search)

:정렬된 배열에서 특정한 값을 효율적으로 찾는 탐색 알고리즘

정렬된 배열에서 중간 값을 선택하여 비교하고 중간 값 보다 작은 경우 왼쪽 부분 배열 대상으로 탐색, 큰 경우 오른쪽 부분 배열 대상으로 탐색하는 과정을 반복하여 특정 값을 찾도록 동작한다.

장점

1. 빠른 탐색 속도: 이분 탐색은 탐색 범위를 반으로 나누면서 탐색을 수행하기 때문에, 평균적으로 O(log n)의 시간 복잡도를 가짐
2. 간결하고 이해하기 쉬운 구현: 이분 탐색은 반복문 또는 재귀 함수를 사용하여 구현할 수 있으며, 구현이 간결하고 직관적

단점

1. 정렬된 배열에서만 가능 : 탐색을 수행하기 전에 배열의 정렬을 확인하고 정렬 후 이분 탐색 사용이 가능
2. 추가 메모리 공간 사용 :  탐색 범위를 축소하는 과정에서 추가 메모리 공간을 사용
3. 원하는 값을 찾을 수 없는 경우 발생 : 배열에서 원하는 값을 찾을 수 없는 경우에 대한 고려 필요

활용

1.  배열에서 특정 값을 찾는 경우
2.  특정 값의 인덱스를 찾는 경우
3.  최대.최소 값을 찾는 경우
4.  특정 조건에 해당하는 값을 찾는 경우

시간복잡도

: O(log n)

<이분탐색 Python 코드 예시>

def binary_search(start,end,target,array):
    while start <= end:

        mid = (start+end) //2

        if array[mid] == target:
            return mid
        
        elif array[mid] > target:
            end = mid-1
        elif array[mid] < target:
            start = mid+1

그리디 알고리즘은 단순하지만 강력한 알고리즘이라고 할 수 있다.

어떤 문제가 주어졌을 때 현재 상황에서 가장 좋은 방식을 선택하는 알고리즘으로 단순 무식하다고 볼 수 있다.

그리디 알고리즘에 해당하는 문제 풀이시 현재 상황에서 최선의 선택을 하는 것의 정당성을 파악하는 것이 중요하다!

대표적인 예시로는 거스름돈 문제를 생각 해 볼 수 있다.

x만큼의 거스름돈을 돌려줘야하는 상황에 500원,100원,50원,10원 짜리의 동전 사용이 가능한 경우 그리디 알고리즘에서는 가장 큰 화폐 단위부터 돈을 거슬러 준다면 동전 개수를 최소화 하여 거슬러 줄 수 있게 되는 것이다.

[백준 그리디 알고리즘 예시 문제]

https://www.acmicpc.net/problem/11047

문제의 표현이 조금 달라 졌을 뿐 본질적인 문제는 위의 거스름돈 문제와 동일하다.

n,k= map(int,input().split())

coin = []   #화폐 단위를 입력받을 리스트
for i in range(n):
    n = int(input())
    coin.append(n)

coin.reverse()  #큰 단위 부터 체크하기 위해 내림차순으로 변경
cnt = 0     #필요한 동전 개수

for i in range(len(coin)):
    if k >=coin[i]:
        cnt += k //coin[i]
        k = k%coin[i]

print(cnt)