목록CS/알고리즘 (9)

하루살이 개발자

[알고리즘] 순열과 조합

코딩테스트에서 자주 만났던 순열과 조합에대해 정리해보려고 합니다! 순서, 중복여부에 따라서 순열, 조합, 중복순열, 중복조합으로 나뉜다. 종류 순열 중복순열 조합 중복조합 순서 다름 구분 여부 O O X X 중복 여부 X O X O {1, 2, 3}, r = 2일 경우 1 2 1 3 2 1 2 3 3 1 3 2 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 1 2 1 3 2 3 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 특징 원소저장 배열 result 필요 방문처리 배열 visited 필요 탐색 시작기준 start 필요X 원소저장 배열 result 필요 방문처리 배열 visited 필요X 탐색 시작기준 start 필요X 원소저장 배열 result 필요X 방문처리 배..
CS/알고리즘 2022. 12. 10. 21:11
[알고리즘] 최소 신장 트리(Kruskal, Prim 알고리즘)

1. 신장 트리 - 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. * 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 다는 조건은 트리의 조건이기도 한다. 2. 최소 신장 트리 - 최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 - 크루스칼/프림 알고리즘 1) 크루스칼 알고리즘 - 대표적인 최소 신장 트리 알고리즘이다. - 그리디 알고리즘으로 분류된다. [동작 과정] 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.(비용이 적은 순으로 나열) 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다. 2) 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다. ..
CS/알고리즘 2022. 2. 23. 14:05
이전 Prev 1 2 3 4 5 Next 다음