Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

재귀 알고리즘의 비재귀적 표현

static void recur(int n)
{
    if(n > 0)
    {
        recur(n - 1);
        System.out.println(n);
        recur(n-2);
    }
}

위 메소드의 꼬리 재귀를 제거하는 방법과 비재귀적 표현으로 나타내는 방법을 정리하려고 한다.

꼬리 재귀의 제거

메소드의 꼬리에서 재귀 호출하는 메소드 recur(n-2)는 파라미터로 n-2를 전달하여 recur 메소드를 호출한다는 뜻이다. 따라서 이 호출은 'n의 값을 n-2로 업데이트하고 메소드의 시작 지점으로 돌아간다'는 뜻이다.

아래는 위 방법을 그대로 구현한 코드이다. n의 값을 -2만큼 감소한 후 메소드의 시작 지점으로 돌아간다.

static void recur(int n)
{
    while (n > 0) {
        recur(n - 1);
        System.out.println(n);
        n = n-2;
    }
}

이렇게 하면 메소드의 끝에서 실행하는 꼬리 재귀는 쉽게 제거할 수 있다.

그림으로 표현하면 아래와 같다.

재귀의 제거

꼬리 재귀와는 다르게 앞에서 호출한 재귀 메소드(recur(n-1))의 제거는 쉽지 않다. 예를 들어 n이 4인 경우 재귀호출 recur(3)의 처리가 완료되지 않으면 n의 값인 4를 저장해야 한다. 

그래서 recur(n-1)을 아래처럼 바로 바꿀 수 없다.

• n의 값을 n-1로 업데이트하고 메소드의 시작 지점으로 돌아간다.

왜냐하면 다음과 같은 작업을 미리 해야 하기 때문이다.

• 현재 n의 값을 잠시 저장

또 recur(n-1)의 처리가 완료된 다음에 n의 값을 출력할 때는 다음 과정을 따르게 된다.

• 저장했던 n을 다시 꺼내 그 값을 출력

이런 재귀 호출을 제거하기 위해서는 변수 n의 값을 잠시 저장해야 한다는 점이다.

이런 문제를 잘 해결할 수 있는 데이터 구조가 스택이다.

아래의 코드는 스택을 이용한 재귀의 제거이다.

스택 구현

public class IntStack {
	private int max;
	private int ptr;
	private int[] stk;

	public class EmptyIntStackException extends RuntimeException {
		public EmptyIntStackException() { }
	}

	public class OverflowIntStackException extends RuntimeException {
		public OverflowIntStackException() { }
	}

	//--- 생성자 ---//
	public IntStack(int capacity) {
		ptr = 0;
		max = capacity;
		try {
			stk = new int[max];	// 스택본체용의 배열을 생성
		} catch (OutOfMemoryError e) { // 생성할 수 없음
			max = 0;
		}
	}

	public int push(int x) throws OverflowIntStackException {
		if (ptr >= max)									// 스택은 가득 참
			throw new OverflowIntStackException();
		return stk[ptr++] = x;
	}

	public int pop() throws EmptyIntStackException {
		if (ptr <= 0)
			throw new EmptyIntStackException();
		return stk[--ptr];
	}

	public int peek() throws EmptyIntStackException {
		if (ptr <= 0)
			throw new EmptyIntStackException();
		return stk[ptr - 1];
	}

	public int indexOf(int x) {
		for (int i = ptr - 1; i >= 0; i--)
			if (stk[i] == x)
				return i;
		return -1;
	}

	public void clear() {
		ptr = 0;
	}

	public int capacity() {
		return max;
	}

	public int size() {
		return ptr;
	}

	public boolean isEmpty() {
		return ptr <= 0;
	}

	public boolean isFull() {
		return ptr >= max;
	}

	public void dump() {
		if (ptr <= 0)
			System.out.println("스택이 비어있습니다..");
		else {
			for (int i = 0; i < ptr; i++)
				System.out.print(stk[i] + " ");
			System.out.println();
		}
	}
}

재귀를 제거한 메소드

static void recur(int n)
{
    IntStack s = new IntStack(n);

    while (true) {
        if (n > 0) {
            s.push(n);
            n = n - 1;
            continue;
        }
        if (s.isEmpty() != true) {
            n = s.pop();
            System.out.println(n);
            n = n - 2;
            continue;
        }
        break;
    }
}

실행 예제

public class Main{

	static void recur(int n) {
		IntStack s = new IntStack(n);
	
		while (true) {
			if (n > 0) {
				s.push(n);
				n = n - 1;
				continue;
			}
			if (s.isEmpty() != true) {
				n = s.pop();
				System.out.println(n);
				n = n - 2;
				continue;
			}
			break;
		}
	}


	public static void main(String[] args) {
		recur(4);
		}
	}
/*
1
2
3
1
4
1
2
*/

위 코드에서 스택을 그림으로 나타내면 아래와 같다.

static void recur(int n)
{
    if(n>3)
    {
        recur(n-1);
        recur(n-2);
        System.out.println(n);
    }
}

