Java Decorator Pattern은 객체 지향 디자인 패턴 중 하나로, 기본 기능에 추가할 수 있는 기능의 종류가 많은 경우에 각 추가 기능을 Decorator클래스로 정의 한 후 필요한 Decorator 객체를 조합함으로써 추가 기능의 조합을 설계 하는 방식이다. 

 

Decorator 패턴은 기존 객체를 감싸는 새로운 데코레이터 클래스를 만들어서 기존 객체의 메소드를 호출하는 방식으로 동작합니다.이 패턴을 사용하면 기존 객체에 새로운 기능을 추가하기 위해 상속을 사용하는 대신, 런타임 시간에 객체의 기능을 동적으로 조작할 수 있습니다. 또한 여러 개의 데코레이터를 순차적으로 적용하여 새로운 기능을 더욱 다양하게 추가할 수 있습니다.

Java Decorator Pattern의 구성요소는 다음과 같습니다.

  1. Component: Decorator 패턴의 기초가 되는 인터페이스 또는 추상 클래스. Decorator 클래스와 ConcreteComponent 클래스가 이를 구현하게 됩니다.
  2. ConcreteComponent: Component의 구현체로서, 기본적인 기능을 제공하는 클래스입니다.
  3. Decorator: Component를 상속받는 추상 클래스로, 새로운 기능을 추가하기 위한 필드와 메소드를 가지고 있습니다. 또한 Component를 상속받는 모든 데코레이터 클래스의 공통점을 정의합니다.
  4. ConcreteDecorator: Decorator를 상속받는 실제 데코레이터 클래스로, 기존 객체에 새로운 기능을 추가합니다.

이렇게 구성된 Decorator 패턴은 객체 지향의 다형성을 이용하여 기존 객체에 새로운 기능을 추가하고 확장할 수 있으며, 코드의 유연성과 확장성을 높여줍니다.

 

// Component interface
public interface Coffee {
    String getDescription();
    double cost();
}

// Concrete Component
public class BasicCoffee implements Coffee {
    @Override
    public String getDescription() {
        return "Basic coffee";
    }

    @Override
    public double cost() {
        return 2.0;
    }
}

// Decorator
public abstract class CoffeeDecorator implements Coffee {
    private Coffee decoratedCoffee;

    public CoffeeDecorator(Coffee decoratedCoffee) {
        this.decoratedCoffee = decoratedCoffee;
    }

    @Override
    public String getDescription() {
        return decoratedCoffee.getDescription();
    }

    @Override
    public double cost() {
        return decoratedCoffee.cost();
    }
}

// Concrete Decorator
public class Milk extends CoffeeDecorator {
    public Milk(Coffee decoratedCoffee) {
        super(decoratedCoffee);
    }

    @Override
    public String getDescription() {
        return super.getDescription() + ", with milk";
    }

    @Override
    public double cost() {
        return super.cost() + 0.5;
    }
}

// Concrete Decorator
public class Sugar extends CoffeeDecorator {
    public Sugar(Coffee decoratedCoffee) {
        super(decoratedCoffee);
    }

    @Override
    public String getDescription() {
        return super.getDescription() + ", with sugar";
    }

    @Override
    public double cost() {
        return super.cost() + 0.25;
    }
}

// Client code
public class CoffeeShop {
    public static void main(String[] args) {
        Coffee basicCoffee = new BasicCoffee();
        System.out.println(basicCoffee.getDescription() + ": " + basicCoffee.cost());

        Coffee milkCoffee = new Milk(basicCoffee);
        System.out.println(milkCoffee.getDescription() + ": " + milkCoffee.cost());

        Coffee sugarCoffee = new Sugar(basicCoffee);
        System.out.println(sugarCoffee.getDescription() + ": " + sugarCoffee.cost());

        Coffee milkSugarCoffee = new Milk(new Sugar(basicCoffee));
        System.out.println(milkSugarCoffee.getDescription() + ": " + milkSugarCoffee.cost());
    }
}

위 코드는 Coffee 인터페이스를 구현한 BasicCoffee 클래스와 CoffeeDecorator 추상 클래스를 정의하고, 이를 상속받아 구체적인 데코레이터 클래스인 Milk와 Sugar를 구현합니다. 각 데코레이터 클래스에서는 커피의 설명과 가격을 반환할 때 super 키워드를 이용해 기존 커피 객체의 설명과 가격을 먼저 가져오고, 이에 추가적인 설명과 가격을 더해줍니다. 마지막으로 클라이언트 코드에서는 다양한 데코레이터 객체를 조합하여 원하는 커피를 생성할 수 있습니다.

