21.08.09 자료구조와 알고리즘

알고리즘 스터디 (1)

스택 / 큐

참고한 Velog

스택

Stack이란?
Stack은 쌓다라는 의미를 가지고 있으며 프로그래밍에서는 목록 혹은 리스트에서 접근이 한 쪽에서만 가능한 구조를 말한다. LIFO가 원칙

스택의 구조
Book이라는 목록이 [Book1,Book2,Book3] 로 이루어져있는데 여기서 Push를 통해 Book4가 맨 끝(위)에 추가되며 Peek을 통해서 맨끝(위)에 있는 Book4를 지정하게 된다. 만약 맨위의 자료를 뺀다면 Pop을 통해서 Book4가 제거된다.

자바에서는 원래 Stack 클래스를 기본으로 제공한다.
기본적으로 Java의 Stack클래스는

Stack<Element> stack = new Stack<>();

와 같이 생성이 가능하다. 그리고 Stack 클래스는 기본적으로

push(Element Item) // 데이터 추가
pop() // 최근에 추가된 데이터 삭제
peek() // 최근에 추가된 데이터 조회
empty() // stack의 값이 비었는지 확인, 비었으면 True 아니면 false
seach(Obejct o) // 인자값으로 받은 데이터의 위치를 반환.

5개의 메소드를 지원한다.
만약 stack을 직접 만들게 된다면 배열 또는 연결리스트로 만들수 있는데 배열로 만든다면 조회가 빠른대신 배열로 만드는만큼 최대 갯수를 지정해야만 사용이 가능하다.
연결리스트로 만든다면 최대 개수가 정해져 있지 않기에 삽입 삭제가 용이하다 하지만 속도가 느리다
Stack의 특성상 마지막 데이터를 쉽게 빼낼 수 있어 마지막 기록, 최근 기록등등을 저장할 경우만 사용한다. 그렇기에 조회속도가 느린 연결리스트는 실질적으로 단점이 아니기에 스택구현시 연결리스트로 구현하는것을 선호한다.

큐

Queue란?
Queue는 Stack과 마찬가지로 입력과 출력이 한 방향으로만 이루어지는 선형 자료형이다. 자료의 데이터를 입력하는 enqueue와 자료의 데이터를 추출하는 dequeue가 있다(Stack과 마찬가지로 pop,peek,empty가 존재) Queue는 입력한 데이터 순서대로 출력(FIFO)이 된다.
흔히 대기줄을 생각하면 편하다.

큐의 구조
Book이라는 목록이 [Book3,Book2,Book1] 로 이루어져있는데 여기서 Push를 통해 Book4가 맨 처음(아래)에 [Book4,Book3,Book2,Book1] 추가되며 Peek을 통해서 맨 처음(아래)에 있는 Book4를 지정하게 된다. 만약 맨 처음(아래)의 자료를 뺀다면 Pop을 통해서 Book1가 제거된다.

스택/큐 알고리즘 문제 풀기

1. 주식가격

스택과 큐를 활용하는 문제지만 기본 배열로만으로도 풀수있을거라 생각해서 배열로 해결했다.

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
price [1, 2, 3, 2, 3]
return [4, 3, 1, 1, 0]

순차탐색으로 한개의 배열을 이중반복을 돌려 탐색을했다.
만약 i의 값보다 j의값이 작다면 (J는 0 + i이다.) 그 이후의 값은 볼 필요가 없으므로
같은 배열의 크기를가진 answer[] 배열에 찾은 인덱스(j)와 기준점(i) 만큼 뺀 값을 넣는다.
그렇지 않다면 기준점(i)보다 작은값이 없으므로 (기준점에서 주식이 떨어진적이 없다) answer[]배열에 주식가격 배열의 크기에서 기준점만큼 뺀값을 추가한다.
아래는 위의 코드이다.

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];

        for(int i = 0; i < prices.length; i++){
            for (int j = 0 + i; j < prices.length; j++){
                if(prices[i] > prices[j]){
                    answer[i] = j-i;
                    break;
                } else {
                    answer[i] = (prices.length-1) - i;
                }
            }
        }
        return answer;
    }
}