위 알고리즘을 비재귀적으로 작성하면 아래와 같다.

static void recur(int n)
{
    int[] nstk = new int[100];
    int[] sstk = new int[100];
    int ptr = -1;
    int sw = 0;

    while (true) {
        if (n > 0) {
            ptr++;
            nstk[ptr] = n;
            sstk[ptr] = sw;

            if (sw == 0)
                n = n - 1;
            else if (sw == 1) {
                n = n - 2;
                sw = 0;
            }
            continue;
        }
        do {
            n = nstk[ptr];
            sw = sstk[ptr--] + 1;

            if (sw == 2) {
                System.out.println(n);
                if (ptr < 0)
                    return;
            }
        } while (sw == 2);
    }
}

그림 출처 : https://velog.io/@jimmy48

본 게시글은 유튜브 : 경제 TV 너무경 : 너무 쉬운 경제 윤성종 님의 유튜브 영상을 참고하였습니다. 개인적으로 정리하는  글임을 알립니다.

금융용어정리 - 주식 거래시간

주식 거래시간

전날 종가가 9,000원이었고, 오늘 종가가 10,000원이라면

• 08:30~08:40 : 전일 종가(9,000원)로 거래 가능
• 08:30~09:00 : 장 시작 전 동시호가매매시간
• 09:00~15:30 : 정규시장
• 15:20~15:30 : 장 마감 후 동시호가매매시간
• 15:30~16:00 : 당일 종가(10,000원)로 거래 가능
• 16:00~18:00 : 10분에 한번씩 당일 종가 ±10%가격(9,000~11,000원)으로 거래 가능

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

재귀 알고리즘을 분석하는 방법은 아래의 두가지가 있다.

• 하향식(top down) 분석 방법
• 상향식(bottom up) 분석 방법

아래의 코드를 바탕으로 하향식과 상향식 분석 방법을 정리하겠다.

static void recur(int n)
{
    if(n > 0)
    {
        recur(n-1);
        System.out.println(n);
        recur(n-2);
    }
}

위 메소드에 파라미터에 4를 넘기면 아래와 같은 결과가 나온다.

하향식 분석

파라미터에 4를 넘기면 recur 메소드는 아래 과정을 순서대로 실행한다.

• ① recur(3)을 실행
• ② 4를 출력
• ③ recur(2)를 실행

아래의 그림에서 상자는 recur 메서드의 동작을 나타낸다. 전달받은 값이 0 이하면 아무 일도 하지 않으므로 검은색 상자로 표시되어 있다.

위의 그림은 맨 꼭대기에서 왼쪽 화살표를 따라 하나 아래 상자로 이동하고, 다시 원래의 상자로 돌아오면 회색박스의 내용을 출력하고 이어서 오른쪽 화살표를 따라 한 칸 아래 상자로 이동하면서 해석하면 된다.

이처럼 가장 위쪽에 위치한 상자의 메소드 호출부터 시작해 계단식으로 자세히 조사하는 분석 기법을 하향식 분석이라고 한다. 그런데 이 그림 안에는 recur(1), recur(2)와 같은 동일한 호출이 여러 번 있다. 꼭대기부터 분석하면 이렇게 같은 메소드의 호출이 여러 번 나올 수 있기 때문에 하향식 분석이 반드시 효율적이라고 말할 수 없다.

상향식 분석

위쪽부터 분석하는 하향식 분석과는 대조적으로 아래쪽부터 쌓아 올리며 분석하는 방법이 상향식 분석이다.

recur(1)이 수행하는 작업은 아래와 같다.

• ① recur(0)을 실행
• ② 1를 출력
• ③ recur(-1)을 실행

①과 ③은 출력할 내용이 없다 따라서 ②의 1만 출력한다.

recur(2)의 수행하는 작업은 아래와 같다.

• ① recur(1)을 실행
• ② 2를 출력
• ③ recur(0)을 실행

이러한 작업을 recur(4)까지 과정은 아래의 그림과 같다.

그림 출처 : https://velog.io/@jimmy48

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

재귀란 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(Recursive)이라고 한다.

재귀는 직접 재귀와 간접 재귀로 나뉜다.

• 직접 재귀 : 메소드 a가  자신(메소드 a)을 호출
• 간접 재귀 : 메소드 a가 메소드 b를 호출하고, 메소드 b는 메소드 a를 호출

재귀 메소드는 정지조건(재귀 앵커)을 제대로 설정하지 않으면 무한 루프와 같이 끝없이 재귀 메소드가 호출되므로 유의하여야 한다.

팩토리얼 구하기

음이 아닌 정수 n의 팩토리얼(n!)은 아래처럼 재귀적으로 정의할 수 있다.

1. 0! = 1
2. n > 0 이면 n! = n * (n-1)!

위의 정의를 그대로 구현하면 아래와 같다.

static int factorial(int n)
{
    if(n > 0) return n * factorial(n-1);
    else return 1; //정지 조건
}

실행 예제

public class Main{
	
	static int factorial(int n)
	{
		if(n > 0) return n * factorial(n-1);
		else return 1;
	}
	