https://shlegeris.com/2016/08/14/algorithms

 

My advice on studying algorithms

Software engineering interviews often ask whiteboard algorithms questions. Here’s my advice on how to study for them. (My credentials on this topic are: I have passed a lot of whiteboard interviews, including at Google and Apple; as part of my job I prep

shlegeris.com

  •  Hash tables
  •  Linked lists
  •  Set 
  •  Map

필수 메소드의 구현 방식, 런타임에 동작 방식

  •  Breadth-first search, depth-first search
  •  Quicksort, merge sort
  •  Binary search
  •  2D arrays
  •  Dynamic arrays
  •  Binary search trees
  •  Dynamic programming
  •  Big-O analysis

 

etc

  •  HTTP (at the protocol level)
  •  Databases (indexes, query planning)
  •  CDNs
  •  Caching (LRU cache, memcached, redis)
  •  Load balancers
  •  Distributed worker systems

 

  • 그래프 알고리즘: 너비 우선 탐색(breadth first search), 깊이 우선 탐색(depth first search), 다익스트라 알고리즘 (dikstra’s algorithm)
  • 빠른 정렬 알고리즘 하나. 병합 정렬(mergesort) 또는 퀵 정렬(quicksort)
  • 배열에서 수행하는 이진 검색. 이 알고리즘은 제대로 작성하기 매우 까다롭고 대략적으로 알고리즘을 이해하고 있더라도 코드로 작성해볼 가치가 있습니다.

 

 

-

https://edykim.com/ko/post/advice-on-learning-algorithms/

  • Comparable과 Comparator 인터페이스의 차이는?
    • Comparable 인터페이스는 자연스러운 순서로 정렬할 때 사용하고. Comparator는 원하는 대로 정렬 순서를 지정한다.
    • Array와 Collection 클래스는 몇 가지 오버로딩된 정렬 메서드가 있다. 
      • 배열을 받는 메서드
      • 배열과 Comparator 객체를 받는 메서드 
    • 지정한 순서대로 정렬하고 싶으면 sort 메서드에서 사용할 Comparator 인터페이스를 구현한 후 이를 제공해야 한다.
      • Comparator를 인터페이스를 구현한 ReverseNumericalOrder 클래스가 있다고 치자.
        • 이 클래스는 compare 메소드를 오버라이드 한 것
      • 이것을 Collections.sort(number, new ReverseNumbericalOrder()); 이렇게 전달하면 원하는 순서대로 정렬이 되는 것을 볼 수 있다. 

 

 

  • 버블 정렬 알고리즘
    • 순환할 때 마다 하나의 원소만 변경한다. 
    • 최선의 경우는 이미 정렬되어 잇을 때
    • 최악의 경우는 역순으로 정렬되어 있을 떄 
    • O(n^2)
  • 삽입 정렬 알고리즘 
    • 정렬된 원소들을 새로운 리스트에 담아서 반환 (버블 정렬과 다른 점)
    • LinkedList를 사용하며 반환할 리스트가 구성되면 즉시 반환할 수 있다. 
    • 최악의 경우는 이미 정렬되어 있을 때고, 이때는 O(n^2)
    • 최선의 경우는 역순으로 정렬되어 있을 때고, 이때는 O(n)
  • 버블vs삽입
    • 삽입 정렬 알고리즘은 새로운 리스트를 반환해야 하므로 정렬하려는 리스트의 두배 정도 되는 저장 공간이 필요하다. 
    • 버블 정렬은 스왑할 때 사용하는 임시 변수용으로 사용할 여분의 메모리 슬롯 하나만 더 있으면 된다.
    • 따라서, (나의 의견)
      • 어느 정도 정렬된 아주 큰 배열은 버블정렬
      • 전혀 정렬되지 않았고 그다지 크지 않은 배열의 경우에는 삽입정렬
  • 퀵 정렬 알고리즘
    • 재귀적인 알고리즘으로 버블과 삽입 보다 훨씬 더 효율적이고 성능이 ㅇ좋음
    • 원소들을 두 개의 리스트로 분리하는 시간 복잡도는 O(n)이고, 각각의 재귀 호출은 각 리스트 숫자의 절반만큼의 횟수만 발생
    • 복잡도는 O(n logn)
    • 최악의 경우는 pivot (get(0)으로 무작위로 선택한 기준)을 선태갛는 기준에 있는데 리스트가 역순으로 정렬되어 있을 때
  • 병합 정렬 알고리즘
    • 분할정복 알고리즘
    • 리스트를 두 개로 나누고 각 하위 리스트를 정렬한 후 각각 하나로 합친다
    • 병합 정렬의 성능은 O(n logn)이고 각각의 병합시간은 O(n)이며 각 재귀 호출은 주어진 리스트 숫자의 절반 만큼만 발생

분할정복 알고리즘으로 리스트를 두 개로 나누고 각 하위 리스트를 정렬한 후 각각을 하나로 합친다. 

  @Test
    public void mergeSortTest() {
        // divide-and-conquer 알고리즘
        // 리스트를 두 개로 나누고 각 하위 리스트를 정렬한 후 각각을 하나로 합친다.
        // 병합정렬 성능은 O(nlogn), 각각의 병합시간이 O(n)이다.
        // 왼쪽으로 나눈 리스트를 정렬하고 -> 오른쪽으로 나눈 리스트를 정렬한다.

        List<Integer> values = Arrays.asList(7,1,3,2,3,9,2,5);
        List<Integer> sorted = divide(values);
        System.out.println(sorted);
    }

    public List<Integer> divide(final List<Integer> values) {
        if (values.size() < 2) {
            return values;
        }

        int listSize = values.size();

        final List<Integer> leftHalf = values.subList(0, listSize / 2);
        final List<Integer> rightHalf = values.subList(listSize / 2, listSize);

        System.out.println("-- dividing..leftHalf : " + leftHalf + " , rightHalf : " + rightHalf);

        return conquer(divide(leftHalf), divide(rightHalf));
    }

    private List<Integer> conquer(final List<Integer> left, final List<Integer> right) {
        System.out.println("## merging.. leftHalf : " + left + " , rightHalf : " + right);
        int leftPtr = 0;
        int rightPtr = 0;

        final List<Integer> merged = new ArrayList<>(left.size() + right.size());

        int leftSize = left.size();
        int rightSize = right.size();

        while (leftPtr < leftSize && rightPtr < rightSize) {
            if (left.get(leftPtr) < right.get(rightPtr)) {
                merged.add(left.get(leftPtr));
                leftPtr++;
            } else {
                merged.add(right.get(rightPtr));
                rightPtr++;
            }
        }

        while (leftPtr < leftSize) {
            merged.add(left.get(leftPtr));
            leftPtr++;
        }

        while (rightPtr < rightSize) {
            merged.add(right.get(rightPtr));
            rightPtr++;
        }

        System.out.println("## merged : " + merged);

        return merged;
    }
-- dividing..leftHalf : [7, 1, 3, 2] , rightHalf : [3, 9, 2, 5]
-- dividing..leftHalf : [7, 1] , rightHalf : [3, 2]
-- dividing..leftHalf : [7] , rightHalf : [1]
## merging.. leftHalf : [7] , rightHalf : [1]
## merged : [1, 7]
-- dividing..leftHalf : [3] , rightHalf : [2]
## merging.. leftHalf : [3] , rightHalf : [2]
## merged : [2, 3]
## merging.. leftHalf : [1, 7] , rightHalf : [2, 3]
## merged : [1, 2, 3, 7]
-- dividing..leftHalf : [3, 9] , rightHalf : [2, 5]
-- dividing..leftHalf : [3] , rightHalf : [9]
## merging.. leftHalf : [3] , rightHalf : [9]
## merged : [3, 9]
-- dividing..leftHalf : [2] , rightHalf : [5]
## merging.. leftHalf : [2] , rightHalf : [5]
## merged : [2, 5]
## merging.. leftHalf : [3, 9] , rightHalf : [2, 5]
## merged : [2, 3, 5, 9]
## merging.. leftHalf : [1, 2, 3, 7] , rightHalf : [2, 3, 5, 9]
## merged : [1, 2, 2, 3, 3, 5, 7, 9]
[1, 2, 2, 3, 3, 5, 7, 9]

 

병합정렬의 성능은 O(nlogn)이고 각각의 병합시간은 O(n)이며 각 재귀 호출은 주어진 리스트 숫자의 절반만큼만 발생한다는 사실을 다시 한번 기억하자.

출처 : JAVA 프로그래밍 면접 이렇게 준비한다

'알고리즘과 디자인패턴' 카테고리의 다른 글

Java Decorator Pattern 설명과 예시  (0) 2023.03.09
알고리즘 관련 to know list  (0) 2022.03.29
리스트 정렬하기  (0) 2022.01.23
자바 알고리즘 스터디  (0) 2021.08.11

알고리즘 강의를 통해 해당 문제에서 짚고 넘어가야 할 포인트를 정리하는 위주로 써내려 가겠다. 

그 포인트는 나만의 기준으로, 평소에 잘 몰랐거나 효율적으로 잘 쓰지 못했던 부분이 될 것이다. 

 


String 

문제 1 ) 영어 알파벳과 특수문자로 구성된 문자열이 주어지면 영어 알파벳만 뒤집고,

