Giter Club home page Giter Club logo

algorithmhw's Introduction

algorithmHW

  • 2019-2 알고리즘 분석(CSI3108-01) HW 모음.

HW1

  • 문제: NxNxN개의 정육면체가 있을 때 위와 옆의 두 면으로부터 구멍을 뚫으면, 총 몇 개의 정육면체가 남게 되는지를 계산하는 자바 프로그램을 작성
  • 접근법: 구멍의 dimension에 따라 제거되는 좌표를 구함. 제거되는 좌표들을 중복 카운트하지 않기 위해 HashSet<ArrayList<Integer>>을 사용함.

HW2

  • 문제: 2차원 평면에 n개의 점들이 주어질 때, 서로 다른 3개 이상의 점들을 지나는 선분들을 찾고, 이 선분들이 서로 교차하여 만들어지는 점들의 수를 계산하는 자바 프로그램을 작성
  • 접근법
    1. 세 점으로 가능한 조합을 모두 구함.
    2. ccw(counterclockwise)를 이용해 선분이 될 수 있는지 검사.
    3. 선분 상에 있는 점 추가.
    4. 선분의 시작점과 끝 점을 구함.
    5. ccw를 이용해 교차하는 선분들을 구함.
    6. 기울기와 y절편을 이용해 교점 구함.

HW3

  • 문제: Cooley-Tukey FFT(fast fourier transform) 알고리즘 이용하여 주어지는 다항식에 대해 DFT(discrete fourier transform)를 계산하는 자바 프로그램을 작성
  • 접근법
    1. 주어진 다항식의 coefficient를 2**n만큼의 길이를 가지는 array로 만들어 줌. (없는 경우 0으로 처리)
    2. coefficient array를 even(0, 2, 4...)과 odd(1, 3, 5...)로 반씩 나눔.
    3. array의 길이가 1일 때를 base case로 만들어 재귀적으로 1 ~ 2 적용.
    4. 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 사용)
  • 접근법
    1. graph 초기화. (edge 추가)
    2. parents 초기화.
    3. edge들에 랜덤하게 weight 할당.
    4. weight 오름차순으로 edge 정렬.
    5. 서로 다른 parent를 가지는 vertex가 2개 남을 때까지 find와 union을 통해 vertex 합침. (mst 구하는 과정)
    6. 서로 다른 parent를 가지는 vertex 개수, 즉 cut을 구함.
    7. 3 ~ 6 과정을 n*(n-1)/2 반복. (해당 값은 마지막에 min cut을 찾았을 때를 가정한 확률)

HW5

  • Symmetric Traveling Salesman 문제를 해결하는 DP로 최적 싸이클을 찾는 자바 프로그램을 작성
  • 접근법
    1. distance graph 초기화.
    2. subset S를 넣었을 때 j의 min dist를 반환하는 HashMap c 정의
    3. 출발점에서 출발점으로 도착하는 거리 0으로 초기화
    4. size를 2부터 도시 개수(n)까지 증가시키면서 subset을 뽑음.
    5. 출발점으로 되돌아가는 거리는 inf로 값 설정.
    6. subset마다 모든 second last의 min dist를 구함.
    7. second last의 min dist에 second last와 last의 거리를 더해 subset에 해당하는 min dist를 구함. (DP)
    8. n까지 5~7 과정을 반복해 최적 싸이클을 찾음.

HW6

  • Linear Programming 문제를 해결하기 위한 Simplex 알고리즘을 자바 프로그램으로 구현
  • 접근법
    1. 항 개수 n, variable 개수 m을 인풋으로 받음.
    2. 계수의 값을 2차원 배열에 담음.
    3. obj value의 맨 처음 값으로 0.0 추가 (obj value는 모든 식에 0을 대입했을 때의 값)
    4. 표현식에 대한 slack form을 얻음. ex) 4x + 3y <= 2 -> a = 2 - 4x - 3y

algorithmhw's People

Contributors

zzozzolev avatar

Watchers

avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.