이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 문제들로 나누어 해결한 뒤, 그 결과 값을 저장해두었다가 다시 사용하는 알고리즘 기법이다. 일반적인 재귀 방식은 같은 계산을 다시 반복해야 할 때가 많아 ...

이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 유니온 파인드는 이름 그대로 합치기와 찾기라는 두 가지 연산으로 여러 개의 요소들 사이의 관계를 효율적으로 관리하는 자료구조이다. 흔히 서로소 집합 알고리즘이라고도 불린다. 분리 집합 (Disjoint Set) aka 서로소...

이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 배낭 문제는 조합 최적화의 고전적인 문제로, 한정된 용량의 배낭에 최대의 가치를 갖도록 문제를 담는 방법을 찾는 문제이다. 가령, 도둑이 보석 가게에 침입했는데 보석마다 무게와 가치가 다르고, 배낭의 무게 제한이 10KG라면 어떤...

이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 두 포인터는 리스트에서 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다. 배열의 부분 배열 중 그 원소들의 합을 구해야 하거나, 배열의 원소들 중에 몇 개의 합이 특정 수가 되는 가짓수를 구할 때 유용하다. 과정 ...

이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 벨만 포드 알고리즘은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. (One To All) 다익스트라 알고리즘과 비슷하지만, 가장 큰 차이점은 가중치가 음수인 간선이 있어도 사용할 수 있다는 점이다...

본 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있다면 언제든지 피드백을 주시면 감사하겠습니다. 참고로만 활용해주시길 바랍니다. 개요 위상 정렬은 방향 그래프의 모든 노드를 주어진 방향성에 어긋나지 않게 순서대로 나열하는 알고리즘이다. 선수 과목이 있는 커리큘럼이나 조립 순서가 정해진 프라모델을 떠올리면 이해하기 쉽다. 특정 ...

본 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있다면 언제든지 피드백을 주시면 감사하겠습니다. 참고로만 활용해주시길 바랍니다. 개요 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 어떤 경로도 음수 가중치를 갖지 않는 그래프에서 사용 가능 유향/무향 상관이 없다. 다익스트라...

이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 부분 수열이라고 한다. 그리고 그 부분 수열 중에서 요소들이 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라고 한다. 크게 두 가지 $O...

이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 스위핑(Sweeping)은 ‘쓸다’, ‘훑어보다’라는 의미 그대로, 공간이나 직선 상에서 한쪽 끝부터 다른 쪽 끝까지 가상의 선을 이동시키면서 문제를 해결해 나가는 방식이다 가상의 선이 이동하면서 특정 요소와 마주칠 때마다 그...

이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 이분 그래프는 그래프의 모든 정점을 서로 겹치지 않는 두 개의 집합 A와 B로 분할했을 때, 그래프의 모든 간선이 반드시 집합 A의 정점과 집합 B의 정점을 연결하도록 분할할 수 있는 그래프를 말한다. 쉽게 말해, 정점을 두...