	public static void main(String[] args) {
		
		for(int i = 0; i < 10; ++i) System.out.println(i + " : " + factorial(i));

	}
}
/*
0 : 1
1 : 1
2 : 2
3 : 6
4 : 24
5 : 120
6 : 720
7 : 5040
8 : 40320
9 : 362880
 */

재귀를 사용하지 않고 팩토리얼을 구하는 알고리즘은 아래와 같다.

static int factorial(int n)
{
    if(n == 0) return 1;
    int tmp = 1;
    for(int i = 1; i <= n; ++i) tmp *= i;
    return tmp;
}

두 정수의 최대공약수 구하기

static int gcd(int x, int y)
{
    if(y == 0) return x;
    else return gcd(y, x % y);
}

실행 예제

public class Main{
	
	static int gcd(int x, int y)
	{
		if(y == 0) return x;
		else return gcd(y, x % y);
	}
	
	public static void main(String[] args) {
		
		System.out.println("22와 8의 최대공약수 : " + gcd(22, 8));

	}
}
/*
22와 8의 최대공약수 : 2
*/

유클리드 호제법
위 알고리즘은 유클리드 호제법을 이용한 것이다.
두 정수를 직사각형의 두 변의 길이라고 생각하면 두 정수의 최대공약수를 구하는 문제는
직사각형을 정사각형으로 완전히 채우고 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하면 된다.

1. 짧은 변의 길이를 한 번으로 하는 정사각형으로 채운다.
2. 남은 직사각형에 대해 같은 작업을 반복
3. 정사각형만으로 구성되었을 때의 변의길이가 최대공약수

재귀를 사용하지 않은 두 정수의 최대공약수를 구하는 알고리즘은 아래와 같다.

static int gcd(int x, int y)
{
    while(y != 0)
    {

        int temp = y;
        System.out.println(y + " " + x);
        y = x % y; //y에 나머지 저장
        x = temp;
    }
    return x;
}

배열의 모든 원소의 최대공약수 구하기

import java.util.Scanner;
public class Main{
	
	static int gcd(int x, int y) {
		if(y == 0) return x;
	    else return gcd(y, x % y);
	}

	static int gcdArray(int arr[], int start, int no) {
		if (no == 1) return arr[start];
		else if (no == 2) return gcd(arr[start], arr[start + 1]);
		else return gcd(arr[start], gcdArray(arr, start + 1, no - 1));
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("정수 몇 개의 최대 공약수를 구할까요?：");
		int num;
		do {
			num = sc.nextInt();
		} while (num <= 1);

		int[] arr = new int[num];

		for (int i = 0; i < num; i++) {
			System.out.print("x[" + i + "]：");
			arr[i] = sc.nextInt();
		}

		System.out.println("최대 공약수는 " + gcdArray(arr, 0, num) + "입니다.");
		}
	}
/*
정수 몇 개의 최대 공약수를 구할까요?：3
x[0]：25
x[1]：1525
x[2]：2000
최대 공약수는 25입니다.
*/

본 게시글은 유튜브 : 경제 TV 너무경 : 너무 쉬운 경제 윤성종 님의 유튜브 영상을 참고하였습니다. 개인적으로 정리하는  글임을 알립니다.

금융용어정리 - 따상

따상

따상은 아래의 조건을 만족하는 경우를 칭하는 속어이다.

• 시가가 공모가(주식시장에 최초로 상장될 때의 주식 한 주당 가격)의 두 배가 된 경우
• 종가가 시가의 +30%인 경우

시가
장 시작전 동시호가매매시간이 끝남과 동시에 시가가 결정된다.
시가는 시초가라고 부르기도 한다.

주식 시장에서 주가는 최대 30% 상승 또는 하락할 수 있다. 이는 동시호가도 마찬가지이다.

하지만 한 가지 예외가 있는데, 처음 상장하는 날은 동시호가가 -10% ~ 100%까지 하락 또는 상승이 가능하다.

예를 들어
공모가 5,000원으로 상장하고 장 시작전 동시호가매매시간(08:30~09:00)이 끝나고 시가가 공모가의 두 배가 되어 시가가 1만 원으로 형성되고 또다시 15:20 ~ 15:30에 동시호가매매시간이 끝나고 종가가 시가의 30% 상승한 13,000원이 되면 따상에 성공한 것이다.

동시호가의 개념을 모른다면 아래의 링크 클릭

2022.11.16 - [경제/금융용어] - 금융용어정리 - 주식매매체결의 원칙, 동시호가

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

큐

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다. 하지만 큐는 스택과 다르게 선입선출(FIFO, First In First Out)이다.

아래의 그림과 같이 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조로 되어 있다.

큐에 데이터를 넣는 작업을 인큐라 하고, 데이터를 꺼내는 작업을 디큐라고 한다.

인큐와 디큐

인큐

위 그림에서 리어(rear)인 53 뒤에 24를 인큐 한다.

이 처리의 시간복잡도는 O(1)이고 적은 비용으로 구현할 수 있다.

디큐

