[자바 기초부터 하나씩/14장 연습문제 솔루션 답지 해답] 데이터 구조와 제네릭

1. 참 또는 거짓

만약 거짓이면 이유를 설명하여라.

a. 운동장에 있는 미끄럼틀은 큐보다는 스택과 유사하다.

답 : 거짓. 선입선출에 해당하는 큐와 유사합니다.

 

b. 한 개의 문만 작동하는 자동차는 큐보다는 스택과 더 유사하다.

답 : 참

 

c. 연결 리스트는 요소의 인덱스를 알고 있다면 리스트의 길이에 상관없이 리스트의 어떠한 요소로도 직접적인 접근이 가능하다.

답 : 거짓. 연결리스트는 이웃에 대한 링크만 가질 수 있으므로 직접적인 접근은 불가능합니다.

 

d. 배열과 달리, ArrayList는 동적으로 크기를 증가시킬 수 있다.

답 : 참

 

e. 순환 배열에서 가장 큰 숫자의 인덱스 다음의 인덱스는 0이고, 0보다 앞서는 인덱스는 가장 큰 값의 인덱스이다.

답 : 참

 

f. 큐는 뒤로 돌아가는(backtrack) 작업이 포함된 문제를 위한 좋은 데이터 구조이다.

답 : 거짓. 큐보다는 스택이 더 유용합니다.

 

g. 제네릭 클래스를 사용하면 데이터 유형에 독립적인 데이터 구조를 정의할 수 있다.

답 : 참

 

h. 제네릭 클래스는 상표(brand name)가 없는 클래스이다.

답 : 거짓

 

i. ArrayList 객체는 같은 효율로 리스트의 앞과 뒤에서 삽입을 처리한다.

답 : 거짓

 

j. 단지 두 개의 팬 케이크로 이루어진 아침 식사나, 포커 테이블에서 적은 수의 칩은 짧은 스택의 한 종류라고 할 수 있다.

답 : 참

 

 

2. 컴파일러 실행

다음 클래스에서 구문 오류와 논리 오류(들)를 찾고 수정하여라. Board는 두 명의 게임을 캡슐화 한다. Board는 T유형을 저장하는 2차원 배열을 사용한다. 또한 Board는 1번 플레이어의 차례인지 2번 플레이어의 차례인지를 기억한다.

class Board<T>

{

private ArrayList <T>items; //①

int turn; //어느 플레이어의 차례인가, 1또는 2

public Board()

//기본 생성자

{

items = new <T>bo[8][8]; //②

turn = 1;

}//빈 8 x 8 2차원 배열을 생성

 

public Board(int initialCapacity, int player )

// 단일 인수 생성자, initialCapacity의 행과 열을 갖는

// 2차원 배열 생성.

{

items = new <T>bo[initialCapacity] [initialCapacity]; //③

turn = player;

}

 

public Board(int initialRowCapacity, int initialColumnCapacity, int player)

// 두 인수 생성자, initialCapacity의 행과 열을 갖는

// 2차원 배열을 생성

{

items = new <T>bo[initialCapacity] [initialCapacity]; //④

turn = player;

}

 

public T whoseturn()

//⑤

//누구의 차례인지를 위한 접근자(accessor)

{

return (turn);

}

 

public T addtoBoard(T item, int row, int col)

//⑥

//보드에 한 조각을 놓을 수 있도록 함.

{

bo[row, col] = item; // ⑦

}

 

public T peek(int row, int col)

// 보드에서 한 조각을 볼 수 있도록 함.

{

return bo[row][col];

//⑧

}

 

public void switchturn()

//다음 차례를 서로 바꾸도록 함.

{

if (turn == 1)

turn = 2;

if (turn == 2) //⑨

turn = 1;

}

}

① private T[][] items;

② items = (T[][]) new Object[8][8];

③ items = (T[][]) new Object[initialCapacity][initialCapacity];

④ items = (T[][])new Object[initialRowCapacity] [initialColumnCapacity];

⑤ int 타입을 return 해야합니다.

⑥ T는 void 타입이여야 합니다.

⑦ items[row][col] = item;

⑧ bo가 아닌 item을 return해야합니다.

⑨ if (turn == 1)

turn = 2;

else

turn = 1;

 

 

3.컴파일러 실행

각각의 다음 코드에 대해 오류를 설명하고 수정하여라. 만약 코드가 올바른 상태이면, 오류가 없다고 하여라.

a. ArrayList <Integer> test = new ArrayList<Integer>(20);

list.add("35");

list.add(35);

답 : Integer타입이아닌 list.add("35");에서 오류가 납니다.

 

b. ArrayList temp = new ArrayList();

