[Algorithm] 최소신장트리(MST) - Prim

하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식

1. 임의의 정점을 하나 선택
2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
3. 모든 정점이 선택될 때까지 1, 2 과정을 반복

code

Edge

public class Edge {
    int adjvertex; // 간선의 다른쪽 끝 정점
    int weight;    // 간선의 가중치
    public Edge(int v, int wt) {
        adjvertex = v;
        weight    = wt;
    }
}

PrimMST

import java.util.List;
public class PrimMST {
    int N; // 그래프 정점의 수
    List<Edge>[] graph;

    public PrimMST(List<Edge>[] adjList) { // 생성자
        N = adjList.length;
        graph = adjList;
    }

    public int[] mst (int s) { // Prim 알고리즘,s는 시작정점
        boolean[] visited = new boolean[N]; // 방문된 정점은 true로
        int[] D = new int[N];
        int[] previous = new int[N]; // 최소신장트리의 간선으로 확정될 때 간선의 다른 쪽 (트리의)끝점
        for(int i = 0; i < N; i++){  // 초기화
            visited[i] = false;
            previous[i] = -1;
            D[i] = Integer.MAX_VALUE;  // D[i]를 최댓값으로 초기화
        }
        previous[s] = 0;  //시작정점 s의 관련 정보 초기화
        D[s] = 0;

        for(int k = 0; k < N; k++){ // 방문안된 정점들의 D 원소들중 에서 최솟값가진 정점 minVertex 찾기            
            int minVertex = -1;
            int min = Integer.MAX_VALUE;
            for(int j=0;j<N;j++){
                if ((!visited[j])&&(D[j] < min)){
                    min = D[j];
                    minVertex = j;
                }
            }
            visited[minVertex] = true;
            for (Edge i : graph[minVertex]){ // minVertex에 인접한 각 정점의 D의 원소 갱신             
                if (!visited[i.adjvertex]){  // 트리에 아직 포함 안된 정점이면
                    int currentDist = D[i.adjvertex];
                    int newDist = i.weight;
                    if (newDist < currentDist){             
                        D[i.adjvertex] = newDist; // minVertex와 연결된 정점들의 D 원소 갱신
                        previous[i.adjvertex] = minVertex; // 트리 간선 추출을 위해 
                    }
                }
            }
        }   
        return previous; // 최소신장트리 간선 정보 리턴
    }
}

수행시간

Prim 알고리즘은 N번의 반복을 통해 minVertex를 찾고 minVertex에 인접하면서 트리에 속하지 않은 정점에 해당하는 D 의 원소 값을 갱신

PrimMST 클래스에서는 minVertex를 배열 D에서 탐색하는 과정에서 $O(N)$ 시간이 소요되고, minVertex에 인접한 정점들을 검사하여 D의 해당 원소를 갱신하므로 $O(N)$ 시간이 소요된다. 따라서 총 수행시간은
$$
N\times(O(N) +O(N)) = O(N^2)
$$

Reference

『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)

『SW 문제해결 응용 - 구현 - 그래프의 최소 비용 문제』

​ https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AV3GBeD6AF4BBARB#

[Data Structure] 그래프(Graph)

1. 그래프

그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결관걔를 표현한다.

그래프는 정점(Vertex)과 정점을 연결하는 간선(Edge)의 집합로 객체간의 관계를 표현할 수 있는 자료구조이다.

• $|V|$: 정점의 개수, $|E|$: 그래프에 포함된 간선의 개수
• $|V|$개의 정점을 가지는 그래프는 최대 간선의 개수는$|E|=|V|\times\frac{|V|−1}{2}$개의이다.

선형 자료구조나 트리 자료구조로 표현하기 어려운 $N:N$ 관계를 가지는 원소들을 표현하기 용이하다.

2. 그래프의 유형

1) 무향그래프(Undirected Graph)

서로 대칭적인 관계를 연결해서 나타낸 그래프

간선에 방향이 없는 그래프

정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.

• (A, B)와 (B, A)는 같은 간선을 의미

2) 유향그래프(Directed Graph)