위 그림에서 프론트(front)인19와 22을 디큐 한다. 디큐한 후에는 모든 요소를 앞으로 옮겨야 한다.

이 처리의 시간복잡도는 O(N)이며 데이터를 꺼낼 때마다 이런 처리를 하게 되면 효율이 떨어진다.

구현

IntAryQueue 클래스 (int형 배열로 구현)

public class IntAryQueue {
    private int max; //큐 용량
    private int num; //현재 데이터 수
    private int[] que;

    IntAryQueue(int capacity) //생성자
    {
        this.max = capacity;
        que = new int[max];
        num = 0;
    }

    private boolean isFull() {return num >= max;} //큐의 공간이 모두 사용중인지 리턴

    private boolean isEmpty() {return num <= 0;} //큐의 공간이 비어있는지 리턴

    public int capacity() {return max;} //큐의 용량을 리턴

    public int size() {return num;} //큐의 현재 데이터 수를 리턴

    public void enque(int value)
    {
        if(!isFull()) que[num++] = value;
        else System.out.println("큐의 공간을 모두 사용중입니다.");
    }

    public void deque()
    {
        if(!isEmpty())
        {
            for (int i = 1; i < num; ++i)
            {
                que[i-1] = que[i];
            }
            que[--num] = 0;
        }
        else System.out.println("이미 큐의 공간이 비어있습니다.");
    }

    public void peek() //큐의 front를 리턴
    {
        if(num > 0) System.out.println("front : " + que[0]);
        else System.out.println("큐의 공간이 비어있습니다.");
    }

    public void back() //큐의 rear을 리턴
    {
        if(num > 0) System.out.println("rear : " + que[num- 1]);
        else System.out.println("큐의 공간이 비어있습니다.");
    }

    public void indexOf(int value) //큐에서 찾는 데이터가 있는지 출력
    {
        for(int i = 0; i < num; ++i)
        {
            if(que[i] == value)
            {
                System.out.println("찾는 값이 있습니다. 인덱스 : " + i);
                return;
            }
        }
        System.out.println("찾는 값이 없습니다.");
    }

    public void clear() {num = 0;} //큐의 front를 초기화 시킴

    public void dump() //모든 큐의 값을 출력
    {
        if(isEmpty())
        {
            System.out.println("큐가 비어있습니다.");
            return;
        }
        for (int i = 0; i < num; ++i)
        {
            System.out.println("[" + i + "]" + "=" + que[i]);
        }
    }
}

실행 예제

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("큐 용량 입력 : ");
        int command = sc.nextInt();
        IntAryQueue que = new IntAryQueue(command);
        while(true)
        {
            System.out.println();
            System.out.println("현재 데이터 수 : " + que.size() + "/" + que.capacity());
            System.out.println("(1)inqueue (2)dequeue (3)search (4)front (5)back (6)dump (7)clear (8)exit");
            System.out.print("cmd : ");
            command = sc.nextInt();
            if(command == 1)
            {
                System.out.print("value : ");
                command = sc.nextInt();
                que.enque(command);
            }
            else if(command == 2) que.deque();
            else if(command == 3)
            {
                System.out.print("Data for Search: ");
                command = sc.nextInt();
                que.indexOf(command);
            }
            else if(command == 4) que.peek();
            else if(command == 5) que.back();
            else if(command == 6) que.dump();
            else if(command == 7) que.clear();
            else if(command == 8) System.exit(0);
            else continue;
        }
    }
}

링 버퍼(Ring Buffer)

일반 큐는 디큐를 하고나서 모든 배열의 요소를 맨 앞으로 옮기는 작업을 해야 했다.

그래서 시간복잡도가 증가하였다.

링 버퍼 큐는 배열의 요소를 앞쪽으로 옮기지 않는 큐이다.

링 버퍼 큐는 배열의 처음과 끝이 연결되었다고 보는 자료구조이다.

여기서 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수가 front와 rear이다.

• front : 맨 처음 요소의 인덱스
• rear : 맨 끝 요소의 하나 뒤의 인덱스(다음 요소를 인큐 할 위치를 미리 지정)
• front와 rear는 논리적인 데이터 순서를 말한다. 배열의 물리적 요소의 순서가 아니다.

인큐, 디큐, 검색

인큐

인큐를 할 때, 데이터는 que[rear]에 저장된다. 즉, 데이터는 rear에 저장된다.

만약 rear가 배열의 공간과 같다면(배열의 최대 인덱스보다 크다면), rear를 배열의 가장 작은 인덱스로 바꿔줘야 한다.

que[rear++] = value;
++num;
if(rear == max) rear = 0;

디큐

디큐를 할 때, que[front]의 데이터가 삭제된다.

만약 front가 배열의 공간과 같다면(배열의 최대 인덱스보다 크다면), front를 배열의 가장 작은 인덱스로 바꿔줘야 한다.

que[front++] = 0;
--num;
if(front == max) front = 0;

검색

for(int i = 0; i < num; ++i)
{
    int index = (i + front) % max;
    if(que[index] == value)
    {
        System.out.println(value + "는 큐의 " + (i+1) + "번째 데이터이고, 배열의 " + index + "인덱스에 있습니다.");
        return;
    }
}
System.out.println("찾는 값이 없습니다.");

