본문 바로가기

Tech-Algorithm3

동적프로그래밍 - 배낭 채우기 문제(Knapsack Problem) * 아래 예제는 "그림으로 개념을 이해하는 알고리즘-한빛미디어"를 참고했습니다. 알고리즘문제 중 자주보게되는 배낭 채우기 문제 (Knapsack Problem)입니다. 여러가지 해법이 있지만 여기서는 동적프로그래밍을 통한 해법을 알아봅니다. 4파운드의 가방을 갖고있는 도둑이 있습니다. 이 도둑은 모두 합쳐 4파운드의 물건만을 훔쳐 가지고 갈수 있습니다. 훔칠수 있는 물건이 아래 3개가 있다면 어떤 물건을 가방에 넣어야 최대로 많은 가치를 얻을 수 있을까요? - 스테레오 : 3000달러 , 4파운드 - 노트북 : 2000달러 , 3파운드 - 기타 : 1500달러, 1파운드 물건이 3가지 밖에 없으므로 물건의 조합 (2^3 = 8)으로 최적해를 찾을 수 있습니다. 스테레오-노트북 : 무게초과 스테레오-기타 .. 2022. 6. 14.
Matrix Rotate 정사각형의 matrix를 시계방향, 시계반대방향으로 회전시키기. 입력 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16============시계방향 13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4============반시계방향 4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13 public class ArrayRotate {public static void main(String[] args) {int arr[][] = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};int result[][] = new int[arr.length][arr[0].length];System.out.println("입력");pri.. 2018. 7. 12.
Spiral Matrix 자주 접하는 문제임에도 익숙해지지 않는 Spiral Matrix. n by n 배열에 우->하->좌->상으로 돌리면서 숫자를 배열하는 방식이다. 0 1 2 3 4 5 19 20 21 22 23 6 18 31 32 33 24 7 17 30 35 34 25 8 16 29 28 27 26 9 15 14 13 12 11 10 깔끔한 알고리즘이 많이 있지만 한방향에만 특화되어있고, 좌, 우 방향 모두 써먹을 수 있는건 단순한 알고리즘이 최고인듯하다. public class SpiralArray {public static void main(String[] args) {int iArraySize = 6;int[][] arrResult = makeSpiralArray(iArraySize);for(int i=0 ; i<.. 2018. 7. 12.

티스토리툴바