happyduck-git

    public static void bubbleSort(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {
            for(int j = 0; j < arr.length - i - 1; j++) {
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }

happyduck-git

    public static void countingSort(int[] arr) {
        //arr의 원소로 들어갈 수 있는 수의 범위가 0부터 100까지라고 가정
        //범위에 따라 사이즈를 다르게 하면 됨
        int[] countArr = new int[101];
        
        //countArr을 이용해 정수가 몇개 들어왔는지 확인하기
        for(int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
        }
        

happyduck-git

//amount원 만큼을 coins[]에 있는 coin들을 사용하여 만들 수 있는 조합의 수를 구하는 method
public static long change(int amount, int[] coins) {
      
     //조합의 수를 저장할 array 생성
     long[] combinations = new long[amount + 1]; //0부터 amount까지의 숫자가 모두 들어가야 해서 size는 amount+1이 됨

     //0번째는 무조건 1
     combinations[0] = 1;

happyduck-git

//matrix 형태의 graph에서 dfs 탐색하는 방법 

public void depthFirstSearch(int from) {
  boolean[] visited = new boolean[matrix.length];
  dFSHelper(from, visited);
}

public void dFSHelper(int from, boolean[] visited) {
  //방문 이력 체크
  if(visited[from]) { return; }

happyduck-git

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

public class Graph {
  int size;
  ArrayList<Node> vertices;

happyduck-git

public Graph {

  ArrayList<LinkedList<Node>> verticesAndEdges;
  
  public Graph() {
    verticesAndEdges = new ArrayList<LinkedList<Node>>();
  }
  
  public void addVertedx(Node vertex) {
    LinkedList<Node> list = new LinkedList<>();

happyduck-git

//Recursion 이용한 DFS!

public void dFS(int from, int[][] matrix) {
  boolean[] visited = new boolean[matrix.length];
  dFSHelper(from, visited, matrix);
}

public void dFSHelper(int from, boolean[] visited, int[][] matrix) {
  //방문 여부 체크
  if(visited[from]) return;

happyduck-git

public void dFS(int from, int[][] matrix) {
  
  ArrayList<Node> stack = new ArrayList<>();
  
  if(visited[from]) return;
  //첫 방문이면 방문 확인!
  visited[from] = true;
  stack.add(vertices.get(from)); //Node type의 데이터를 add 하는 부분 (Graph class에 정의한 vertices list를 의미한 것인데 때에 따라 변경될 수 있음)
  
  //stack이 빌 때까지 진행!

happyduck-git

public void bFS(int from, int[][] matrix) {

  Queue<Integer> queue = new LinkedList<>();
  boolean[] visited = new boolean[matrix.length];
  
  queue.offer(from);
  visited[from] = true;
  
  while(!queue.isEmpty()) {
    from = queue.poll();

happyduck-git

/* 1D나 2D array 모두에 사용 가능!*/

int[][] ints = new int[n][2];

for(int i = 0; i < n; i++) {
    st = new StringTokenizer(br.readLine());
    ints[i][0] = Integer.parseInt(st.nextToken());
    ints[i][1] = Integer.parseInt(st.nextToken());
}