프로그래밍/Algorithm 105

0번부터 차례대로 번호 매겨진 n개의 원소 중 4 개를 고르는 모든 경우를 출력하라

public void selectArr(int[] arr) { for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length + 3; j++) { for (int k = j + 1; k < arr.length; k++) { for (int l = k + 1; l < arr.length; l++) { System.out.println(arr[i] + ", " + arr[j] + ", " + arr[k] + ", " + arr[l]); } } } }회고. 0번부터 차례대로 번호 매겨진 n개의 원소 중 4개를 구하는 것이라면 굳이 배열을 쓸 필요가 없었다. 그냥 public void selectArr(int n) { for (int i = ..

N개의 측정치가 주어질 때 M개의 이동 평균을 계산하라.(2)

package kwo2002.java; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * Created by kwo2002 on 2015-08-21. */ public class MAverage { public List mAvg(List nList, int m) { if (m > nList.size()) { throw new IllegalArgumentException(); } List avgList = new ArrayList(); double firstSum = 0.0d; for (int i = 0; i < m; i++) { firstSum += nList.get(i); } avgList.add(first..

N개의 측정치가 주어질 때 M개의 이동 평균을 계산하라.

package kwo2002.java; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * Created by kwo2002 on 2015-08-21. */ public class MAverage { public List mAvg(List nList, int m) { if (m > nList.size()) { throw new IllegalArgumentException(); } List avgList = new ArrayList(); for (int i = m - 1; i < nList.size(); i++) { double sum = 0.0d; for (int j = 0; j < m; j++) { sum +..

짝수개의 문자열을 두글자씩 나눈다음 정렬하라.

문제Professor Lew teaches Algorithm course in Sonyusi University (소녀시대학교). It is his first year as a professor, so he spends a lot of time making lecture notes. He'll teach recursion and sorting algorithms in the next class, and he wants to make some examples which will be included in his lecture note.While making some examples for his lecture note, he noticed that one of his work was quite diffic..

사각형 중 3 꼭지점의 좌표가 입력되었을 때, 나머지 좌표를 알아내라.

문제AdbyMe, Inc. 의 인턴인 A.I.는 웹 브라우저에 직사각형을 그리는 코드를 작성해야 한다. 웹 브라우저는 직사각형 모양의 뷰포트를 가지고 있고, 그려지는 직사각형의 네 변은 반드시 그 뷰포트의 두 축에 평행해야 한다.한편, A.I.는 코드를 작성하던 중 그릴 직사각형의 네 꼭지점 중 어느 것이든 세 개의 좌표를 알고 있다면 나머지 점의 위치는 유일하게 결정됨을 알아내었다 (네 점 중 어떤 두 개의 좌표를 알아낸 경우는 때에 따라 직사각형을 결정하지 못할 수도 있다.)A.I.는 LIBe에게 이를 이번 대회 문제로 출제할 것을 제안하였다.직사각형을 이루는 네 점 중 임의의 세 점의 좌표가 주어졌을 때, 나머지 한 개의 점의 좌표를 찾는 프로그램을 작성하라.입력입력은 T 개의 테스트 케이스로 구성..

공연장 대여 일수 별 평균 최소비용을 구하라.

커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 L개의 팀은 이미 섭외가 끝난 상태입니다. 따라서 페스티벌은 최소 L일 이상 진행하게 됩니다.이번에 사용할 공연장은 하루 빌리는 데 드는 비용이 매일 매일 다릅니다. 때문에 공연 일정을 잘 정해서 공연장 대여 비용을 줄이려고 합니다. 앞으로 N일간의 공연장 대여 비용을 알고 있다고 합시다. 이 중 L일 이상을 연속해서 대여하되, 공연장을 하루 빌리는 데 드는 평균 비용을 최소화하려면 어떻게 공연장을 빌려야 할까요?예를 들어 앞으로 6일간 공연장을 빌리는 데 드는 비용이 각 ..

M X N 행렬의 한 원소가 0이라면, 해당 원소가 속한 행과 열의 모든 원소를 0으로 바꾸는 함수를 작성하라

/** * Created by kwo2002 on 2015-08-04. */ object MatrixZero { def getZeroElemIndex(matrix: Array[Array[Int]]): Array[Array[Int]] = { def go(i: Int, j: Int): (Int, Int) = { if (i > matrix.length) { (-1, -1) } else { if (matrix(i)(j) == 0) { (i, j) } else { if (j >= matrix(i).length - 1) { go(i + 1, 0) } else { go(i, j + 1) } } } } val zeroIndex: (Int, Int) = go(0, 0) if (zeroIndex._1 >= 0) { mod..

n번째 피보나치 수를 돌려주는 재귀 함수를 작성하라

/** * Created by kwo2002 on 2015-08-04. */ object Fibonacci { def fibonacci(n: Int): Int = { def go(a: Int, b: Int): Int = { if(b >= n) { b }else { print(b + " ") go(b, a + b) } } print(0 + " ") go(0, 1) } def main(args: Array[String]) { println(fibonacci(25)) } } 회고1. n번째 피보나치 수를 돌려주는 재귀 함수 자체는 아주 쉬웠으나,피보나치 수열을 print 해주는건 의외로 약간의 고민이 필요했음. 2. 재귀 호출로 go의 b인자가 결국 피보나치 수열인건데, 첫번째 피보나치 수열 (위에서는 0) ..

같은 문자가 반복될 경우, 그 횟수를 사용해 문자열을 압축하는 메소드를 구현하라.(3)

def zipString2(str: String): String = { def go(i: Int, li: Int, cnt: Int, zipStr: StringBuilder): String = { if (i >= str.length) { zipStr.append(str.charAt(li)) zipStr.append(cnt) zipStr.toString() } else { if (str.charAt(li) == str.charAt(i)) { go(i + 1, li, cnt + 1, zipStr) } else { zipStr.append(str.charAt(li)) zipStr.append(cnt) go(i + 1, i, 1, zipStr) } } } val zipStr: String = go(1, 0, 1,..

같은 문자가 반복될 경우, 그 횟수를 사용해 문자열을 압축하는 메소드를 구현하라.(2)

import scala.StringBuilder /** * Created by kwo2002 on 2015-08-03. */ object ZipString { def zipString(str: String): String = { def go(n: Int, cnt: Int, zipString: StringBuilder): String = { if (cnt == 1) { zipString.append(str.charAt(n)) } if (n >= str.length - 1) { zipString.append(cnt) zipString.toString() } else { if (str.charAt(n) == str.charAt(n + 1)) { go(n + 1, cnt + 1, zipString) } else..