Coffee And Coding

- 문제 : https://www.acmicpc.net/problem/1260

- 분류 : DFS, BFS

- 풀이

• BFS (너비우선탐색)
  • 가까운 정점을 먼저 방문하는 구조이기 때문에, 가까운 정점을 저장해두고 순서대로 방문할 수 있도록 선입선출 구조인 Queue를 사용한다.

• DFS (깊이우선탐색) 
  • 재귀 또는 스택을 사용해서 자기자신을 호출하는 순환 알고리즘 형태를 띈다.
  • 일단 한방향으로 갈 수 있는 데까지 깊이있게 파고든 다음에 다음으로 이동하는 방식.

import java.util.*;


class Node {
    int number; //정점 번호는 1번부터 N번까지
    LinkedList<Node> adjacent;
    boolean visited;
    
    public Node(int number) {
        this.number = number;
        this.visited = false;
        this.adjacent = new LinkedList<Node>();
    }
    
}

class Graph {
    Node[] nodes;
    
    public Graph(int nodeCount) {
        this.nodes = new Node[nodeCount];
        for(int i = 0; i<nodeCount; i++) {
            this.nodes[i] = new Node(i+1);
        }
    }
    
     public void addEdge(int a, int b) {
        Node aNode = this.nodes[a-1];
        Node bNode = this.nodes[b-1];
        
        if(!aNode.adjacent.contains(bNode)) {
            aNode.adjacent.add(bNode);
            // 여러개일 경우 작은 정점 먼저 방문하도록 정렬
            Collections.sort(aNode.adjacent, new Comparator<Node>() {
               @Override
               public int compare(Node a, Node b) {
                   return a.number > b.number ? 1: -1;
               }
            });
            
        }
        
        if(!bNode.adjacent.contains(aNode)) {
            bNode.adjacent.add(aNode);
            // 여러개일 경우 작은 정점 먼저 방문하도록 정렬
            Collections.sort(bNode.adjacent, new Comparator<Node>() {
               @Override
               public int compare(Node a, Node b) {
                   return a.number > b.number ? 1: -1;
               }
            });
        }
        
        
    }
    
    public void dfs(int v) {
        Node vNode = this.nodes[v-1];
        System.out.print(vNode.number + " ");
        vNode.visited = true;
        
        for(Node node: vNode.adjacent) {
            if(node.visited == false) {
                dfs(node.number);
            }
        }
    }

    public void bfs(int v) {
        Queue<Node> q = new LinkedList<Node>();
        Node vNode = this.nodes[v-1];
        q.add(vNode);
        vNode.visited = true;
      
        while(!q.isEmpty()){
            Node toVisit = q.peek();
            q.poll();
            System.out.print(toVisit.number + " ");
            
            if(!toVisit.adjacent.isEmpty()) {
                for(Node node : toVisit.adjacent) {
                    if(!node.visited) {
                        q.add(node);
                        node.visited = true;
                    }
                }
            } 
        }
    }
    
    //방문기록 초기화
    public void clearVisited() {
        for(Node node : this.nodes) {
            node.visited = false;
        }
    }

    
}



public class Main
{
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    
	    int nodeCount = sc.nextInt();
	    int edgeCount = sc.nextInt();
	    int v = sc.nextInt(); //startNode
	    
	    Graph g = new Graph(nodeCount);
	    
	    for(int i = 0; i<edgeCount; i++) {
	        int a = sc.nextInt();
	        int b = sc.nextInt();
	        
	        g.addEdge(a,b);
	    }
	    
	    g.dfs(v);
	   g.clearVisited();
	    System.out.println();
	    g.bfs(v);
	
	}
}

문제 : https://www.acmicpc.net/problem/18258

풀이

문제 자체는 쉽다. Queue에 대한 기본 개념만 있으면 쉽게 구현할 수 있다.

다만 계속 '시간초과'가 떠서 이를 해결하는 데 초점을 맞춰야 한다.

