complex array에 base case 부터 순차적으로 k, k + n/2에 각각 복소수 곱과 복소수 합 값을 넣어줌. (k와 k + n/2가 plus minus pair인 것을 이용)
HW4
n개의 점을 가지고 하나의 연결 성분(connected component)으로 된 그래프 G=(V, E)에 대해 D.Karger의 Randomized Min-Cut 알고리즘 이용하여 minimum cut을 찾는 자바 프로그램을 작성 (Union-by-Rank, Path Compression 사용)
접근법
graph 초기화. (edge 추가)
parents 초기화.
edge들에 랜덤하게 weight 할당.
weight 오름차순으로 edge 정렬.
서로 다른 parent를 가지는 vertex가 2개 남을 때까지 find와 union을 통해 vertex 합침. (mst 구하는 과정)
서로 다른 parent를 가지는 vertex 개수, 즉 cut을 구함.
3 ~ 6 과정을 n*(n-1)/2 반복. (해당 값은 마지막에 min cut을 찾았을 때를 가정한 확률)
HW5
Symmetric Traveling Salesman 문제를 해결하는 DP로 최적 싸이클을 찾는 자바 프로그램을 작성
접근법
distance graph 초기화.
subset S를 넣었을 때 j의 min dist를 반환하는 HashMap c 정의
출발점에서 출발점으로 도착하는 거리 0으로 초기화
size를 2부터 도시 개수(n)까지 증가시키면서 subset을 뽑음.
출발점으로 되돌아가는 거리는 inf로 값 설정.
subset마다 모든 second last의 min dist를 구함.
second last의 min dist에 second last와 last의 거리를 더해 subset에 해당하는 min dist를 구함. (DP)
n까지 5~7 과정을 반복해 최적 싸이클을 찾음.
HW6
Linear Programming 문제를 해결하기 위한 Simplex 알고리즘을 자바 프로그램으로 구현
접근법
항 개수 n, variable 개수 m을 인풋으로 받음.
계수의 값을 2차원 배열에 담음.
obj value의 맨 처음 값으로 0.0 추가 (obj value는 모든 식에 0을 대입했을 때의 값)
표현식에 대한 slack form을 얻음. ex) 4x + 3y <= 2 -> a = 2 - 4x - 3y