개발야옹

🌼 Binary Search (이분 탐색)

🌼 이진 탐색 알고리즘

• 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
• 이진 탐색: 정렬되어 있는 리스트에 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
  • 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다.

🌼 이진 탐색 동작 예시

• [Step 1] 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거)

• [Step 2] 시작점: 0, 끝점: 3, 중간점: 1 (소수점 이하 제거)

• [Step 3] 시작점: 2, 끝점: 3, 중간점: 2 (소수점 이하 제거)

🌼 이진 탐색의 시간 복잡도

• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2N에 비례합니다.
• 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개 가량의 데이터만 남습니다./
  • 2단계를 거치면 8개가량의 데이터만 남습니다.
  • 3단계를 거치면 4개가량의 데이터만 남습니다.
• 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장합니다.

✅ 재귀로 구현

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2

    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid + 1, end)

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

array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

✅ 반복문으로 구현

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

array = list(map(int, input().split()))

start = 0
end = n-1

result = None
while start <= end:
    mid = (start + end) // 2
    if array[mid] < target:
        start = mid + 1
    elif array[mid] > target:
        end = mid - 1
    else:
        result = mid
        break
print(None if result == None else result + 1)

🌼 Floyd-Warshall Algorithm (플로이드 워셜 알고리즘)

🌼 플로이드 워셜 알고리즘

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산
• 플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다.
  • 다만, 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이 필요하지 않다플로이드 워셜은 2차원 테이블에 최단거리 정보를 계산한다.
• 플로이드 워셜은 2차원 테이블에 최단거리 정보를 계산한다.
• 플로이드 워셜 알고리즘은 DP 유형에 속한다.
• 각 단계마다 특정한 노드 K를 거쳐가는 경로를 확인한다.
  • a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 좋은지 검사
• 점화식
  • Dab = min(Dab, Dak + Dkb)

🌼 플로이드 워셜 알고리즘: 동작과정 살펴보기

• [초기상태] 그래프를 준비하고, 최단거리 테이블 초기화

• [Step1] 1번 노드를 거쳐가는 경우를 고려하여 테이블을 갱신

위 단계를 반복

🌼 플로이드 워셜 알고리즘 구현 코드

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())

# 2차원 리스트(그래프 표현)를 만들고, 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            graph[i][j] = 0

# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
    # A에서 B로 가는 비용은 C라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        # 도달할 수 없는 경우, 무한이라고 출력
        if graph[a][b] == INF:
            print('INFINITY', end=' ')
        else:
            print(graph[a][b], end=' ')
    print()

🌼 DFS(Depth-First-Search) Algorithm

• DFS는 깊이 우선 탐색이라고도 부르며, 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
• DFS는 Stack 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.
  1. 탐색 시작노드를 스택에 넣고, 방문처리한다.
  2. 스택의 최상단 노드와 인접한 노드 중 방문하지 않은 노드가 있다면, 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없다면 스택 최상단 노드를 pop한다.
  3. 2번의 과정을 수행할 수 없을때까지(stack이 empty할때까지) 반복한다.

🌼 재귀함수로 DFS 구현

# DFS 메서드 정의
def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

# 각 노드가 연결된 정보를 표현(2차원 배열)
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7], 
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

# 실행 결과
# 1 2 7 6 8 3 4 5

🌼 재귀함수로 DFS 구현

# DFS 메서드 정의
def dfs(graph, v):
    visited = [False] * len(graph)
    stack = []
    stack.append(v)

    while stack:
        v = stack.pop()

        if not visited[v]:
            print(v, end=' ')
            visited[v] = True

        for w in sorted(graph[v], reverse=True):
            if not visited[w]:
                stack.append(w)

# 각 노드가 연결된 정보를 표현(2차원 배열)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 정의된 DFS 함수 호출
dfs(graph, 1)

# 실행 결과
# 1 2 7 6 8 3 4 5

Greedy Algorithm (탐욕 알고리즘)

• 선택의 순간마다 가장 최적을 선택하여 결과를 도출하는 알고리즘이다.
• 여러 경우 중 하나를 결정해야 하는 경우 그때 가장 최적의 경우를 선택해 나가는 방식이다.

Greedy Algorithm 해결 과정

1. Selection Procedure (선택 절차) : 현재 상태에서의 최적의 해답 선택
2. Feasibility Check (적절성 검사) : 선택된 해가 문제의 조건을 만족하는지 검사
3. Solution Check (해답 검사) : 최종 해답이 원래 문제를 해결하는지 검사, 만족하지 않는다면 Selection Procedure부터 위 절차들을 다시 반복

Greedy Algorithm 적용 조건 2가지

1. 탐욕스런 선택 조건(Greedy choice property): 앞의 선택이 이후의 선택에 영향을 주지 않아야 한다.
2. 최적부분구조조건(Optimal suvstructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

프로그래머스 Greedy Alogrithm 문제 풀어보기

체육복 - lv1

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

입출력 예

function solution(n, lost, reserve) {
    var answer = 0;
    
    ////////// 여벌 체육복도 있으면서 도둑도 맞은 사람 lost와 reserve 배열에서 삭제
    lost = lost.map((l) => {
       if(reserve.includes(l)) {
           reserve = new Set(reserve);
           reserve.delete(l);
           reserve = Array.from(reserve);
       } else return l;
    });
    //////////
    
    // borrow array -> 1: 체육복 빌려줄 수 있는 사람, 0: 체육복 못 빌려주는 사람
    let borrow = new Array(n).fill().map(n => 0);
    borrow = borrow.map((n, index) => {
        if(reserve.includes(index+1)) {
            return 1;
        } else return 0;
    });
    
    // student array -> 1: 체육복 있는 학생 ,0: 체육복 없는 학생
    let student = new Array(n).fill().map(n => true);
    student = student.map((n, index) => {
        if(lost.includes(index+1)) {
            return false;
        } else return true;
    });
    
    // 특정학생 기준 양옆 체육복 빌릴수 있는지 확인하고 빌려줄수있는 학생이 있다면 빌린다.
    student.forEach((s, index) => {
        if(!s) { // 체육복 없는 학생
            let left = index -1 < 0 ? null : index -1;
            let right = index +1 >= student.length ? null : index +1;
            
            if(left !== null && borrow[left] === 1) {
                student[index] = true;
                borrow[left] = 0;
            } else if(borrow[right] !== null && borrow[right] === 1) {
                student[index] = true;
                borrow[right] = 0;            
            }
        }
    })

    return student.filter(s => s === true).length;
}

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=javascript