알고리즘

그래프

그래프의 시작점에서 다른 지점까지의 최단 거리최단 거리를 구하는 알고리즘은 매우 다양함그 중 2개만 집중적으로 공부!BFS 최단 거리는 그래프 탐색에서 자세히input그래프 (v, e)간선 가중치 ≥ 0시작점 s시작점이 여러 개 있는 multi-source Dijkst

확인해야 하는 모든 경우를 전부 탐색함수 정의가 중요함백트래킹을 사용해야 하는 경우도 있음백트래킹 : 답을 찾는 도중 그 경로가 닶이 될 수 없는 경우 뒤로 되돌아 가는 방식경우의 수 4가지 case 1 : 중복 O, 나열 O (순서 O)case 2 : 중복 X, 나

문제의 크기를 변화해가면서 작은 문제의 결과를 이용해 큰 문제를 빠르게 계산하는 알고리즘먼저 완전 탐색(brute force)를 시도해 본 후 탐색되는 경우가 매우 많아 시간초과가 날 경우 DP를 시도해 볼 수 있음규격화된 방법을 외워서 연습할 것구현 코드 자체는 매우

데이터의 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법배열 내부의 데이터가 정렬된 상태여야 함변수 3개 사용startmidend동작 과정배열의 시작 인덱스를 start, 마지막 인덱스를 end로 설정mid = (start + end) / 2로 설정실수인 경우 내림

정답을 찾기 위해 꼭 봐야하는 부분만 본다.키워드“연속 부분 수열”“순서를 차례대로 지키면서”“곱의 최소”A x BA가 커지면 B가 작아짐포인터 2개에 의미를 부여해서 탐색 범위를 좁혀야 함변수를 포인터로 사용함1차원 배열에서 2개의 포인터를 만들 경우2개의 포인터 모

부모-자식 관계를 가지는 특수한 형태의 그래프모두가 연결되어 있는 그래프어떤 두 점을 골라도 간선을 타고 이동 가능문제에서 keyword가 되는 조건 ex) 모든 두 정점 사이에 이들을 잇는 경로가 존재하며… 사이클이 존재하지 않음대놓고 키워드로 줌정점 = 간선 +

동작 과정가장 작은 데이터를 맨 앞에 있는 데이터와 바꿈1번 반복시간 복잡도 : O(N^2)비효율적인 정렬 방식동작 과정리스트 내에서 (왼쪽에) 정렬된 데이터가 있음리스트의 (오른쪽에) 정렬되지 않은 데이터 중 특정 데이터 하나를 지정특정 데이터를 왼쪽에 정렬된 리스트

Directed간선의 방향이 존재함Acycliccycle이 없음Graph정점(Vertex) + 간선(Edge)inDegree & outDegree들어오는 선의 갯수 & 나가는 선의 갯수DAG를 위상에 맞춰 정렬하는 것위상에 맞춰 정렬한다는 의미올 수 있는 순서에 맞춰