알고리즘 강의를 통해 해당 문제에서 짚고 넘어가야 할 포인트를 정리하는 위주로 써내려 가겠다.
그 포인트는 나만의 기준으로, 평소에 잘 몰랐거나 효율적으로 잘 쓰지 못했던 부분이 될 것이다.
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는 데이터 접근 속도가 빠르지만 최대 개수를 항상 정해놔야 하는 단점이 있음
- 최대 개수 정해놓지 않아도 되지만 데이터의 조회가 힘듬 (노드를 따라 가야되기 때문)
- Array vs LinkedList 비교
-
- 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);
}
}'알고리즘과 디자인패턴' 카테고리의 다른 글
| Java Decorator Pattern 설명과 예시 (0) | 2023.03.09 |
|---|---|
| 알고리즘 관련 to know list (0) | 2022.03.29 |
| 리스트 정렬하기 (0) | 2022.01.23 |
| 자바로 구현한 병합 정렬 알고리즘 (merge sort) (0) | 2021.12.07 |