front가 6이고, 배열의 길이가 12라면 i와 index는 아래와 같다.

• i : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
• index : 7 -> 8 -> 9 -> 10 -> 11 -> 0 -> 1

구현

int형 배열을 이용한 IntQueue 클래스

public class IntQueue {
	private int max; //큐 용량
	private int num; //현재 데이터 수
	private int front; //디큐를 할 인덱스를 가리킴
	private int rear; //인큐를 할 인덱스를 가리킴
	private int[] que;
	
	IntQueue(int capacity) //생성자
	{
		this.max = capacity;
		num = front = rear = 0;
		que = new int[max];
	}
	
	private boolean isEmpty() {return num <= 0;} //큐가 비어있는지를 리턴
	
	private boolean isFull() {return num >= max;} //큐의 공간이 모두 사용중인지 리턴
	
	public int capacity() {return max;} //큐의 용량을 리턴
	
	public int size() {return num;} //큐가 현재 사용중인 공간을 리턴
	
	public void clear() {num = front = rear = 0;} //큐 초기화
	
	public void enque(int value)
	{
		if(!isFull())
		{
			que[rear++] = value;
			++num;
			if(rear == max) rear = 0;
			return;
		}
		else
		{
			System.out.println("큐의 모든 공간이 사용중입니다.");
			return;
		}
	}
	
	public void deque()
	{
		if(!isEmpty())
		{
			que[front++] = 0;
			--num;
			if(front == max) front = 0;
			return;
		}
		else
		{
			System.out.println("이미 큐가 비어있습니다.");
			return;
		}
	}
	
	public void peek() //front를 출력
	{
		if(!isEmpty()) System.out.println(que[front]);
		else System.out.println("큐가 비어있습니다.");
	}
	
	public void indexOf(int value) //값이 배열에 존재하는지와 몇 번째 데이터인지, 배열의 몇 번째 인덱스인지 출력
	{
		for(int i = 0; i < num; ++i)
		{
			int index = (i + front) % max;
			if(que[index] == value)
			{
				System.out.println(value + "는 큐의 " + (i+1) + "번째 데이터이고, 배열의 " + index + "인덱스에 있습니다.");
				return;
			}
		}
		System.out.println("찾는 값이 없습니다.");
	}
	
	public void dump() //큐에 저장중인 모든 데이터 출력
	{
		if(!isEmpty())
		{
			for(int i = 0; i < num; ++i)System.out.println(i+1 + "번째 데이터 : " + que[(i + front) % max]);
		}
		else System.out.println("큐가 비어있습니다.");
	}
}

실행 예제

import java.util.Scanner;
public class Main2{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("큐 용량 입력 : ");
		int command = sc.nextInt();
		IntQueue que = new IntQueue(command);
		while(true)
		{
			System.out.println();
			System.out.println("현재 데이터 수 : " + que.size() + "/" + que.capacity());
			System.out.println("(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit");
			System.out.print("cmd : ");
			command = sc.nextInt();
			if(command == 1)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				que.enque(command);
			}
			else if(command == 2) que.deque();
			else if(command == 3)
			{
				System.out.print("Data for Search: ");
				command = sc.nextInt();
				que.indexOf(command);
			}
			else if(command == 4) que.peek();
			else if(command == 5) que.dump();
			else if(command == 6) que.clear();
			else if(command == 7) System.exit(0);
			else continue;
		}
	}
}
/*
큐 용량 입력 : 5

현재 데이터 수 : 0/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 1

현재 데이터 수 : 1/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 2

현재 데이터 수 : 2/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 3

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 4

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 5

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 6

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 7

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 5
1번째 데이터 : 3
2번째 데이터 : 4
3번째 데이터 : 5
4번째 데이터 : 6
5번째 데이터 : 7

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 3
Data for Search: 5
5는 큐의 3번째 데이터이고, 배열의 4인덱스에 있습니다.

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 2/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 8

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 9

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 10

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 5
1번째 데이터 : 6
2번째 데이터 : 7
3번째 데이터 : 8
4번째 데이터 : 9
5번째 데이터 : 10

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 22

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 2/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 1/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 0/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2
이미 큐가 비어있습니다.
*/

링 버퍼의 활용

링 버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있다.

예를 들면 요소의 개수가 n개인 배열에서 계속해서 데이터가 입력될 때 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버리는 용도로 사용한다.

예제
아래의 예제는 배열 a의 길이는 10이다. 인큐는 무한히 할 수 있지만, 배열에 저장되는 데이터는 가장 최근에 입력한 10개의 데이터만 링 버퍼에 남아있다.

import java.util.Scanner;
// 원하는 개수만큼 값을 입력 받아 요솟수 N인 배열에 마지막 N개를 저장

class LastNElements {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		final int N = 10;
		int[] a = new int[N];		// 입력 받은 값을 저장
		int cnt = 0;				// 입력 받은 개수
		int retry;					// 다시 한 번?