시간초과를 해결하기 위해서는 아래 방법들이 있다.

1. 시간이 오래 걸리는 Scanner나 System.out.print() 대신 => BufferedReader, BufferedWriter를 사용한다

• 입력된 데이터를 바로 전달되지 않고 buffer에 모았다가 한번에 전달하므로 데이터 처리 효율성을 높인다. 다만 입력받은 데이터를 전부 String타입으로 고정하기 때문에 다른 타입으로 변환하는 가공 작업이 필요하다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());

2. StringBuilder를 사용해서 output을 한번에 출력한다

코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Queue{
	
	StringBuilder sb = new StringBuilder();
	LinkedList<Integer> list = new LinkedList<Integer>();

	public void push(int x) {
		list.add(x);
	}
	
	public void pop() throws IOException {
		//가장 앞에 있는 정수를 빼고 그 수를 출력한다
		//만일 큐에 들어있는 정수가 없으면 -1 출력
		sb.append(list.isEmpty()? "-1": list.poll());
		sb.append("\n");
    }
	
	public void size() throws IOException {
		//큐에 들어있는 정수의 개수를 출력한다
		sb.append(list.size() + "\n");
		
	}
	
	public void empty() throws IOException {
		//큐가 비어있으면 1, 아니면 0 출력
		sb.append(list.isEmpty()?"1":"0");
		sb.append("\n");
	}
    
	public void front() throws IOException {
		//가장 앞에 있는 정수를 출력
		//만약 큐에 들어있는 정수가 없으면 -1 출력
		sb.append(list.isEmpty() ? "-1" : list.getFirst());
		sb.append("\n");
		
	}
	public void back() throws IOException {
		//가장 뒤에 있는 정수를 출력
		//만약 큐에 들어있는 정수가 없는 경우 -1 출력
		sb.append(list.isEmpty()? "-1" : list.getLast());
		sb.append("\n");
	
	}
    
    public void print() {
        System.out.print(sb);
    }
}
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Queue q = new Queue();
		String command[] = new String[n];
		
		for(int i = 0; i<n; i++) {
			command[i] = br.readLine();
		}
		
		for(int i = 0; i<n; i++) {
			String tmp = command[i];
		
			switch(tmp) {
			case "front":
				q.front();
				break;
			case "pop":
				q.pop();
				break;
			case "size":
				q.size();
				break;
			case "empty":
				q.empty();
				break;
			case "back":
				q.back();
				break;
			default:
				String sx = tmp.substring(5);
				int x = Integer.parseInt(sx);
				q.push(x);
			}
		}
       
        q.print();
        br.close();
	}
}

참고자료

https://docs.oracle.com/javase/8/docs/api/java/io/BufferedReader.html

https://jhnyang.tistory.com/92

https://yeon-kr.tistory.com/152

https://www.acmicpc.net/problem/2164

- 분류 : Queue

아주 간단한 문제이다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		Queue<Integer> q = new LinkedList();
		for(int i = 0; i<n ; i++) {
		    q.add(i+1);
		}
		
		while(q.size() > 1) {
		    q.remove();
		    int head = q.poll();
		    q.add(head);
		}
		
		System.out.println(q.poll());
		
	}
}

- 문제 :

https://www.acmicpc.net/problem/2630

- 분류 : 분할정복 알고리즘

기본적인 분할정복 알고리즘 문제이다.

첨에 2차원 배열을 어떻게 사분할로 쪼개지? 에서 조금 생각을 했는데 결국은 시작점을 상하좌우로 이동시켜서 생각하면 된다. 예를 들면 이렇다.

  //같은 색이 아니라면 1/4로 쪼갠다
int divide = n/2;

int [][] arr1 = new int[divide][divide];
int [][] arr2 = new int[divide][divide];
int [][] arr3 = new int[divide][divide];
int [][] arr4 = new int[divide][divide];


