알고리즘

하나의 큰 problem을 중첩되는 sub problem으로 해결하는 알고리즘 테크닉각각의 sub problem을 해결하고, 그 결과를 테이블에 기록하고, 이를 통해 원래 문제를 해결하는 식으로 진행된다ex) 1원, 3원, 5원 각각의 동전을 무한대로 사용할 수 있을

저번 포스팅과 이어진다dp(n)이 n원을 만들 수 있는 최소한의 화폐 구성에서 사용된 화폐 수라고 한다면dp(15)는 아래 경우의 수 중 최소값이다dp(12) + 1 // 12원의 최소 화폐 수 + 1. dp(12)라는 더 작은 문제의 답을 재활용dp(13) + 1 /

DFS & BFS - 그래프를 탐색하기 위한 알고리즘 DFS 깊이 우선 탐색. 스택이나 재귀를 사용해서 구현 탐색을 시작할 노드를 스택에 삽입, 방문 처리 스택에서 pop해서 노드 꺼냄 & 노드 방문 처리 pop한 노드에서 방문하지 않은 인접 노드 기타 기억할

이진탐색 개념 개념 이진 탐색: 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함 중간점 인덱스가 가리키는 값인 8보다 찾고자 하는 값인 4가 더 작으므로 중간점 이후는 탐색을 하지 않음 !

사진 참고:1번 -> 3번 경로의 최단 거리는 아래와 같은 경로로 진행될 때 음의 무한이 될 수 있음음수 간선이 있다고 무조건 음의 순환이 발생하는 건 아님을 주의다익스트라 문제와 같이 하나의 노드에서 다른 모든 노드로 가는 최단경로 문제를 풀 때 사용다만 다익스트라와

사이클이 없는 방향 그래프(DAG)로 풀이 가능위상정렬: 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것노드를 하나씩 나열하되 방향성에 거스르지 않도록 나열해야됨큐를 이용하거나 dfs를 이용해서 풀이 가능순환하지 않는(사이클이 없

특정한 노드에서 출발, 다른 모든 노드로 가는 최단 경로를 계산음의 간선이 없을 때 정상적으로 동작함방향성 있는 그래프와 없는 그래프 모두에 적합함그리디 혹은 다이나믹 프로그래밍 알고리즘으로 분류됨1\. 출발 노드를 설정2\. 최단거리 테이블을 초기화함초기화 시 자기

정의: 리스트에 순차적으로 접근해야 하 ㄹ때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘ex) 2, 3, 4, 5, 6, 7번 학생을 지목할 때\-> 시작점 2와 끝점 7이라는 2개의 점으로 접근할 데이터의 범위 표현 \-> 2번부터 7번까지 학생ex) 특정한 합