profile
1일1커밋

SubsetSum (부분집합의 합)

SubsetSum K개의 원소중에서 몇개의 원소를 선택해 부분집합을만들고 그 부분집합의 합 N을 구해보자. 1. 비트연산자를 이용한 부분집합의 합 배열버전 결과화면 image.png ArrayList버전 결과화면 image.png 2. 사용한 원소를 체크하면서 (boolean배열 사용) 합이 N 이 될때 출력. (순열 만들기 응용) 결과화면 ![...

2019년 10월 19일
·
0개의 댓글

순열과 조합

Permutation & Combination 순열이란 >서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 순열이라고 한다. 조합이란 >조합은 집합에서 일부 원소를 취해 부분집합을 만드는 방법을 말한다. 코드 1. swap과정을 통한 순열만들기 2. used[] 배열을 이용하여 (사용한 카드는 체킹) 이용하여 순열만들기...

2019년 10월 19일
·
0개의 댓글

Graph - 최소신장트리 MST(Prim알고리즘)

Prim 알고리즘 > 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법 과정 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식 임의정점을 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중의 최소비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때까지 1,2 과정을 반복 코드 구현

2019년 10월 13일
·
0개의 댓글

Graph - 최소신장트리 MST(Kruskal알고리즘)

Kruskal 알고리즘 (Union- find를 이용한 mst) > 탐욕적인 방법(greedy)를 이용하여 네트워크의 모든 정점을 최소비용으로 연결하는 최적해답을 구하는 알고리즘. 과정 간선을 하나씩 선택해서 MST를 찾는 알고리즘 최초, 모든 간선을 가중치에따라 오름차순으로 정렬한다. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다. ...

2019년 10월 13일
·
0개의 댓글