알고리즘별 용도 및 목표

문제 풀면서 ' 이 알고리즘은 이런 용도로 사용되는구나 ' 습득한 내용들을 정리해보자

 

📌BFS : 가중치가 1일 때 최단 경로를 찾을 때 사용한다.

visited 필요
종료 조건 설정
queue 사용

 

📌DFS : 백트래킹 혹은 존재 여부 판단에 사용된다.

존재 여부라고 했을 때는 주로 '조합 찾기' 로 사용된다.

=종료 조건=

for 모든 i에 대해
> 넣고
> Search
> 뺀다 (그러고 다음 i로 넘어감)

 

📌플로이드 - 워셜 : 모든 노드에 대해서 관계를 파악

각 노드와의 관계를 파악하는 것에 사용한다.

for k in range(1, n+1) :
    for i in range(1, n+1) :
        for j in range(1, n+1) :
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
            > '그냥 나한테 직진으로 가는 거 vs k 거쳐서 가는 거'

 

같은 수업 들으시는 코딩짱짱맨의 발표 자료

---

 

📌DP : 이전에 계산했던 값을 기반으로 현재 값을 계산하는 방식

기저 설정
점화식 세우기 
ex) min(이전 DP값 + 추가 가중치 , 그냥 현재 값)

 

📌그리디 :  Optimal SubProblem으로 나누어 최적의 해를 구하는 것

1. Subproblem으로 나누기 좋게 정리
2. 조건에 맞게 최적의 해 구하기

 

 

📌이분 탐색 : 값이 정렬되어 있는 상태, 전체 범위에서 절반씩 줄여가며 원하는 값을 탐색한다. 

정렬
중간값 설정
> 원하는 값 vs 중간 값
  원하는 값이 더 크다면 왼쪽은 버리고 오른쪽 구간에서 절반 나눠서 다시 탐색
  그렇지 않다면 왼쪽 구간에서 절반 나눠서 탐색
  
  [ 언제까지 ? ]
  오른쪽 값이 왼쪽보다 클 때 or 중간 값 == 원하는 값

 

📌문자열 관련 문제 : 문자를 찾거나 없애거나 하는 게 많음

스택이나 List 자료구조를 많이 쓴다.

담고 / 특정 크기만큼 검사하고

 

---

 

 

 

 

현재 목표는 4다

3정도는 온 듯