Algorithm
-
[구현] 개념정리Algorithm/개념정리 2022. 2. 11. 16:31
✔️ 구현(Implementation) 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다. # 동, 북, 서, 남 dx = [0, -1, 0, 1] # 행 (direction x) dy = [1, 0, -1, 0] # 열 (direction y) # 현재 위치 x , y = 2, 2 for i in range(4): # 다음 위치 nx = x + dx[i] ny = y + dy[i] print(nx, ny) → 시뮬레이션, 구현, 완전 탐색 유형은 서로 유사한 점이 많다
-
[그리디] 개념 정리Algorithm/개념정리 2022. 2. 7. 19:17
그리디 알고리즘(탐욕법)은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미함 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함 그리디 해법은 정당성 분석이 중요함 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검함 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨
-
[최단 경로] 개념 정리Algorithm/개념정리 2022. 1. 11. 02:06
최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미함 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 1. 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산함 음의 간선이 없을 때 정상적으로 동작함 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음 그리디 알고리즘으로 분류됨 매 상황에서 가장 비용이 최소인 노드를 선택해 임의의 과정을 반복함 # 동작 과정 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중에서 최단 거리..