		System.out.println("정수를 입력하세요.");

		do {
			System.out.printf("%d번째 정수：", cnt + 1);
			a[cnt++ % N] = stdIn.nextInt();

			System.out.print("계속 할까요? (예.1／아니오.0）：");
			retry = stdIn.nextInt();
		} while (retry == 1);

		int i = cnt - N;
		if (i < 0) i = 0;

		for ( ; i < cnt; i++)
			System.out.printf("%2d번째의 정수 ＝ %d\n", i + 1, a[i % N]);
	}
}​

데크(deque)

deque(Double Ended Queue)는 인큐와 디큐가 배열의 양쪽 끝에서 모두 발생할 수 있는 자료구조이다.

즉, 큐의 양끝이 front이면서, rear인 형태인 것이다.

이러한 특성 때문에 데이터의 삽입과 삭제의 자유도가 높다.

Stack과 Queue의 장점만 모아서 구성한 자료구조이다.

int형 배열을 이용한 IntDeque 클래스

public class IntDeque {
	private int max; //큐 용량
	private int num; //현재 데이터 수
	private int front; //디큐를 할 인덱스를 가리킴
	private int rear; //인큐를 할 인덱스를 가리킴
	private int[] que;
	
	IntDeque(int capacity) //생성자
	{
		this.max = capacity;
		num = front = rear = 0;
		que = new int[max];
	}
	
	private boolean isEmpty() {return num <= 0;} //큐가 비어있는지를 리턴
	
	private boolean isFull() {return num >= max;} //큐의 공간이 모두 사용중인지 리턴
	
	public int capacity() {return max;} //큐의 용량을 리턴
	
	public int size() {return num;} //큐가 현재 사용중인 공간을 리턴
	
	public void clear() {num = front = rear = 0;} //큐 초기화
	
	public void enque(int value)
	{
		if(!isFull())
		{
			que[rear++] = value;
			++num;
			if(rear == max) rear = 0;
		}
		else
		{
			System.out.println("큐의 모든 공간이 사용중입니다.");
		}
		return;
	}
	
	public void enqueFront(int value)
	{
		if(!isFull())
		{
			if(--front < 0) front = max -1;
			que[front] = value;
			++num;
			if(rear == max) rear = 0;
		}
		else
		{
			System.out.println("큐의 모든 공간이 사용중입니다.");
		}
		return;
	}
	
	public void deque()
	{
		if(!isEmpty())
		{
			que[front++] = 0;
			--num;
			if(front == max) front = 0;
			return;
		}
		else
		{
			System.out.println("이미 큐가 비어있습니다.");
			return;
		}
	}
	
	public void dequeRear()
	{
		if(!isEmpty())
		{
			if(--rear < 0) rear = max -1;
			que[rear] = 0;
			--num;
			return;
		}
		else
		{
			System.out.println("이미 큐가 비어있습니다.");
			return;
		}
	}
	
	public void peek() //front를 출력
	{
		if(!isEmpty()) System.out.println(que[front]);
		else System.out.println("큐가 비어있습니다.");
	}
	
	public void peekRear() //front를 출력
	{
		if(!isEmpty())
		{
			if(rear == 0) System.out.println(que[max -1]);
			else System.out.println(que[rear -1]);
		}
		else System.out.println("큐가 비어있습니다.");
	}
	
	public void indexOf(int value) //값이 배열에 존재하는지와 몇 번째 데이터인지, 배열의 몇 번째 인덱스인지 출력
	{
		for(int i = 0; i < num; ++i)
		{
			int index = (i + front) % max;
			if(que[index] == value)
			{
				System.out.println(value + "는 큐의 " + (i+1) + "번째 데이터이고, 배열의 " + index + "인덱스에 있습니다.");
				return;
			}
		}
		System.out.println("찾는 값이 없습니다.");
	}
	
	public void dump() //큐에 저장중인 모든 데이터 출력
	{
		if(!isEmpty())
		{
			for(int i = 0; i < num; ++i)System.out.println(i+1 + "번째 데이터 : " + que[(i + front) % max]);
		}
		else System.out.println("큐가 비어있습니다.");
	}
}

실행 예제