temp.add("35");

temp.add(35);

답 : 오류가 없음.

 

c. Stack<Integer> = new Stack();

push(1);

push('a');

답 : 오류가 없음.

 

d. Stack<ArrayList <Integer>> really = new Stack<ArrayList <Intger>>();

답 : 오류가 없음.

 

e. LList <Integer> testlist = new testlist<Integer>();

testlist[3] = 7;

답 : LList라는 클래스가 존재하지 않기 때문에 컴파일 되지 않습니다.

 

4. 데이터 구조 선택

다음 각 문제에 대해 어떤 데이터 구조를 사용할 수 있을지 자신의 선택에 대해 설명하여라.

 

a. 자바는 가용한 메모리 위치를 찾고, 그 위치에 새로운 객체가 배정될 수 있도록 하기 위해서 가비지 컬렉션(garbage collection)을 사용한다. new 명령이 사용될 때마다 생성된 새로운 객체를 위한 저장 공간을 생성하기 위해 메모리가 할당된다. 어떤 데이터 구조에 이러한 장소를 저장할 수 있겠는가? 이유는?

답 : 메모리가 해제된 순서대로 대기열을 사용합니다.

 

b. 비디오 편집기는 비디오 클립을 이어 붙임으로써 비디오 무비가 생성되도록 해 준다.

사용자는 두 개의 클립 사이에 클립을 추가하고 삭제하거나, 다른 위치로 클립을 이동시킬 수 있다. 결국 이어붙은 클립들이 연속적으로 재생되어 최종 비디오가 완성된다. 어떤 데이터 구조에 저장된 클립을 저장할 수 있겠는가? 이유는?

답 : 링크 된 목록에 저장해야합니다. 클립을 순서대로 재생하면 목록을 간단하게 탐색할 수 있습니다.

 

5. 데이터 구조 선택

다음 각 문제에 대해 가능한 가장 효율적인 방법으로 문제를 해결하기 위해 사용할 수 있는 데이터 구조를 결정하여라. 효율적인 가장 간단한 데이터 구조(들)를 사용해야 한다.

a. 웹을 위한 브라우저(browser) 프로그램을 만들고 있는데, 작성 중인 브라우저는 ‘뒤로’와 ‘앞으로’ 버튼의 적절한 구현을 위해 사용자가 방문했던 모든 사이트를 기억하고 있어야 한다.

답 : 뒤로, 앞으로를 구현하기 위해서는 Stack을 사용해야 합니다.

 

b. 사이트가 주어졌을 때, 그와 연결된 모든 사이트를 찾고, 그 다음에 그 사이트들과 연결된 모든 사이트를 찾고, 등등 10단계까지 이를 수행하는 웹 크롤링(web crawling) 프로그램을 만드는 중이다. 이 프로그램은 모든 사이트와 해당 레벨의 목록을 보유하고 있다.

답 : FIFO에 해당하는 Queue를 사용해야합니다. 첫 번째 링크는 다음 링크로 이동하기 전에 먼저 처리 됩니다.

 

 

6. 스택 구현

때로는 어떤 데이터 구조가 다른 데이터 구조를 구현하는 데 사용될 수 있다. 예를 들어, 이장에서 ArrayList는 스택을 구현하기 위해 사용된다. 다음을 사용하여 스택을 어떻게 구현할 수 있는지를 서술하여라.

 

a. 연결 리스트

b. 큐

push(...)와 pop(...) 메소드의 효율성은 스택에 있는 요소의 수에 따라 달라지는가?

a. 링크된 목록의 시작부분에 요소를 추가하거나 제거합니다. 스택이 필요에 따라 동적으로 커질 수 있기 때문입니다. push,pop은 요소의 수에 관계없이 항상 일정한 시간이 걸립니다.

 

b. 대기열의 뒷면에 요소를 추가합니다. pushing은 일정한시간이 걸리고, pop은 대기열의 요소 수에 따라 달라집니다.

 

7. ArrayList<E> 구현

ArrayList<E> 객체가 더 많은 공간을 필요로할 때, 더 많은 메모리를 할당하고 메모리의 큰 블록으로 현재 객체를 복사함으로써 자기 자신의 크기를 변경한다.

ArrayList<E> 객체가 자기 자신의 크기를 변경할 때 얼마나 많은 공간을 할당하는가? 다음 세 가지 방법을 고려해보자.

 

a. 10 만큼 크기 증가

b. 현재 크기 두 배로 증가

c. 1만큼 크기 wd가

 

다음을 가정한다.

●ArrayList<E>의 크기는 10으로 초기화된다.

●새로운 데이터는 한 번에 하나의 값을 갖는다.

