자바 알고리즘 스터디

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

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

 

---

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 / 3 

 

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);
    }
}