간선을 화살표로 표현, 방향성의 개념이 포함이된다.

간선에 방향이 있는 그래프

정점 A에서 정점 B로만 갈수 있는 간선은 <A, B>와 같이 표현한다.

• <A, B>와 <B, A>는 다름

3) 가중치그래프(Weighted Graph)

이동하는 데 드는 비용을 간선에 부여한 그래프

가중치는 두 정점 사이의 거리, 지나는 시간, 금액등이 될수 있으며 또한 음수인 경우도 존재한다.

두 정점 간의 이동방향이 다를경우 가중치가 다를 수 있음.

4) 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)

어떠한 정점 v에서 시작하여 다시 v로 가는 경로가 없는 그래프

위상정렬이 있는 유향그래프

5) 완전 그래프

정점들에 대해 가능한 모든 간선들을 가진 그래프

6) 부분 그래프

원래 그래프에서 일부의 정점이나 간선을 제외한 그래프

3. 그래프 용어와 표현

1) 그래프(Graph)

G=(V, E)로 표현, V=정점의 집합, E=간선의 집합

2) 인접(Adjacency)

두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.

2) 차수(Degree)

정점에 인접한 정점의 수

방향그래프에서는 차수를 진입차수(In-degree)와 진출차수(Out-degree)로 구분

3) 경로(Path)

시작 정점부터 도착 정점까지의 정점들을 나열하여 표현

• [a, c, b, e] : 정점 a로부터 도착점 e까지의 여러 경로들 중 하나

단순 경로(Simple Path)

• 경로 중에서 반복되는 정점이 없는 경우(경로상의 정점들이 모두 다른 경로)

사이클(Cycle)

• 단순 경로의 시작 정점과 종료 정점이 동일한 경우

4. 그래프 표현

그래프는 주로 2가지 방법을 이용하여 표현한다

• 인접행렬
• 인접리스트

메모리나 성능을 고려해서 결정해야한다.

1) 인접행렬

두 정점을 연결하는 간선의 유무를 행렬로 표현

• NN개의 정점(노드)을 가진 그래프를 $N×N$배열에 저장하여 표현
• 간선의 수와 무관하게 항상 $N^2$개의 메모리 공간이 필요하다.

배열의 인덱스는 정점을 의미

정점 i와 j 사이에 간선이 없으면 $a[i][j]=0$, 간선이 있으면 $a[i][j]=1$로 표현

• 가중치그래프는 1대신 가중치를 저장하고 인접하지 않은 정점의 비용은 무한대로 표시한다.

대각선의 요소는 무의미

단점

정점의 개수 $N$이 커지면 필요한 메모리 크기는 $N^2$에 비례하여 커짐

어떤 정점의 인접 정점을 찾을때마다 $N$개의 정점을 탐색해야한다.

정점의 개수에 비례하여 시간도 증가한다.

해결

그래프를 인접리스트로 표현하여 불필요한 메모리사용과 비용을 줄일 수 있음.

2) 인접리스트

각 정점에 대한 인접 정점들을 순차적으로 표현

하나의 정점에 인접한 모든 노드를 연결 리스트 형태로 저장

• 경로에 관한 정보가 아님.

가중치 정보를 표시하려면 노드에 가중치 필드를 추가하여 표현한다.

5. 그래프의 순회

모든 자료(정점)을 빠짐없이 탐색하는 것을 의미한다.

그래프에서는 2가지 방식으로 모든 정점을 탐색한다.

• 깊이우선탐색(DFS: Depth First Search)
• 너비우선탐색(BFS: Breadth First)

1) 깊이우선탐색(DFS)

가장 마지막 정점으로 돌아가 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용하거나 재귀 호출을 이용하여 구현한다.

방법

1. 시작 정점에서 방향을 선택해서 다음 정점으로 이동
2. 선택된 정점에서 앞 단계 작업을 반복 수행하면서 갈 수 있는 경로가 있는 곳 까지 탐색
   • 이미 방문한 정점은 재방문 하지 않는다.
3. 더이상 갈 곳이 없으면 가장 최근 갈림길의 정점으로 돌아와 다른 방향의 정점으로 탐색을 반복, 모든 정점을 방문한다.