특수문자는 자기 자리에 그대로 있는 문자열을 만들어 출력하는 프로그램을 작성하세요.

a#b!GE*T@S   ->    S#T!EG*b@a

 

String -> .toCharArray()를 이용해 char 배열로 변경해주고, 

for문이 아닌 index를 이용해 문자들을 교체해준다. (left++ / right --)

-> 나는 처음에 for문으로 해결하려 했다 

 

Character.isAlphabetic(xxx) 을 이용하면 알파벳인지 아닌지 확인이 가능하다.

left와 right은 인덱스 위치를 표시하는 건데 왼쪽에서 읽어들이는 인덱스가 오른쪽에서 줄어드는 인덱스를 초과하지 않을 때 까지 체크를 하는 방식을 취한다. 

=> while (left < rifht) { } 


Stack & Queue


개념정리

  • Stack : Last In First Out (LIFO)
    • 메소드
      • public Element push(Element item); // 스택에 데이터 추가
      • public Element pop(); // 최상단 데이터 삭제
      • public Element peek(); // 최상단 데이터 조회
      • public boolean empty(); // 스택에 데이터 있는지 확인
      • public int seach(Object o); // 인자값으로 전달받은 데이터 위치 확인
    • 구현방법
      • LInkedList 이용
public class Node {
    private int data;
    private Node nextNode;

