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. 방문하지 않은 노드 중에서 최단 거리..
-
[다이나믹 프로그래밍] 개념 정리Algorithm/개념정리 2021. 11. 23. 21:11
다이나믹 프로그래밍(동적 계획법)?! 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법임 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 구현은 일반적으로 2가지 방식(탑다운 & 보텀업)으로 구성됨 '동적 계획법' 이라고도 부르는데, 흔히 프로그래밍에서 다이나믹은 '프로그램이 실행되는 도중에' 라는 의미임 예를 들어, 자료구조에서 동적 할당은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법임 하지만 다이나믹 프로그래밍에서의 '다이나믹'은 동적 할당(Dynamic Allocation)에서의 다이나믹과는 다른 의미임 다이나믹 프로그래밍의 기본적인 아이디어 1줄 요약 : 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면..