알고리즘

최근 유니온 파인드 알고리즘을 푸는데 개념은 이해했고 알고 있지만 백준 문제에 적용해서 풀려고 하니 어려워 제대로 아는 것이 아니다라고 생각해서 이렇게 정리하려고 한다.유니온-파인드는 그래프에서 두 노드가 같은 집합에 속하는지 판별하는 알고리즘이다.

유니온-파인드를 공부하면서 문제를 풀다 최소 신장 트리로 푸는 문제가 나와 정리해보았다.최소 신장 트리를 알기 전에 신장 트리가 무엇인지 알아야 한다.

문자열 뒤집기 시간복잡도 분석

조합과 순열을 공부하면서 항상 재귀를 통해 조합 또는 순열을 구했는데 다른 방법이 있었다.Next Permutation이 바로 그것이다. 말 그대로 다음 순열을 찾는 방법이다.위와 같은 4가지 단계를 거친다.오름차순으로 정렬된 배열이 있을 때 맨 뒤에서 탐색하며, 교환