import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("큐 용량 입력 : ");
		int command = sc.nextInt();
		IntDeque que = new IntDeque(command);
		while(true)
		{
			System.out.println();
			System.out.println("현재 데이터 수 : " + que.size() + "/" + que.capacity());
			System.out.println("(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit");
			System.out.print("cmd : ");
			command = sc.nextInt();
			if(command == 1)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				que.enque(command);
			}
			else if(command ==2)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				que.enqueFront(command);
			}
			else if(command == 3) que.deque();
			else if(command == 4) que.dequeRear();
			else if(command == 5)
			{
				System.out.print("Data for Search: ");
				command = sc.nextInt();
				que.indexOf(command);
			}
			else if(command == 6) que.peek();
			else if(command == 7) que.peekRear();
			else if(command == 8) que.dump();
			else if(command == 9) que.clear();
			else if(command == 10) System.exit(0);
			else continue;
		}
	}
}
/*
큐 용량 입력 : 5

현재 데이터 수 : 0/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 1
value : 1

현재 데이터 수 : 1/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 1
value : 2

현재 데이터 수 : 2/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 1
value : 3

현재 데이터 수 : 3/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 2
value : 5

현재 데이터 수 : 4/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 2
value : 4

현재 데이터 수 : 5/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 8
1번째 데이터 : 4
2번째 데이터 : 5
3번째 데이터 : 1
4번째 데이터 : 2
5번째 데이터 : 3

현재 데이터 수 : 5/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 5
Data for Search: 3
3는 큐의 5번째 데이터이고, 배열의 2인덱스에 있습니다.

현재 데이터 수 : 5/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 4

현재 데이터 수 : 4/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 4

현재 데이터 수 : 3/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 8
1번째 데이터 : 4
2번째 데이터 : 5
3번째 데이터 : 1
 */

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

스택

스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.

데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)이다. 스택에 데이터를 넣는 작업을 푸시라 하고, 스택에서 데이터를 꺼내는 작업을 팝이라고 한다.

이렇게 푸시와 팝을 하는 위치를 꼭대기(top)라 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다.

int 배열을 이용한 IntStack 클래스

public class IntStack {
	private int max;
	private int ptr;
	private int []stk;
	
	public IntStack(int capacity) //생성자
	{
		max = capacity;
		ptr = 0;
		stk = new int[max];
	}
	
	private boolean isFull() {return ptr >= max;} //스택이 용량이 남아있는지 리턴
	
	private boolean isEmpty() {return ptr <= 0;} //스택 비어있는지 리턴
	
	public void push(int value)
	{
		if(!isFull()) stk[ptr++] = value;
		else System.out.println("스택의 남은 용량이 없습니다.");
		
	}
	
	public void pop()
	{
		if(!isEmpty()) --ptr;
		else System.out.println("이미 스택이 비어있습니다.");
	}
	
	public void peek() //스택의 꼭대기 값을 출력
	{
		if(!isEmpty()) System.out.println(stk[ptr-1]);
		else System.out.println("스택이 비어있습니다.");
	}
	
	public void indexOf(int value) //스택에서 원하는 값을 검색
	{
		for(int i = ptr -1; i >= 0; --i) 
			{
				if(stk[i] == value)
				{
					System.out.println("찾는 값이 있습니다. 인덱스 : " + i);
					return;
				}
			}
		System.out.println("찾는 값이 없습니다.");
	}
	
	public void clear() {ptr = 0;} //ptr을 0으로 바꿔줌으로서 스택에 쌓인 데이터가 0으로 인식
	
	public int capacity() {return max;} //스택의 최대용량 리턴
	
	public int size() {return ptr;} //데이터 수를 확인 하는 메소드
	
	public void dump() //스택 안에 있는 모든 데이터를 표시하는 메소드
	{
		if(isEmpty())
		{
			System.out.println("스택이 비어있습니다.");
			return;
		}
		
		for (int i = 0; i < ptr; ++i)
		{
			System.out.println("[" + i + "]" + "=" + stk[i]);
		}
	}
	
}

실행 예제

import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("스택 용량 입력 : ");
		int command = sc.nextInt();
		IntStack stk = new IntStack(command);
		while(true)
		{
			System.out.println("현재 데이터 수 : " + stk.size() + "/" + stk.capacity());
			System.out.println("(1) push (2)pop (3)search (4)peek (5)dump (6)exit");
			System.out.print("cmd : ");
			command = sc.nextInt();
			if(command == 1)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				stk.push(command);
			}
			else if(command == 2) stk.pop();
			else if(command == 3)
			{
				System.out.print("Data for Search: ");
				command = sc.nextInt();
				stk.indexOf(command);
			}
			else if(command == 4) stk.peek();
			else if(command == 5) stk.dump();
			else if(command == 6) System.exit(0);
			else continue;
		}
	}
}

양쪽 스택

배열을 공유하여 2개의 스택을 구현하는 int형 스택 클래스를 작성

(스택에 저장하는 데이터는 int형 값으로 아래 그림처럼 배열의 처음과 끝을 사용)

IntStackX 클래스

public class IntStackX{
	private int max;
	private int Aptr;
	private int Bptr;
	private int []stk;
	
	public enum AB{A, B}; //열거 타입
	
	public IntStackX(int capacity) //생성자
	{
		max = capacity;
		stk = new int[max];
		Aptr = 0;
		Bptr = stk.length -1;
	}
	
	private boolean isFull() {return Aptr >= Bptr +1;}
		
	
	private boolean isEmpty(AB ab) {
		switch (ab)
		{
		case A:
			return Aptr <= 0;
		case B:
			return Bptr >= max-1;
		}
		return true;
	}
	
	public void push(int value, AB ab)
	{
		if(!isFull())
		{
			switch(ab)
			{
			case A:
				stk[Aptr++] = value;
				break;
			case B:
				stk[Bptr--] = value;
				break;
			}
		}
		else
		{
			System.out.println("스택이 모두 사용중입니다.");
			return;
		}
	}
	
