배열 3
아래 모든 문제에 적용되는 지시 사항
- 클래스 선언문 바로 위에 그 클래스에 대한 설명을 주석으로 넣으시오.
- main 함수 외의 함수에도 주석을 넣으시오.
- 주석의 첫 부분은 /** 로 시작하고 끝 부분은 */로 마칩니다.
- 주석을 적어 넣지 않거나 들여쓰기를 하지 않으면 감점합니다.
P1 (메소드 오버로딩(overloading), 다중정의)
SwapComparison이라는 이름의 클래스를 작성하시오.
우선 아래와 같은 두 개의 swap 메소드를 입력하시오. swap 메소드는 주어진 두 개의 값을 서로 바꾸어줍니다.
이 두 메소드들은 이름이 같고 파라미터 리스트가 서로 다르므로 오버로딩(overloading, 다중정의)된 것입니다.
코드
아래와 같은 main 메소드를 작성하고 실행하면 33번 줄과 35번 줄 각각에 의해 두 개의 swap 메소드들 중 어느 것이 실행될지 생각해 보시오.
또 프로그램의 출력이 어떻게 될지 생각해 보시오.
33번 줄과 35번 줄의 작동에 대한 설명을 33번 줄 바로 위와 35번 줄 바로 위에 주석 형태로 적어 넣으시오.
[힌트]
P2
주사위를 한 개 혹은 여러 개 던져 나온 수를 관찰하는 일을 여러 번 반복할 때 그 수의 분포가 어떻게 되는지 알아보는 프로그램을 작성합니다. 클래스 이름은 Dice로 지으시오.
프로그램을 실행한 예는 아래와 같습니다.
아래는 주사위 한 개를 1,000번 던졌을 때 관찰된 분포입니다.
(NUM_DICE = 1, TRIALS = 1000일 때)
아래는 주사위 두 개를 던져 나온 수의 합이 얼마인지 10,000번 관찰한 결과입니다.
(NUM_DICE = 2, TRIALS = 10,000일 때)
아래는 주사위 5개를 던져 나온 수의 합이 얼마인지 10,000번 관찰한 결과입니다.
(NUM_DICE = 5, TRIALS = 10,000일 때)
우선 여러 개의 주사위를 던져 나온 수의 합을 int 타입으로 반환하는 static 메소드를 작성하시오. 주사위는 1부터 6까지가 가능한 정육면체입니다. 이 메소드를 호출할 때는 주사위 몇 개를 던질지 호출하는 자가 지정하게 하시오. 메소드 이름은 castDice로 지으시오.
main 메소드를 아래 설명에 맞춰 작성하시오.
아래와 같이 조건을 변경하고 프로그램을 실행해 보시오.
TRIALS=10,000
NUM_DICE = 2
P3
위 P2 프로그램을 개선하여 주사위 던지기 모의실험(simulation)결과를 그래프로 보여주도록 합니다. 클래스 이름은 DiceGraph로 지으시오.
프로그램을 실행한 예는 아래와 같습니다.
(NUM_DICE = 1, TRIALS = 20일 때)
(NUM_DICE = 2, TRIALS = 30일 때)
(NUM_DICE = 2, TRIALS = 300일 때)
별 문자로 그래프를 그리는 메소드를 먼저 작성하고 main에서 이 메소드를 이용하도록 하시오. 그래프를 그리는 메소드 이름은 graph로 지으시오. 이 메소드는 (1) 그래프를 그릴 배열과 (2) 그 배열의 몇 번 방부터 그릴 것인지 등 두 개의 파라미터를 갖도록 하시오. 주사위를 던지는 작업을 모의실험하기 위해서는 Dice.castDice 메소드를 이용하시오.
P4
위 P3 프로그램을 개선하는 문제입니다.
DiceGraph는 각 수가 발생한 횟수를 숫자로 먼저 보여주고 막대 그래프로도 보여줍니다. 그런데 단순히 발생 횟수만큼의 별 문자를 인쇄하면 실행 횟수(TRIALS)가 매우 커질 때 그래프 막대의 높이가 너무 커집니다. 이 문제를 해결하기 위해서 아래와 같이 합니다.
그래프 막대의 최대 높이(HEIGHT)를 정해 놓고 (가령 별 문자 50개) 발생 횟수 중 가장 큰 수가 그 높이의 막대로 나타나게 하려면 별 문자 하나가 숫자 얼마에 해당하는지를 계산합니다(가령 별 문자 하나가 13.7에 해당). 그리고, 각 발생 횟수는 별 문자 몇 개로 그려야 하는지를 계산해서 (발생횟수/13.7), 그 만큼의 별 문자를 막대 그래프로 그립니다. 별 문자의 일부만을 그릴 수는 없으므로 각 발생횟수에 해당하는 별 문자가 몇 개인지를 계산할 때는 (Math.round 메소드를 사용하여) 정수로 반올림합니다. 소수점 아래를 버려도 좋습니다.
실행 예를 보면 아래와 같습니다.
아래 그래프들은 모두 HEIGHT(그래프의 최대 높이)를 50으로 설정하고 실행한 결과입니다. 가장 긴 막대의 별 문자가 50개입니다.
(NUM_DICE = 1, TRIALS = 1,000, HEIGHT = 50일 때)
(NUM_DICE = 1, TRIALS = 100,000, HEIGHT = 50일 때)
(NUM_DICE = 2, TRIALS = 1,000, HEIGHT = 50일 때)
이 프로그램을 완성하기 위해서 DiceGraph 클래스에 graph 메소드 하나를 추가하시오(다중정의, method overloading).
프로그램을 완성하여 위에서 제시한 예와 유사한 출력이 얻어지면 아래와 같은 경우를 모의실험해 보시오.
HEIGHT는 50으로 고정.
NUM_DICE = 2 로 고정하고 아래와 같이 TRIALS를 변경하면서 실행
TRIALS =1,000, 100,000
TRIALS =100,000 로 고정하고 아래와 같이 주사위 갯수를 변경하면서 실행
NUM_DICE = 2, 5, 10, 20
과제를 제출할 때는, 위 문제 P3에서 작성한 main 메소드는 삭제하고, 이 문제에 맞는 main 메소드가 있는 상태로 제출하시오. 아래와 같이 설정된 상태로 제출하시오.
HEIGHT = 50
TRIALS =10,000
NUM_DICE = 5
P5
여러 어플리케이션에서 많이 쓰이는 배열 조작을 하나의 클래스에 구현해 놓고 필요할 때마다 사용하도록 합시다. 클래스 이름은 ArrayUtil로 지으시오. 지난 주에 작성한 클래스를 재사용하지 말고 새로 만드시오.
ArrayUtil에 아래와 같은 메소드를 작성하시오.
main 메소드를 작성하고 그 안에 printArray 메소드가 올바로 작동하는지 시험하는 코드를 넣으시오.
예를 들면 먼저 정수 배열을 만들고 임의의 숫자를 채운 후 아래와 같은 코드를 이용해 시험할 수 있습니다.
위 코드를 실행하면 아래와 같은 출력이 나와야 합니다. 0개를 출력하게 하면 아무 출력도 나타나지 않습니다. 배열의 크기보다 더 많은 갯수를 출력하도록 하면 배열 전체를 출력합니다.
테스트를 할 때는 통상적인 경우 외에, 특이한 경우(특히 0이나 1, 최대값 등 경계선)에 대해서도 문제가 없는지 철저히 테스트해야 합니다.
P6 (선형탐색(linear search))
선형탐색 메소드를 구현하고 테스트합니다. 클래스 이름은 Search로 지으시오.
Search 클래스 안에 아래와 같은 linearSearch 메소드를 구현하시오. 이 메소드는 주어진 정수 배열(x)의 앞 부분 n개의 방에 주어진 수(key)가 들어 있는지, 들어 있으면 어느 위치에 있는지 알아냅니다. 만약 key가 x의 앞부분 n개의 방에 들어 있지 않다면 메소드는 -1을 반환합니다. 만약 key가 x의 앞부분 n개의 방에 한 개 이상 들어 있다면 그 중 가장 작은 방 번호를 반환합니다.
Search 클래스 내에 이 linearSearch 메소드를 테스트하는 간단한 main 메소드를 작성하여 linearSearch 메소드가 올바르게 작동함을 확인하시오.
무엇을 테스트할 것인가? 예를 들면 아래와 같습니다.
-
key가 배열의 주어진 범위에 들어있는 경우 그 인덱스를 올바로 찾아내는가?
-
key가 배열의 주어진 범위에 여러 개 들어있는 경우 그 중 가장 작은 인덱스를 올바로 찾아내는가?
-
key가 배열의 주어진 범위에 없는 경우 -1을 반환하는가?
-
key가 배열에 있긴 하지만 주어진 범위 밖에 있을 때 -1을 반환하나?
-
n이 0일때는 항상 -1을 반환하나?
-
배열의 크기가 0일 때 항상 -1을 반환하나?
테스트 실행 결과 예를 보이면 아래와 같습니다.
위 그림과 같은 결과를 만들어 내기 위한 테스트 코드의 첫 머리는 아래 그림과 같습니다.
P7 (ArrayUtil)
여러 어플리케이션에서 많이 쓰이는 배열 조작을 ArrayUtil 클래스에 구현해 놓고 필요할 때마다 사용하기로 했습니다. ArrayUtil에 아래 메소드들를 추가하시오.
- 배열에 난수를 채워주는 메소드(원소 중복 허용) - fillRandom
- 배열에 있는 원소들의 중복 여부를 검사하는 메소드 - distinct
- 배열에 서로 다른 난수를 채워주는 메소드 - fillRandomDistinct
- 배열을 만들고 그 배열에 난수를 넣은 후 배열을 반환하는 메소드(원소 중복 허용) - makeRandomArray
(1) 아래와 같은 메소드를 작성하시오.
main 메소드에는 printArray 메소드를 테스트하는 코드가 이미 들어 있습니다. 그 코드에 덧붙여 위 fillRandom 메소드를 테스트하는 코드를 추가로 작성하시오. 테스트 결과 화면의 예를 들면 아래와 같습니다.
테스트를 할 때는 통상적인 경우 외에, 특이한 경우(특히 0이나 1, 최대값 등 경계선)에 대해서도 문제가 없는지 철저히 테스트해야 합니다.
(2) 아래와 같은 메소드를 작성하시오.
이 메소드를 구현할 때 Search.linearSearch 메소드를 사용하면 편리합니다.
main 메소드에는 printArray, fillRandom 메소드를 테스트하는 코드가 이미 들어 있습니다. 그 코드에 덧붙여 위 distinct 메소드를 테스트하는 코드를 추가로 작성하시오. 테스트 결과 화면의 예를 들면 아래와 같습니다.
위 결과를 만들어 낸 테스트 코드의 첫 머리는 아래와 같습니다.
(3) 아래와 같은 메소드를 작성하시오.
위 메소드 이름에 있는 distinct라는 단어는 “중복이 없는”의 의미를 갖습니다.
main 메소드에는 printArray, fillRandom 메소드를 테스트하는 코드가 이미 들어 있습니다. 그 코드에 덧붙여 위 fillRandomDistinct 메소드를 테스트하는 코드를 추가로 작성하시오. 테스트 결과 화면의 예를 들면 아래와 같습니다.
위 출력의 첫 부분은 아래 코드에 의해 만들어진 것입니다.
(4) 아래와 같은 메소드를 작성하시오.
main 메소드에는 printArray, fillRandom, fillRandomDistinct 메소드를 테스트하는 코드가 이미 들어 있습니다. 그 코드에 덧붙여 위 makeRandomArray 메소드를 테스트하는 코드를 추가로 작성하시오. 테스트 결과 화면의 예를 들면 아래와 같습니다.
아래 코드는 위 그림을 만들어 낸 코드 예입니다.
P8 (기억력놀이 (Memorygame))
위에서 작성한 메소드들을 이용하여 기억력놀이를 구현해 봅니다. 클래스 이름은 MemoryGame으로 짓습니다.
먼저 기억력놀이가 어떻게 작동하는지 아래 그림을 보세요.
사용자가 1을 입력하면 위의 내용이 화면 위로 밀려 올라가 더 이상 보이지 않게 됩니다.
그 상태에서 아래와 같은 화면이 나타나고 사용자는 자기가 기억하고 있는 숫자들을 입력합니다.
MemoryGame의 main에서는 아래와 같은 작업을 합니다.
- 몇 개의 정수를 볼지 물어보고 사용자가 입력하면 그 수만큼의 크기를 갖는 배열을 구성한 후 이 배열에 서로 다른 (중복된 숫자가 없도록) 난수를 채운다. 서로 다른 난수를 채우는 작업은 메소드 호출(ArrayUtil.fillRandomDinstinct(…))을 통해 수행한다.
- 배열에 있는 난수들을 화면에 보여주고 사용자가 1을 입력하면 화면에 새줄 문자를 100회 출력하여 화면을 밀어 올리고 기억하고 있는 숫자들을 입력하도록 안내한다.
- 사용자가 기억하고 있는 숫자들을 입력한 후 음수를 입력하면 이 숫자들을 또 다른 배열에 저장하고 사용자가 숫자를 몇 개나 입력했는지 기억한다.
- 사용자가 입력한 숫자가 난수 배열 중에 몇 개나 있는지 검사하여 결과를 출력한다. 사용자가 입력한 숫자가 난수 배열 중에 몇 개나 있는지 검사하는 작업은 Search 클래스의 linearSearch 메소드 호출을 통해 수행한다.
우선, 사용자가 입력한 숫자가 난수 배열 중에 몇 개나 있는지 검사하는 아래 메소드를 MemoryGame 클래스에 구현해 넣으시오. 이 메소드를 구현할 때 Search.linearSearch(…) 메소드를 이용합니다. 사용자가 입력한 숫자 각각이 난수 배열에 들어 있는지 탐색해 봐야 하기 때문입니다.
아래는 main 메소드입니다. 빈 곳을 채워 완성하시오.
위 어플리케이션은 MemoryGame, Search, ArrayUtil 등 세 개의 클래스로 구성되어 있습니다. 세 클래스 각각 main 메소드가 있지만 Search 클래스와 ArrayUtil 클래스에 만들어 놓은 main 메소드는 각각 그 클래스 내에 있는 메소드들이 올바르게 작동하는지 확인하기 위한 테스트 용이었습니다.
MemoryGame 어플리케이션을 실행하려면 MemoryGame 클래스에 들어 있는 main 메소드를 실행해야 합니다. 그러기 위해서는 MemoryGame 클래스가 선택되어 있는 상태로 프로그램을 실행시켜야 합니다. (혹은, MemoryGame 클래스를 오른쪽 마우스 버튼으로 눌러서 나타나는 팝업 메뉴에서 실행시킵니다.)
P9 (Union과 Intersection (합집합과 교집합))
난수로 만들어진 집합을 한 배열에 넣고, 또다른 난수로 만들어진 집합을 또 다른 배열에 넣은 후, 그 합집합과 교집합 배열을 계산하는 프로그램을 작성하시오. 클래스 이름은 UnionIntersection으로 지으시오.
(참고) 집합에서는 원소의 중복이 허용되지 않습니다.
따라서 난수 배열을 만들 때 ArrayUtil.fillRandomDistinct(…) 메소드를 사용해야 합니다.
아래는 실행 예입니다.
아래는 프로그램 뼈대입니다.
P10 (삽입정렬(Insertion Sort))
키보드로부터 입력된 정수들을 오름차순으로 정렬하는 프로그램을 삽입정렬 방식으로 구현하시오. 강의자료에 있는 것처럼 insert메소드와 sort 메소드를 구현하고, main 메소드를 두어 정렬 기능을 테스트하시오. 클래스 이름은 InsertionSort로 지으시오.
실행 예는 아래 그림과 같습니다.
프로그램 뼈대는 아래와 같습니다.
main 메소드에서는 데이터 몇 개를 정렬할 것인지 사용자에게 물어 보고, 사용자가 지정하는 수 만큼의 난수 배열을 만듭니다. 우선 난수 배열을 출력하고, sort 메소드를 이용하여 정렬한 후 정렬된 배열을 출력합니다. 난수 배열을 만들 때, 배열을 출력할 때 ArrayUtil의 메소드를 이용합니다.
P11 (이진탐색(Binary Search))
이 문제에서는 이진탐색 알고리즘을 메소드로 구현하고 그 성능을 관찰합니다.
우선 이미 만들어 놓은 Search 클래스 내에 아래와 같은 메소드를 추가로 구현합니다.
강의자료를 참고하세요.
그리고 지금 만든 이진탐색 메소드, bianarySearch가 올바로 작동하는지를 테스트하는 코드를 main 메소드에 추가하시오.
binarySearch(…) 메소드를 이용하기 전에 배열을 정렬해야 함에 유의하세요. 배열을 정렬하기 위해서는 InsertionSort.sort(…) 메소드를 이용합니다.
끝.