    public Node (int data) {
        this.data = data;
        this.nextNode = null;
    }

    protected void linkNode(Node node) {
        this.nextNode = node;
    }

    protected int getData() {
        return this.data;
    }

    protected Node getPreviousNode() {
        return this.nextNode;
    }
}

/////////////////////////////////////////////////////////////////////////////////////////

public class LinkedListStack {

    Node top;

    public LinkedListStack() {
        this.top = null;
    }

    private void push(int data) {
        Node node = new Node(data);
        node.linkNode(top);
        top = node;
    }

    public int peek() {
        return top.getData();
    }

    private void pop() {
        if (top == null) {
            throw new ArrayIndexOutOfBoundsException("Stack is empty");
        } else {
            top = top.getPreviousNode();
        }
    }

    private int search (int item) {
        Node searchNode = top;
        int index = 1;
        while(true) {
            if (searchNode.getData() == item) {
                return index;
            } else {
                searchNode = searchNode.getPreviousNode();
                index ++;
                if (searchNode == null) {
                    break;
                }
            }
        }
        return -1;
    }
}
      • Array vs LinkedList 비교
        • Array는 데이터 접근 속도가 빠르지만 최대 개수를 항상 정해놔야 하는 단점이 있음
        • 최대 개수 정해놓지 않아도 되지만 데이터의 조회가 힘듬 (노드를 따라 가야되기 때문)
  • Queue : First In First Out (FIFO)
    • 메소드 
      • boolean add(T data) // 큐에 추가 
      • Object remove() // 객체 꺼내서 반환
      • Object element() // 삭제 없이 데이터 읽기
      • boolean offer(Object o) // Queue에 객체를 저장 
      • Object poll() // Queue에서 객체를 꺼내서 반환
      • Object peek() // 삭제없이 요소를 읽어옴 