	public void pop(AB ab)
	{
		if(!isEmpty(ab))
		{
			switch(ab)
			{
			case A:
				stk[--Aptr] = 0;
				return;
			case B:
				stk[++Bptr] = 0;
				return;
			}
		}
		else
		{
			System.out.println("스택이 이미 비어있습니다.");
			return;
		}
	}
	
	public void peek(AB ab) //스택의 꼭대기 값을 출력
	{
		if(!isEmpty(ab))
		{
			switch(ab)
			{
			case A:
				System.out.println("Top Data : " + stk[Aptr -1]);
				return;
			case B:
				System.out.println("Top Data : " + stk[Bptr +1]);
				return;
			}
		}
		else
		{
			System.out.println("스택이 이미 비어있습니다.");
			return;
		}
	}
	
	public void indexOf(int value, AB ab) //스택에서 원하는 값을 검색
	{
		switch(ab)
		{
		case A:
			for(int i = Aptr -1; i >= 0; --i)
			{
				if(stk[i] == value) System.out.println("찾는 값이 있습니다. 인덱스 : " + i);
			}
			return;
		case B:
			for(int i = Bptr +1; i < max; ++i)
			{
				if(stk[i] == value) System.out.println("찾는 값이 있습니다. 인덱스 : " + i);
			}
			return;
		}
		System.out.println("찾는 값이 없습니다.");
	}
	
	public void clear(AB ab)
	{
		switch(ab)
		{
		case A:
			Aptr = 0;
			System.out.println("A스택이 초기화 되었습니다.");
			break;
		case B:
			Bptr = max -1;
			System.out.println("B스택이 초기화 되었습니다.");
			break;
		}
	}
	
	public int capacity() {return max;} //스택의 최대용량 리턴
	
	public int size(AB ab)
	{
		switch(ab)
		{
		case A: return Aptr;
		case B: return max - Bptr -1;
		}
	return 0;
	}
	
	public void dump(AB ab) //스택 안에 있는 모든 데이터를 표시하는 메소드
	{
		if(isEmpty(ab))
		{
			System.out.println("스택이 비어있습니다.");
			return;
		}
		else
		{
			switch(ab)
			{
			case A:
				for (int i = 0; i < Aptr; ++i) System.out.println("[" + i + "]" + "=" + stk[i]);
				return;
			case B:
				for (int i = max -1; i > Bptr; --i) System.out.println("[" + i + "]" + "=" + stk[i]);
				return;
			}
		}
	}
	
}

실행 예제

import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("스택 용량 입력 : ");
		int command = sc.nextInt();
		IntStackX stk = new IntStackX(command);
		IntStackX.AB AB = IntStackX.AB.A;
		while(true)
		{
			if(AB == IntStackX.AB.A) {System.out.println("Stack A, 현재 데이터 수 : " + stk.size(AB) + "/" + (stk.capacity() - stk.size(IntStackX.AB.B)));}
			else {System.out.println("Stack B, 현재 데이터 수 : " + stk.size(AB) + "/" + (stk.capacity() - stk.size(IntStackX.AB.A)));}
			System.out.println("(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)exit");
			System.out.print("cmd : ");
			command = sc.nextInt();
			if(command == 0) AB = IntStackX.AB.B;
			else if(command == 1)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				stk.push(command, AB);
			}
			else if(command == 2) stk.pop(AB);
			else if(command == 3)
			{
				System.out.print("Data for Search: ");
				command = sc.nextInt();
				stk.indexOf(command,AB);
			}
			else if(command == 4) stk.peek(AB);
			else if(command == 5) stk.dump(AB);
			else if(command == 6) stk.clear(AB);
			else if(command == 7) System.exit(0);
			else continue;
		}
	}
}
/*
 스택 용량 입력 : 10
Stack A, 현재 데이터 수 : 0/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 1
Stack A, 현재 데이터 수 : 1/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 2
Stack A, 현재 데이터 수 : 2/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 3
Stack A, 현재 데이터 수 : 3/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 4
Stack A, 현재 데이터 수 : 4/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 5
Stack A, 현재 데이터 수 : 5/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 0
Stack B, 현재 데이터 수 : 0/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 1
Stack B, 현재 데이터 수 : 1/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 2
Stack B, 현재 데이터 수 : 2/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 3
Stack B, 현재 데이터 수 : 3/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 4
Stack B, 현재 데이터 수 : 4/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 5
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 5
[9]=1
[8]=2
[7]=3
[6]=4
[5]=5
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 6
스택이 모두 사용중입니다.
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 0
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 6
스택이 모두 사용중입니다.
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 5
[9]=1
[8]=2
[7]=3
[6]=4
[5]=5
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 3
Data for Search: 5
찾는 값이 있습니다. 인덱스 : 5
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 2
Stack B, 현재 데이터 수 : 4/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 2
Stack B, 현재 데이터 수 : 3/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 5
[9]=1
[8]=2
[7]=3
Stack B, 현재 데이터 수 : 3/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 
 */