●결국 리스트는 80개의 값을 수용해야 한다.

크기 변경을 위한 세 가지 방법을 사용하여 복사될 요소의 총 수를 계산하여라. ArrayList<E>를 구현하는 데 어떤 방법을 사용하겠는가? 이유는?

b를 사용하겠습니다. 그 이유는

a = 10개씩 변경시에 10개의 값을 처음으로 복사해야하고 다음 크기 조정은 20개의 요소를 복사해야 합니다. 크기마다 10개의 더많은 요소가 복사되어야 함. 10+20+30+40+50+60회(210)가 복사되어야 함.

b = b를 사용하는 것이 가장 좋습니다 처음으로 용량을 두 배로 늘리면 10개의 요소가 복사되고, 처음에 20이 복사됩니다. 마지막으로 40개가 추가되어 70개가 복사됩니다.

c = 처음에는 값1이 복사되고 다음에 2가 복사되고 3번에 3이 복사됩니다. 이 패턴은 70까지 반복되는데 1+2+3+4+...+69를 하면 값은 2415개가 되므로 비효율적입니다.

 

8. ArrayList<E>와 LList<E>

ArrayList<E>와 LList<E>는 많은 수의 같은 메소드를 제공하고 있다. 이들은 ListInterface<E>에서 열거된다. 그러나 LList<E>는 ArrayList<E>에 의해 제공되지 않는 다음과 같은 세 개의 메소드를 제공해 준다.

 

●void reset()

●boolean hasNext()

●E next()

 

ArrayList<E>에서 이들 메소드를 구현하지 않는 이유를 설명하여라. 이들 메소드가 LList<E>의 구현에는 포함되는 이유는?

답 : arraylist에는 재설정 포인터가 없기 때문에 reset () 메소드가 없습니다. hasnext () 메서드는 현재 요소 뒤에 오는 것이 있는지 여부를 알려줍니다. 마찬가지로, next ()는 현재 요소 뒤의 요소를 반환합니다.

 

 

9. 데이터 구조로 예외 사용

a. 스택이 비어있을 때 pop()이 NoSuchElementException 예외를 전달하도록 Stack<E>의 pop() 메소드를 다시 작성하여라. 또한 StackInterface<E>를 변경해야 할 것이다.

private int size;

private int[] data;

public void pop(){

if(size == 0){

return throw new NoSuchElementException();

}

data[front++];

}

 

b. Queue<E>의 메소드인 insert(E x)와 remove()를 다시 작성하여, 각각이 널(null)을 반환하거나 갑작스럽게 종료되지 않고 적절한 예외를 발생시키도록 하여라. QueueInterface<E>를 적당하게 수정하여라.

private int front;

private int[] data;

public void insert(E x){

if(top == data.length){

System.out.println("isFull");

}else{

data[top++] = num;

}

}

public void pop(){

if(top==front){

System.out.println("Empty!");

}

data[front++];

}

 

c. 다섯 개의 LList<E> 메소드는 예외 조건 하에서 갑자기 종료된다. 이를 메소드를 다시 작성하여 각각이 적절한 예외를 발송시키도록 하여라.

private int front;

private int[] data;

public void insert(E x){

if(top == data.length){

System.out.println("isFull");

}else{

data[top++] = num;

}

}

public void pop(){

if(top==front){

System.out.println("Empty!");

}

data[front++];

}

 

10. 결함 찾기

예제 14.6에서 사용된 알고리즘을 다음과 같이 쓸 수 있다고 가정하여라.

0부터 59까지 각각의 분(minute)에 대하여

{

만약 기다리는 사람이 있고, 그리고 ATM 기가 사용가능 하다면

{

큐에서 사람을 제거한다;

서비스를 받은 사람(사용자)의 수를 증가시킨다;

현재 사람의 대기 시간을 전체 대기 시간에 더한다;

ATM의 다음 가용 시간을 업데이트한다;

}

새로 도착한 사람의 수를 결정한다: 0, 1, 2;

각각의 새로 온 사람에 대해

큐에 새로온 사람을 넣는다;

}

통계 요약을 화면에 표시한다.

답 : 이 알고리즘의 결함을 찾아보아라. 어떻게 잘못된 출력이 발생하는지 설명하여라.

대기열이 비어 있음과 동시에 시간이 비어있을 경우 잘못된 출력이 발생합니다. if문에서 대기열 고객이 없으므로 고객이 atm에 안들어가고 다음 고객은 atm기가 비었음에도 즉시 atm으로 향하지 않습니다. 고객은 시간 t + 1까지 대기해야만 atm으로 진행할 수 있습니다.