문제 1 ) 괄호가 입력되면 올바른 괄호이면 'YES', 아니면 'NO'를 출력합니다.

(( )(( )))(( ) -> NO

(())() -> YES

 

스택을 이용하는 문제 

'('가 들어오면 push, ')'가 나오면 pop을 한다. 

전부 다 스택에 넣는 것이 아니라 ( 만 스택에 쌓는다. 

 

Stack<Character> stack = new Stack<>();
for (char x : str.toCharArray()) { 
	if (x == 'C') { 
    	stack.push(x);
    } else { 
    	if (stack.isEmpty()) {
        	System.out.println("NO"); 
        } 
        stack.pop();
    }
}

if (!stack.isEmpty()) {
	System.out.println("NO");
} 

System.out.println("YES");

 


문제 2 ) 인형뽑기 

NXN 배열에 있는 인형들을 바구니에 위로 쌓는다. 이때 같은 인형이 바구니에 쌓이면 인형이 터뜨려지게 된다. M사이즈의 배열에는 어떤 NXN 배열에서 어떤 '열'로 이동하는지 정보가 있다고 가정했을 때 이동이 끝나서 터뜨려지는 인형의 개수를 구하라.

 

5 (N)
0 0 0 0 0
0 0 1 0 3
0 2 5 0 1
4 2 4 4 2
3 5 1 3 1  -> NxN 배열이고 0은 인형이 없고 비어있는 개수라고 생각하면 된다.
8 (M)
1 5 3 5 1 2 1 4 (열을 어떤 순서로 이동할지 정보가 담겨있는 M사이즈의 배열)

 

이것도 마찬가지로 스택을 이용하는 문제이고, .peek()메소드를 이용해 맨 상단의 수를 체크해서 같지 않은 경우엔 .push() 같으면 .pop()을 시킨다. 다차원 배열도 같이 잘 다뤄줘야 하는데 int[N][N] box = new int[][]; 라고 가정하면 box.length는 행의 개수, box[3].length 이렇게 하면 열의 개수를 알 수 있다. 

 


DFS

개념정리

  • 전위순회 : 부모 - 왼 - 오 (0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6)
  • 중위순회 : 왼 - 부모 - 오 (3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6)
  • 후위순회 : 왼 - 오 - 부모 (3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0)

 

class Node {
    int data;
    Node lt;
    Node rt;
    
    public Node (int data) {
    	this.data = data;
        lt=rt=null;
    }
}
public class Main {
    Node root;
    public void DFS(Node root) {
    	if (root == null) return;
        else {
            // System.out.println(root.data + " "); // 전위순회
            DFS(root.lt); // 왼쪽으로
            // System.out.println(root.data + " "); // 중위순회
            DFS(root.rt); // 오른쪽으로
            // System.out.println(root.data + " "); // 후위순회
        }
    }
    
    public static void main(String args[]) {
    Main tree = new Main();
    tree.root = new Node(1);
    tree.root.lt = new Node(2);
    tree.root.rt = new Node(3);
    tree.root.lt.lt = new Node(4);
    tree.root.lt.rt = new Node(5);
    tree.root.rt.lt = new Node(6);
    tree.root.rt.rt = new Node(7);
    tree.DFS(tree.root);
}

문제 1 ) 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성 (공집합 제외)

3 -> 1,2,3 / 1,2 / 1,3 / 1 / 2,3 / 2 / 

 

1,2,3 에서 각 자연수는 집합에 들어갈 수 있다/없다 (LT / RT) 두가지 경우의수를 가진다. 

 

class Main {
    static int n;
    static int[] ch;
    
    public void DFS(int L) {
    	if (L == n+1) {
        	// 1로 표시된 인덱스를 표시해준다.
            String tmp = "";
            for (int i = 1; i <= n ; i++) {
            	if (ch[i] == 1) tmp += (i + " ");
            }
            if (tmp.length() > 0) {
            	System.out.println(tmp);
            }
        } else { 
            ch[L] = 1;
            DFS(L+1) // 사용한다 (왼쪽)
            ch[L] = 0; 
            DFS(L+1) // 사용하지 않는다 (오른쪽)
        }
    }

    public static void main(String[] args) {
    	Main T = new Main();
        n = 3;
        ch = new int[n+1];
        T.DFS(1);
    }
}

+ Recent posts