for(int i = 0; i<divide; i++) {
   for(int j = 0; j<divide; j++) {
       arr1[i][j] = arr[i][j];
       arr2[i][j] = arr[i+divide][j];
       arr3[i][j] = arr[i][j+divide];
       arr4[i][j] = arr[i+divide][j+divide];
   }
}

풀이

첨에 arr 배열 전체를 넘겨주는 방식으로 풀었는데 다른 사람들의 풀이를 보니 arr[][]을 static으로 두고, index만 넘겨서 푸는 방식으로 풀었길래 나도 그와 같은 방식으로 다시 풀어보았다. 

분할정복 알고리즘은 문제를 작은 방식으로 분할하여 해결하는 방식으로, 

이 문제는 "전체 종이 색깔이 같지 않으면 계속 쪼개는(divide)" 방식으로 해결한다. 전체 종이 색깔이 같아질 때 conquer된다.

첫번째 풀이

import java.util.*;

public class Main
{
    static int white = 0;
	static int blue = 0; 
	
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	  
	    int n = sc.nextInt();
	    int arr[][] = new int[n][n];
	    
	    for(int i = 0; i<n; i++) {
	        for(int j = 0; j<n; j++) {
	            arr[i][j] = sc.nextInt();
	        }
	        sc.nextLine();
	    }
	   
	    quad(arr);
	    
	    System.out.println(white);
	    System.out.println(blue);
	}
	
	 static void quad(int[][] arr) {
	    int n = arr[0].length;
	    
	    //전체가 같은 색이면 컬러 체크
	    if(n == 1 || isAllColorSame(arr)) {
	        checkColor(arr[0][0]);
	        return;
	    }
	   
        //같은 색이 아니라면 1/4로 쪼갠다
	    int divide = n/2;
	    
        int [][] arr1 = new int[divide][divide];
        int [][] arr2 = new int[divide][divide];
        int [][] arr3 = new int[divide][divide];
        int [][] arr4 = new int[divide][divide];
        
      
	    for(int i = 0; i<divide; i++) {
	       for(int j = 0; j<divide; j++) {
	           arr1[i][j] = arr[i][j];
	           arr2[i][j] = arr[i+divide][j];
	           arr3[i][j] = arr[i][j+divide];
	           arr4[i][j] = arr[i+divide][j+divide];
	       }
	    }
	    
	    quad(arr1);
	    quad(arr2);
	    quad(arr3);
	    quad(arr4);
	}
	
	
	 static boolean isAllColorSame(int[][] arr) {
	    int color = arr[0][0];
	    int n = arr[0].length;
	    
	    //전체가 같은 색인지 체크한다
	    for(int i = 0; i<n; i++) {
	        for(int j = 0; j<n; j++) {
	           if(color != arr[i][j]) {
	               return false;
	           }
	        }
	    }
	    return true;
	}
	
	static void checkColor(int color) {
       if(color == 0) {
            white++;
        } else {
            blue++;
        }
	}
}

두번째 풀이

import java.util.*;

public class Main
{
    static int white = 0;
	static int blue = 0; 
	static int arr[][];
	
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	  
	    int n = sc.nextInt();
	    arr = new int[n][n];
	    
	    for(int i = 0; i<n; i++) {
	        for(int j = 0; j<n; j++) {
	            arr[i][j] = sc.nextInt();
	        }
	        sc.nextLine();
	    }
	   
	    quad(n, 0, 0);
	    
	    System.out.println(white);
	    System.out.println(blue);
	}
	
	 static void quad(int n, int row, int column) {
	    
	    // 1. 전체가 같은 색이면 컬러 체크
	    if(n == 1 || isAllColorSame(n, row, column)) {
	        checkColor(arr[row][column]);
	        return;
	    }
	   
        // 2. 같은 색이 아니라면 1/4로 쪼갠다
	   int divide = n/2;
	    
       quad(divide, row, column);
       quad(divide, row+divide, column);
       quad(divide, row, column+divide);
       quad(divide, row+divide, column+divide);
	}
	
	
	//전체가 같은 색인지 체크
	 static boolean isAllColorSame(int n, int row, int column) {
	   int color = arr[row][column];
	   
	    for(int i = row; i<n+row; i++) {
	        for(int j = column; j<n+column; j++) {
	           if(color != arr[i][j]) {
	               return false;
	           }
	        }
	    }
	    return true;
	}
	
	static void checkColor(int color) {
       if(color == 0) {
            white++;
        } else {
            blue++;
        }
	}
}