code

import java.util.List;
public class DFS {

   static class Edge {
        int adjvertex;  // 선분의 다른쪽 정점
        public Edge(int v) { // 생성자
            adjvertex = v;
        }
    }

    int N;     // 그래프 정점의 수
    List<Edge>[] graph;
    private boolean[ ] visited;    // DFS 수행 중 방문한 정점을 true로 만든다.
    public DFS(List<Edge>[] adjList) { // 생성자
        N = adjList.length;
        graph = adjList;
        visited = new boolean [N];
        for (int i = 0; i < N; i++) visited[i] = false;  // 배열 초기화
        for (int i = 0; i < N; i++) if (!visited[i]) dfs(i);
    }
    private void dfs(int i) {
        visited[i] = true;        // 점점 i가 방문되어 visited[i]를 true로 만든다.
        System.out.print(i+" ");  // 정점 i가 방문되었음을 출력한다.
        for (Edge e: graph[i]) {  // 정점 i에 인접한 각 정점에 대해
            if (!visited[e.adjvertex]) { // 정점 i에 인접한 정점이 방문 안되었으면 재귀호출
                dfs(e.adjvertex);
            }
        }
    }
}

2) 너비우선탐색(BFS)

인접한 정점들에 대해 탐색 후 차례로 너비우선탐색을 진행해야 하므로 선입선출 형태의 자료구조인 큐를 활용한다.

방법

1. 시작 정점에서 인접한 정점들을 먼저 모두 차례로 방문한다.
2. 방문했던 정점을 다시 시작점으로 하여 계속 방문 수행함
   • 이미 방문한 정점은 재방문 하지 않는다.

code

import java.util.*;
public class BFS {

    static class  Edge {
        int adjvertex;
        public Edge(int v) {
            adjvertex = v;
        }
    }

    int N;  // 그래프 정점의 수
    List<Edge>[] graph;
    private boolean[ ] visited;     // BFS 수행 중 방문한 정점의 원소를 true로 만든다.
    public BFS(List<Edge>[] adjList) { // 생성자
        N = adjList.length;
        graph = adjList;
        visited = new boolean [N];
        for (int i = 0; i < N; i++) visited[i] = false;   // 배열 초기화
        for (int i = 0; i < N; i++) if (!visited[i]) bfs(i);
    }
    private void bfs(int i) {
        Queue<Integer> q = new LinkedList<Integer>();  // 큐 선언
        visited[i] = true;
        q.add(i); //큐에 시작 정점 s를 삽입        
        while (!q.isEmpty()) {
            int j = q.remove();           // 큐에세 정점 j를 가져옴 
            System.out.print(j+" ");
            for (Edge e: graph[j]) {     // 정점 j에 인접한 정점들 중 방문안된 정점 하나씩 방문
                if (!visited[e.adjvertex]) {
                    visited[e.adjvertex] = true;
                    q.add(e.adjvertex);  // 새로이 방문된 정점을 큐에 삽입
                }
            }
        }
    }
}

Reference

『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)

『SW 문제해결 응용 - 구현 - 그래프의 기본과 탐색』

배열을 이용한 리스트 구현

code

import java.util.NoSuchElementException;

public class ArrayList{

    static class List<E> {
        private E a[]; // 리스트의 항목들을 저장할 배열
        private int size; // 리스트의 항목 수

        // 생성자
        public List() {
            a = (E[]) new Object[1]; // 최초로 1개의 원소를 가진 배열 생성
            size = 0; // 항목 수를 0으로 초기화
        }

        // 리스트가 empty이면 true 리턴
        public boolean isEmpty() {
            return size == 0;
        }

        // 가장 뒤에 새 항목 삽입
        public void insertLast(E newItem) {
            if (size == a.length) // 배열에 빈 공간이 없으면
                resize(2 * a.length); // 배열 크기 2배로 확장
            a[size++] = newItem; // 새 항목 삽입
        }