딱 기본적인 stack을 활용한 문제이다.

• 문제 : https://www.acmicpc.net/problem/4949

<풀이>

• 괄호를 만나면 stack에 넣는다.
• 오른쪽 괄호의 경우 stack의 top에 있는 괄호와 짝을 이룰 경우 stack에 넣지 않고 stack에 들어있는 왼쪽 괄호를 pop한다.

• 최종적으로 stack이 비어있으면 yes를 출력한다.

아래는 java에서 제공하는 Stack을 사용한 풀이이다.

import java.util.Stack;
import java.util.Scanner;

public class BOJ4949 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (true) {
            String str = sc.nextLine();
            Stack<Character> stack = new Stack<>();

            if (str.equals("."))
                break;

            for (int i = 0; i < str.length(); i++) {
								// 괄호를 만났을때 
                if (str.charAt(i) == '[' || str.charAt(i) == ']' || str.charAt(i) == '(' || str.charAt(i) == ')') {
										// 넣으려는 괄호가 오른쪽 괄호일 경우는 stack에 왼쪽괄호가 top에 존재할때 stack에서 왼쪽 괄호를 빼낸다
                    if ((!stack.empty() && stack.peek() == '[' && str.charAt(i) == ']') || (!stack.empty() && stack.peek() == '(' && str.charAt(i) == ')')) {
                        stack.pop();
                    } else {
												// 괄호는 스택에 저장한다
                        stack.push(str.charAt(i));
                    }
                }
            }
            System.out.println(stack.isEmpty() ? "yes" : "no");
        }
    }
}

아래는 ArrayList를 이용해서 직접 Stack을 구현해서 푼 풀이이다.

import java.util.*;

/*
백준 4949번 균형잡힌 세상
분류 : stack
직접 스택 구현해서 풀기
* */


public class BOJ4949_2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (true) {
            String str = scanner.nextLine();
            Stack stack = new Stack();
            if (str.equals("."))
                break;

            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '[' || str.charAt(i) == ']' || str.charAt(i) == '(' || str.charAt(i) == ')') {
                    if ((!stack.isEmpty() && stack.peek() == '[' && str.charAt(i) == ']') || (!stack.isEmpty() && stack.peek() == '(' && str.charAt(i) == ')')) {
                        stack.pop();
                    } else {
                        stack.push(str.charAt(i));
                    }
                }
            }
            System.out.println(stack.isEmpty() ? "yes" : "no");
        }
    }

    private static class Stack {
        private List<Character> elements;
        private int elementSize;

        public Stack() {
            this.elements = new ArrayList<>();
            this.elementSize = 0;
        }

        public void push(char element) {
            elements.add(element);
            elementSize++;
        }

        public void pop() {
            if (isEmpty()) {
                throw new EmptyStackException();
            }

            elements.remove(elementSize - 1);
            elementSize--;
        }

        public char peek() {
            if (isEmpty()) {
                throw new EmptyStackException();
            }

            return elements.get(elementSize - 1);
        }

        public boolean isEmpty() {
            if (elementSize == 0) {
                return true;
            }
            return false;
        }


    }
}

• 분류 : DP
• 문제 : https://www.acmicpc.net/problem/9095

풀이

• n은 양수이며 11미만이다. 그러므로 DP테이블의 사이즈를 11로 하였다. (인덱스0은 비워둠)
• n이 4일때를 계산해보면 쉽게 점화식을 구할 수 있다.
  • n=1 → 1
  • n=2 → 2 (1+1, 2)
  • n=3 → 4 (2+1, 1+2, 1+1+1, 3)
  • n=4 → 7 (1+1+1+1, 2+2, 2+1+1, 1+2+1, 1+1+2, 3+1, 1+3)

import java.util.Scanner;

/*
* 분류 : DP
* */
public class BOJ9095 {
    static int[] table = new int[11];

    public static void main(String[] args) {
        table[1] = 1;
        table[2] = 2; // 1+1, 2
        table[3] = 4; // 2+1, 1+2, 1+1+1, 3
//        table[4] = 7; // 1+1+1+1, 2+2, 2+1+1, 1+2+1, 1+1+2, 3+1, 1+3

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nn = new int[n];
        for (int i = 0; i < n; i++) {
            nn[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i++) {
            System.out.println(recur(nn[i]));
        }
    }

    public static int recur(int n) {
        if (n < 4 || table[n] > 0) {
            return table[n];
        }

        return table[n] = recur(n - 1) + recur(n - 2) + recur(n - 3);
    }
}

• 관리자권한으로 cmd창 실행

덤프 뜨기 전에 DB에 접근해서 덤프 뜰 DB명을 확인한다.

mysql -u [사용자] -p

show databases;
show tables;

DB명을 확인한 후에 mysql에서 나간 다음에 아래 mysqldump 명령어로 DB를 덤프뜬다.

mysqldump -u [계정] --host=[host] --port=3306 -p [데이터베이스명] > [파일명].sql

아래에 덤프 뜬 sql파일이 생성되었다.

덤프 뜬 것을 가져와서 복원시킨다.

mysql -u [계정] --port=3306 -p [데이터베이스명] < [파일명].sql

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17680

풀면서 재밌었던 문제이다.

LRU (Least Recently Used) 알고리즘

Least Recently Used (LRU) is a common caching strategy. It defines the policy to evict elements from the cache to make room for new elements when the cache is full, meaning it discards the least recently used items first.

• OS의 페이지 교체 알고리즘 중 하나.
• 문제에 언급된 LRU 알고리즘은 보편적인 캐싱 전략이며, 캐시가 다 찼을 때 새로운 값을 넣기 위해 가장 오랫동안 사용되지 않은 것을 버리는 방식이다.
• cache hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우.
• cache miss : CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않는 경우.

아래 이미지를 통해 LRU알고리즘의 동작방식을 살펴보겠다.  0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4 가 주어지고, cache size는 3이다. 빨간색 부분이 교체되는 가장 오랫동안 참조되지 않은 페이지이고, 노란 부분이 제일 최근에 참조된 페이지이다. 

• java에서 Doubly Linked List를 이용해서 구현할 수 있다.
  • 사용이유 : list의 front(head)나 end(tail)에 접근시에 모두 O(1) 상수시간 내에 접근 가능하기 때문이다. 그리고 insert, delete시에도 상수시간이다.

풀이

처음엔 '가장 오랫동안 참조되지 않은 페이지'를 찾으려면 어떻게 해야하지? 싶어서 LinkedHashMap을 이용해서 value에 참조된 횟수를 저장하는 식으로 풀려고 했다. 그런데 최근 참조된 페이지를 head에 두고, 오랫동안 참조되지 않은 페이지를 tail에 두는 식으로 풀면 굳이 몇번 참조되었는지의 상세한 정보는 필요가 없어서 LinkedHashSet을 이용해서 푸는 풀이로 바꿨다.

LinkedHashSet을 이용하면 값의 중복은 비허용하고, 삽입한 순서를 기억하기 때문에 아래 방식으로 풀었다.

1. hit한 경우에는 element를 remove했다가 다시 insert해준다. => 최신값으로 유지. 
2. 가장 오랫동안 참조되지 않은 element는 맨 앞에 남게 된다.

참고자료

https://velog.io/@haero_kim/LRU-Cache-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0