        // 새 항목을 k-1번쨰 항목 다음에 삽입
        public void insert(E newItem, int k) {
            if (size == a.length) // 배열에 빈 공간이 없으면
                resize(2 * a.length); // 배열 크기 2배로 확장

            // 한 칸씩 뒤로 이동
            for (int i = size - 1; i >= k; i--)
                a[i + 1] = a[i];

            a[k] = newItem;
            size++;
        }

        // k번째 항목 삭제
        public E delete(int k) {
            // underflow 경우에 프로그램 정지
            if (isEmpty())
                throw new NoSuchElementException();

            E item = a[k];

            // 한 칸씩 앞으로 이동
            for (int i = k; i < size; i++)
                a[i] = a[i + 1];
            size--;

            if (size > 0 && size == a.length / 4) // 배열에 항목들이 1/4만 차지한다면
                resize(a.length / 2); // 배열을 1/2 크기로 축소
            return item;
        }

        // k번째 항목을 리턴, 단순히 읽기만 한다.
        public E peek(int k) {
            // underflow 경우에 프로그램 정지
            if (isEmpty())
                throw new NoSuchElementException();
            return a[k];
        }

        // 배열 크기 조절
        private void resize(int newSize) {
            Object[] t = new Object[newSize]; // newSize 크기의 새로운 배열 t 생성

            for (int i = 0; i < size; i++)
                t[i] = a[i]; // 배열 s를 배열 t로 복사

            a = (E[]) t; // 배열 t를 배열 s로
        }

        // 배열의 항목들을 출력
        public void print() {
            if (isEmpty())
                System.out.print("배열이 비어있음.");
            else
                for (int i = 0; i < a.length; i++)
                    System.out.print(a[i] + "\t ");
            System.out.println();
        }

    }

    public static void main(String[] args) {
        // TO-DO
    }

}

Reference

『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)

[BOJ] 4195. 친구 네트워크 - UnionFind

제출일 : 2019-11-03

문제 풀이 시간 : 2H

난이도 : ★★★☆

Problem

link : https://www.acmicpc.net/problem/4195

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

Example

input

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

output

2
3
4
2
2
4

Solution & Inpression

Union-Find를 활용한 문제

Code

언어 : JAVA

메모리 : 105,164 kb

실행시간 : 1500 ms

import java.io.FileInputStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static Map<String, Integer> map;
    static int[][] parent;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt(); // 테스트 케이스의 개수 T

        for (int tc = 1; tc <= T; tc++) {

            int F = sc.nextInt();// 친구 관계 수 F <= 100,000
            makeSet(2 * F);
            map = new HashMap<>();

            for (int i = 0; i < F; i++) {
                String id1 = sc.next();
                String id2 = sc.next();

                if (!map.containsKey(id1))
                    map.put(id1, map.size());
                if (!map.containsKey(id2))
                    map.put(id2, map.size());

                System.out.println(union(map.get(id1), map.get(id2)));
            }

        } // end of TC
    }// end of Main

    private static void makeSet(int n) {
        parent = new int[n][2];
        for (int i = 0; i < parent.length; i++) {
            parent[i][0] = i; // i의 부모는 i
            parent[i][1] = 1; // i집합의 크기는 1;
        }
    }

    private static int union(int a, int b) {
        int x = find(a);
        int y = find(b);

        if (x != y) {
            if (x < y) {
                parent[y][0] = x;
                return parent[x][1] += parent[y][1];
            } else {
                parent[x][0] = y;
                return parent[y][1] += parent[x][1];
            }
        }
        return parent[x][1];

    }

    private static int find(int x) {
        if (x == parent[x][0])
            return x;
        else
            return parent[x][0] = find(parent[x][0]);
    }

}

[SWEA] 5658. 보물상자 비밀번호 - Simulation

제출일 : 2019-09-03

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo

Input

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 숫자의 개수 N과 크기 순서 K가 주어 진다.

그 다음 줄에는 16진수 0~F 숫자가 공백 없이 N개 주어진다.

Output

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

Example

input

5
12 10
1B3B3B81F75E
16 2
F53586D76286B2D8
…

output

#1 503
#2 55541
#3 334454
#4 5667473
#5 182189737

Code

언어 : JAVA

메모리 : 30,296 kb

실행시간 : 130ms

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            System.out.print("#" + tc + " ");
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            int M = N / 4;
            ArrayList<Character> list = new ArrayList<>();
            String str = br.readLine();
            for (int i = 0; i < N; i++) {
                list.add(str.charAt(i));
            }
            ArrayList<String> numlist = new ArrayList<>();
            str = "";
            for (int i = 1; i <= N; i++) {
                str += list.get(i - 1);
                if (i % M == 0) {
                    if (!numlist.contains(str))
                        numlist.add(str);
                    str = "";
                }
            }

            for (int i = 1; i <= M - 1; i++) {
                char tmp = list.get(0);
                list.remove(0);
                list.add(tmp);
                str = "";
                for (int j = 1; j <= N; j++) {
                    str += list.get(j - 1);
                    if (j % M == 0) {
                        if (!numlist.contains(str))
                            numlist.add(str);
                        str = "";
                    }
                }
            }

            Collections.sort(numlist, new Comparator<String>() { // 역정렬
                @Override
                public int compare(String o1, String o2) {
                    int x = Integer.parseInt(o1, 16);
                    int y = Integer.parseInt(o2, 16);
                    return y - x;
                }
            });

            System.out.println(Integer.parseInt(numlist.get(K-1), 16));

        } // end of TC
    }// end of main
}

[SWEA] 6109. 추억의 2048게임 D4 - Simulation

제출일 : 2019-11-03

문제 풀이 시간 : 1H 30M

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWbrg9uabZsDFAWQ

Input

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1≤N≤20)과 하나의 문자열 S가 공백 하나로 구분되어 주어진다.

S는 “left”, “right”, “up”, “down”의 넷 중 하나이며 각각 타일들을 왼쪽, 오른쪽, 위쪽, 아래쪽으로 이동시키겠다는 뜻이다.

다음 N개의 줄의 i번째 줄에는 N개의 정수가 공백 하나로 구분되어 주어진다.

이 정수들은 0이거나 2이상 1024이하의 2의 제곱수들이다.

i번째 줄의 j번째 정수는 격자의 위에서 i번째 줄의 왼쪽에서 j번째에 있는 칸에 있는 타일에 어떤 정수가 적혀 있는지 나타내며,

0이면 이 칸에 타일이 없음을 의미한다.

Output

각 테스트 케이스마다 ‘#t’(t는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고 한 줄을 띄운 후,

N줄에 걸쳐 격자의 어떤 위치에 어떤 숫자가 적힌 타일이 있는지 입력 형식과 같은 형식으로 출력한다.

Example

input

2
5 up
4 8 2 4 0
4 4 2 0 8
8 0 2 4 4
2 2 2 2 8
0 2 2 0 0
2 down
16 2
0 2

output

#1
8 8 4 8 8
8 4 4 2 4
2 4 2 0 8
0 0 0 0 0
0 0 0 0 0
#2
0 0
16 4

Solution & Inpression

시뮬레이션 문제

차근차근 구현하면 되는 문제......

Code

언어 : JAVA

메모리 : 73,768 kb

실행시간 : 363 ms

import java.io.FileInputStream;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            int N = sc.nextInt();
            String cmd = sc.next();
            int[][] in = new int[N][N];
            int[][] out = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    in[i][j] = sc.nextInt();
                }
            }
            switch (cmd) {
            case "up":
                for (int j = 0; j < N; j++) { // 열 우선 탐색
                    for (int i = 0; i < N - 1; i++) { // 위부터 아래로
                        if (in[i][j] == 0) // 현재 값이 0이면 패스
                            continue;

                        int idx = i + 1;

                        while (in[idx][j] == 0) { // 비교할 값이 0이면 다음값
                            if (idx == N - 1) // 끝까지 탐색
                                break;
                            idx++;
                        }

                        if (in[idx][j] == 0) // 비교할 값이 0이면 패스
                            continue;

                        if (in[i][j] == in[idx][j]) { // 합치고 지우고
                            in[i][j] += in[i][j];
                            in[idx][j] = 0;
                            i = idx;
                        }
                    }
                    int cur = 0;
                    for (int i = 0; i < N; i++) { // 결과 입력
                        if (in[i][j] != 0) {
                            out[cur++][j] = in[i][j];
                        }
                    }
                }
                break;
            case "down":
                for (int j = 0; j < N; j++) { // 열 우선 탐색
                    for (int i = N - 1; i > 0; i--) { // 아래부터 위
                        if (in[i][j] == 0) // 현재 값이 0이면 패스
                            continue;

                        int idx = i - 1;

                        while (in[idx][j] == 0) { // 비교할 값이 0이면 다음값
                            if (idx == 0) // 끝까지 탐색
                                break;
                            idx--;
                        }

                        if (in[idx][j] == 0) // 비교할 값이 0이면 패스
                            continue;
                        if (in[i][j] == in[idx][j]) { // 합치고 지우고
                            in[i][j] += in[i][j];
                            in[idx][j] = 0;
                            i = idx;
                        }

                    }
                    int cur = N - 1;
                    for (int i = N - 1; i >= 0; i--) { // 결과 입력
                        if (in[i][j] != 0) {
                            out[cur--][j] = in[i][j];
                        }
                    }
                }
                break;
            case "left":
                for (int i = 0; i < N; i++) { // 행우선 탐색
                    for (int j = 0; j < N - 1; j++) { // 왼쪽부터 오른쪽으로
                        if (in[i][j] == 0) // 현재 값이 0이면 패스
                            continue;

                        int idx = j + 1;

                        while (in[i][idx] == 0) { // 비교할 값이 0이면 다음값
                            if (idx == N - 1) // 끝까지 탐색
                                break;
                            idx++;
                        }

                        if (in[i][idx] == 0) // 비교할 값이 0이면 패스
                            continue;

                        if (in[i][j] == in[i][idx]) { // 합치고 지우고
                            in[i][j] += in[i][j];
                            in[i][idx] = 0;
                            j = idx;
                        }
                    }
                    int cur = 0;
                    for (int j = 0; j < N; j++) { // 결과 입력
                        if (in[i][j] != 0) {
                            out[i][cur++] = in[i][j];
                        }
                    }
                }
                break;

            case "right":
                for (int i = 0; i < N; i++) { // 행우선 탐색
                    for (int j = N-1; j > 0; j--) { // 오른쪽 부터 왼쪽으로
                        if (in[i][j] == 0) // 현재 값이 0이면 패스
                            continue;

                        int idx = j - 1;

                        while (in[i][idx] == 0) { // 비교할 값이 0이면 다음값
                            if (idx == 0) // 끝까지 탐색
                                break;
                            idx--;
                        }

                        if (in[i][idx] == 0) // 비교할 값이 0이면 패스
                            continue;

                        if (in[i][j] == in[i][idx]) { // 합치고 지우고
                            in[i][j] += in[i][j];
                            in[i][idx] = 0;
                            j = idx;
                        }
                    }
                    int cur = N-1;
                    for (int j = N-1; j >=0 ; j--) { // 결과 입력
                        if (in[i][j] != 0) {
                            out[i][cur--] = in[i][j];
                        }
                    }
                }
                break;

            }

            System.out.println("#" + tc);
            for (int[] is : out) {
                for (int i : is) {
                    System.out.print(i + " ");
                }
                System.out.println();
            }

        } // end of TC
    }// end of Main
}

[JUNGOL] 1921. 구구단

제출일 : 2019-10-23

문제 풀이 시간 : 15M

난이도 : ★

Problem

link : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=574

원하는 구구단의 범위를 입력받아 해당 구간의 구구단을 출력하는 프로그램을 작성하시오.

<처리조건>
(1) 구간의 처음과 끝을 입력받는다.
(2) 입력된 구간은 반드시 처음 입력 값이 끝의 입력 값보다 작아야 하는 것은 아니다.

즉 입력된 구간의 범위는 증가하거나 감소하는 순서 그대로 출력되어야 한다.

Input

구구단의 시작 범위 s,와 끝 범위 e를 입력받는다. (s와 e는 2부터 9사이의 정수)

하나의 결과가 출력되면 프로그램을 종료한다.

Output

시작 범위와 끝 범위사이의 구구단을 출력하되 모든 값과 부호 사이는 공백으로 구분하여 아래 출력 예와 같이 줄을 맞추어 출력해야 한다.

구구단 사이는 3개의 공백으로 구분한다.

데이터의 크기가 주어진 범위를 벗어날 경우는 "INPUT ERROR!"를 출력하고 s와 e를 다시 입력받는다.

Example

input

4 3

output

4 * 1 =  4   3 * 1 =  3
4 * 2 =  8   3 * 2 =  6
4 * 3 = 12   3 * 3 =  9
4 * 4 = 16   3 * 4 = 12
4 * 5 = 20   3 * 5 = 15
4 * 6 = 24   3 * 6 = 18
4 * 7 = 28   3 * 7 = 21
4 * 8 = 32   3 * 8 = 24
4 * 9 = 36   3 * 9 = 27

Solution & Inpression

쉽다고 무시했지만 3번이나 틀린 문제.....

문제를 정확하게 읽고 푸는 연습이 필요하다

Code

언어 : JAVA

메모리 : 10 mb

실행시간 : 202 ms

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s, e;
        while (true) {
            s = sc.nextInt();
            e = sc.nextInt();
            if (s < 2 || 9 < s || e < 2 || 9 < e) {
                System.out.println("INPUT ERROR!");
            } else
                break;
        }
        if (s < e) {
            for (int j = 1; j <= 9; j++) {
                for (int i = s; i <= e; i++) {
                    System.out.printf("%d * %d = %2d   ", i, j, i * j);
                }
                System.out.println();
            }
        } else {
            for (int j = 1; j <= 9; j++) {
                for (int i = s; i >= e; i--) {
                    System.out.printf("%d * %d = %2d   ", i, j, i * j);
                }
                System.out.println();
            }
        }
        sc.close();
    }
}

[SQL 고득점 Kit] - IS NULL

link : https://programmers.co.kr/learn/courses/30/parts/17045

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다.

1. 이름이 없는 동물의 아이디

Problem

동물 보호소에 들어온 동물 중, 이름이 없는 채로 들어온 동물의 ID를 조회하는 SQL 문을 작성해주세요. 단, ID는 오름차순 정렬되어야 합니다.

예시

예를 들어 ANIMAL_INS 테이블이 다음과 같다면

이름이 없는 채로 들어온 동물의 ID는 A368930입니다. 따라서 SQL을 실행하면 다음과 같이 출력되어야 합니다.

code

select animal_id
from animal_ins
where name is null

2. 이름이 있는 동물의 아이디

Problem

동물 보호소에 들어온 동물 중, 이름이 있는 동물의 ID를 조회하는 SQL 문을 작성해주세요. 단, ID는 오름차순 정렬되어야 합니다.

예시

예를 들어 ANIMAL_INS 테이블이 다음과 같다면

이름이 있는 동물의 ID는 A524634와 A465637입니다. 따라서 SQL을 실행하면 다음과 같이 출력되어야 합니다.

code

select animal_id
from animal_ins
where name is not null
order by animal_id

3. NULL 처리하기

Problem

입양 게시판에 동물 정보를 게시하려 합니다. 동물의 생물 종, 이름, 성별 및 중성화 여부를 아이디 순으로 조회하는 SQL문을 작성해주세요. 이때 프로그래밍을 모르는 사람들은 NULL이라는 기호를 모르기 때문에, 이름이 없는 동물의 이름은 No name으로 표시해 주세요.

예시

예를 들어 ANIMAL_INS 테이블이 다음과 같다면

마지막 줄의 개는 이름이 없기 때문에, 이 개의 이름은 No name으로 표시합니다. 따라서 SQL문을 실행하면 다음과 같이 나와야 합니다.

※ 컬럼 이름은 일치하지 않아도 됩니다.

code

select animal_type, ifnull(name,'No name') as name, sex_upon_intake
from animal_ins
order by animal_id