프로젝트의 설계부터 산출물 관리까지 도와주는 서비스 https://github.com/Phoenix-kosa/AM_PM

제공 기능

팀원 관리 회원가입/로그인 프로젝트 산출물 업로드 팀채팅 간트차트 Q&A게시판 관리자 페이지

목표

프로젝트를 기획 단계부터 개발 단계까지 관리해주는 서비스

맡은 역할

웹소켓을 이용한 실시간 채팅 및 프로젝트 생성과 멤버 관리 구현

ERD

화면 구성

프로젝트 아키텍처

구현한 주요 내용

팀채팅

웹소켓을 이용하여 프로젝트 팀원 간의 실시간 채팅을 구현하였다. 팀원이 추가/제거됨에 따라 실시간 채팅 참여 인원이 달라지고 이에 따라 메시지를 읽은 사람의 수가 변화되도록 구현하였다.

프로젝트 생성 및 팀원 관리

사용자가 프로젝트를 생성하면 해당 프로젝트의 대표로 설정되며, 추후 팀원을 추가/제거하고 대표 역할을 위임할 수 있도록 구현하였다. 프로젝트 팀원 추가 혹은 프로젝트의 삭제는 대표의 권한으로 구현하였으며, 프로젝트 삭제시 팀원을 모두 제거하여야 하는 조건을 설정하였다.

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

소스

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.next();
        StringBuilder sb = new StringBuilder();
        String word;
        Queue<String> queue = new LinkedList<>();
        for(int i = 0; i < input.length(); i++) {
            word = input.substring(i, i+1);
            if(word.equals("+") || word.equals("-")) {
                queue.add(String.valueOf(sb));
                sb.setLength(0);
                queue.add(word);
            }
            else
                sb.append(word);
        }
        queue.add(String.valueOf(sb));

        int sum = 0;
        boolean minus = false;
        while(!queue.isEmpty()) {
            if(minus)
                sum -= Integer.parseInt(queue.poll());
            else
                sum += Integer.parseInt(queue.poll());
            if(!queue.isEmpty() && queue.poll().equals("-")) {
                minus = true;
            }
        }
        System.out.println(sum);
    }
}

"-"기호가 한 번이라도 등장하면 그 뒤에 나오는 수식은 모두 뺄셈으로 계산할 수 있다.

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

소스

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int N = Integer.parseInt(br.readLine()); // 회의의 개수
        List<Meeting> meetingList = new ArrayList<>();
        Meeting meeting;
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            meeting = new Meeting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            meetingList.add(meeting);
        }
        int count = 0;
        int endTime;
        meetingList.sort(new Comparator<Meeting>() {
            @Override
            public int compare(Meeting o1, Meeting o2) {
                if(o1.end == o2.end)
                    return o1.start - o2.start;
                return o1.end - o2.end;
            }
        });
        endTime = meetingList.get(0).end;
        count++;
        for(int i = 1; i < meetingList.size(); i++) {
            if(meetingList.get(i).start >= endTime) {
                endTime = meetingList.get(i).end;
                count++;
            }
        }
        System.out.println(count);
    }
}
class Meeting {
    int start;
    int end;
    Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

소스

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int N = Integer.parseInt(br.readLine()); // 수열의 크기
        PriorityQueue<Integer> positive = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> negative = new PriorityQueue<>();
        int input;
        for(int i = 0; i < N; i++) {
            input = Integer.parseInt(br.readLine());
            if(input > 0)
                positive.add(input);
            else
                negative.add(input);
        }
        int sum = 0;
        int num1;
        int num2;
        while(positive.size() > 1) {
            num1 = positive.poll();
            num2 = positive.poll();
            sum += Math.max(num1 + num2, num1 * num2);
        }
        while(!positive.isEmpty())
            sum += positive.poll();
        while(negative.size() > 1) {
            num1 = negative.poll();
            num2 = negative.poll();
            sum += Math.max(num1 + num2, num1 * num2);
        }
        while(!negative.isEmpty())
            sum += negative.poll();
        System.out.println(sum);
    }
}

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

소스

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int N = Integer.parseInt(br.readLine()); // 카드 묶음의 개수
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0; i < N; i++)
            queue.add(Integer.parseInt(br.readLine()));
        int result = 0;
        int num1;
        int num2;
        while(queue.size() > 1) {
            num1 = queue.poll();
            num2 = queue.poll();
            result += num1 + num2;
            queue.add(num1 + num2);
        }
        System.out.println(result);
    }
}

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        final int N = Integer.parseInt(st.nextToken()); // 동전의 종류
        int K = Integer.parseInt(st.nextToken()); // 목표 가격
        int[] coins = new int[N];
        for(int i = 0; i < N; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }
        int cnt = 0;
        while(K > 0) {
            for(int i = N - 1; i >= 0; i--) {
                if(K < coins[i])
                    continue;
                cnt += K / coins[i];
                K %= coins[i];
            }
        }
        System.out.println(cnt);
    }
}

그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다. 그리디 알고리즘은 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수하다. 하지만 항상 최적의 해를 보장하지 못한다는 단점도 있다. 따라서 그리디 알고리즘을 적용할 때의 논리 유무를 충분히 살펴야 한다.

그리디 알고리즘의 핵심 이론

① 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. ② 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. ③ 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 ①로 돌아가 같은 과정을 반복한다.

예제

동전 0 카드 정렬하기 회의실 배정 수 묶기 잃어버린 괄호

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

소스

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int N = Integer.parseInt(br.readLine()); // 배열의 크기
        final int k = Integer.parseInt(br.readLine()); // k번째 수 찾기
        int startIndex = 1;
        int endIndex = k;
        int midIndex;
        int sum;
        int result = 0;
        while(startIndex <= endIndex) {
            midIndex = (startIndex + endIndex) / 2;
            sum = 0;
            for(int i = 0; i < N; i++) {
                sum += Math.min(midIndex / (i + 1), N);
            }
            if(sum < k)
                startIndex = midIndex + 1;
            else {
                endIndex = midIndex - 1;
                result = midIndex;
            }
        }
        System.out.println(result);
    }
}

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

출력

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

소스

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 강의의 수
        int M = Integer.parseInt(st.nextToken()); // 블루레이의 수
        st = new StringTokenizer(br.readLine());
        int[] input = new int[N]; // 강의 길이 배열
        int max = 0; // 길이 최대값
        int total = 0; // 길이 합
        for(int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(st.nextToken());
            max = Math.max(input[i], max);
            total += input[i];
        }
        int startIndex = max;
        int endIndex = total;
        int midIndex;
        int count;
        int sum;
        while(startIndex <= endIndex) {
            midIndex = (startIndex + endIndex) / 2;
            count = 1;
            sum = 0;
            for(int i : input) {
                sum += i;
                if(sum > midIndex) {
                    count++;
                    sum = i;
                }
            }
            if(count <= M)
                endIndex = midIndex - 1;
            else
                startIndex = midIndex + 1;
        }
        System.out.println(startIndex);
    }

}

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

소스

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

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()); // 정렬할 수 개수
        int[] input = new int[N]; // 정수 배열
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(input);
        int M = Integer.parseInt(br.readLine()); // 탐색할 숫자의 개수
        int target;
        int startIndex;
        int endIndex;
        int midIndex;
        boolean exist;
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++) {
            target = Integer.parseInt(st.nextToken()); // 탐색할 숫자
            startIndex = 0;
            endIndex = N - 1;
            midIndex = N / 2;
            exist = false;
            while(startIndex <= endIndex) {
                if(input[midIndex] > target)
                    endIndex = midIndex - 1;
                else if(input[midIndex] < target)
                    startIndex = midIndex + 1;
                else {
                    exist = true;
                    break;
                }
                midIndex = (startIndex + endIndex) / 2;
            }
            if(exist)
                System.out.println(1);
            else
                System.out.println(0);
        }
    }

}

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

풀이

트리의 지름을 찾는 방법 : 임의의 한 정점에서 가장 먼 정점을 찾고 그 정점에서 가장 먼 정점과의 거리가 트리의 지름이다. 증명 링크

소스

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

public class Main {
    static int V;
    static ArrayList[] graph;
    static boolean[] visited;
    static int[] distance;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        V = Integer.parseInt(br.readLine());
        StringTokenizer st = null;
        graph = new ArrayList[V + 1];
        for(int i = 0; i < V; i++) {
            st = new StringTokenizer(br.readLine());
            int order = Integer.parseInt(st.nextToken());
            graph[order] =  new ArrayList<>();
            int input = Integer.parseInt(st.nextToken());
            while(input != -1) {
                Edge edge = new Edge(input, Integer.parseInt(st.nextToken()));
                graph[order].add(edge);
                input = Integer.parseInt(st.nextToken());
            }
        }
        visited = new boolean[V + 1];
        distance = new int[V + 1];
        BFS(1);

        int farFromFirstValue = 1;
        for(int i = 1; i < V + 1; i++) {
            if(distance[farFromFirstValue] < distance[i])
                farFromFirstValue = i;
        }

        Arrays.fill(visited, false);
        Arrays.fill(distance, 0);
        BFS(farFromFirstValue);

        int maxValue = 1;
        for(int i = 1; i < V + 1; i++) {
            if(distance[maxValue] < distance[i])
                maxValue = i;
        }

        System.out.println(distance[maxValue]);
    }
    public static void BFS(int num) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(num);
        visited[num] = true;
        while(!queue.isEmpty()) {
            int now = queue.poll();
            ArrayList<Edge> edgeList = graph[now];
            for(Edge edge : edgeList) {
                if(!visited[edge.node]) {
                    visited[edge.node] = true;
                    queue.add(edge.node);
                    distance[edge.node] = distance[now] + edge.cost;
                }
            }
        }
    }
}
class Edge{
    int node;
    int cost;
    public Edge(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }
}

N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    static int N;
    static int M;
    static int[][] input;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        input = new int[N][M];
        for(int i = 0; i < N; i++) {
            String line = br.readLine();
            String[] lineArry = line.split("");
            for(int j = 0; j < M; j++) {
                input[i][j] = Integer.parseInt(lineArry[j]);
            }
        }

        BFS(0, 0);
        System.out.println(input[N-1][M-1]);
    }
    public static void BFS(int row, int column) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{row, column});

        boolean[][] visited = new boolean[N][M];
        visited[row][column] = true;

        int[][] move = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int[] search = {now[0] + move[i][0], now[1] + move[i][1]};
                if(search[0] > -1 && search[0] < N && search[1] > -1 && search[1] < M) {
                    if (input[search[0]][search[1]] != 0 && !visited[search[0]][search[1]]) {
                        visited[search[0]][search[1]] = true;
                        input[search[0]][search[1]] = input[now[0]][now[1]] + 1;
                        queue.add(search);
                    }
                }
            }
        }
    }
}

BFS를 사용해 최초로 도달했을 때 깊이 => 최단 거리

여러개의 컨텐츠를 여러 페이지로 나누어 보여주고 페이지 번호 버튼, 이전 버튼, 다음 버튼을 눌러서 페이지를 이동하는 기능

필요한 내용

한 페이지에서 보여줄 페이지 버튼의 개수 한 페이지에서 보여줄 컨텐츠 개수 이전 버튼, 다음 버튼

계산해야할 내용

총 페이지 개수 화면에 보여질 페이지 그룹 화면에 보여질 첫번째 페이지 번호 화면에 보여질 마지막 페이지 번호

총 페이지 개수

Math.ceil(전체 컨텐츠 개수/한 페이지에서 보여줄 컨텐츠 개수) ex) 총 페이지 개수 = Math.ceil(111/10) = 12페이지

화면에 보여질 페이지 그룹

Math.ceil(현재 페이지 번호/한 페이지에서 보여줄 페이지 버튼의 개수) ex) 한 화면에 보여줄 페이지 그룹 = Math.ceil(7/5) = 2번째 페이지 그룹

화면에 보여질 첫번째 페이지 번호

((페이지 그룹 - 1) * 한 페이지에서 보여줄 페이지 버튼의 개수) + 1 ex) 화면에 보여질 첫번째 페이지 번호 = ((2-1) * 5) + 1 = 6

화면에 보여질 마지막 페이지 번호

페이지 그룹 * 한 페이지에서 보여줄 페이지 버튼의 개수 ex) 화면에 보여질 마지막 페이지 번호 = 2 * 5 = 10 하지만 전체 페이지보다 크다면 마지막 페이지 번호 = 총 페이지 개수 ex)현재 페이지가 12 라면 페이지 그룹 : 3 첫번째 페이지 번호 : 11 마지막 페이지 번호 : 15 > 총 페이지 개수 12 이므로 마지막 페이지 번호는 12가 된다.

Offset 페이징

SELECT * FROM 테이블
ORDER BY 컬럼
OFFSET 10 LIMIT 5

offset에서 시작하여 limit만큼 가져온다. JPA > Pageable 객체 사용

Cursor 페이징

offset은 이전의 데이터를 조회하고 건너 뛰는 것이므로 데이터가 많을 수록 시간복잡도가 증가한다. 또한 삽입 삭제가 이루어질 경우 다음페이지에서 이전 페이지와 중복되는 데이터가 보일 수 있다.

cursor는 특정 조건 이후에 있는 데이터만 선별해서 가져온다.

SELECT * FROM 테이블
WHERE cursor > timestamp
ORDER BY timestamp
LIMIT 5

커서 페이징을 사용할 때 주의 사항 기준 컬럼이 중복된 값을 갖지 않고 순차적이어야 한다. 따라서 대부분 timestamp 컬럼을 기준으로 사용한다. 중복이 발생하는 컬럼을 커서로 사용하면 데이터 손실이 발생할 수 있다.

2개 이상의 테이블을 연결

Subquery

외부 쿼리 내에 내부 쿼리가 있는 구조

Subquery를 Join으로 대체할 수 있는 경우

1. 내부 쿼리가 단일 값을 반환하거나 1개의 열과 1개의 행을 반환하는 경우
2. IN( ) 연산자 안에 서브쿼리가 있는 경우
3. NOT IN( ) 연산자 안에 서브쿼리가 있는 경우
4. EXISTS, NOT EXISTS 연산자 안에 서브쿼리가 있는 경우

   Subquery를 Join으로 대체할 수 없는 경우

5. GROUP BY를 사용한 서브쿼리가 FROM절에 있는 경우
6. 집계된 값을 반환하는 서브쿼리가 WHERE절에 있는 경우
7. ALL( ) 연산자 안에 서브쿼리가 있는 경우

Join과 Subquery 성능 비교

참고 링크

내 주변의 산책로를 다른 사람과 공유할 수 있는 서비스 https://github.com/Team5Project/WalkingWithWorld

제공 기능

산책로 검색 검색 결과 조건 필터 회원가입/로그인 리뷰 작성(수정, 삭제) 댓글 작성(수정, 삭제) 산책로 공유글 작성(수정, 삭제)

목표

기존 지도 서비스에서는 제공하지 않았던 나만의 산책로를 생성하고 공유하는 기능 제공

맡은 역할

산책로 검색, 산책로 공유글 작성(수정, 삭제), 검색 결과 조건 필터

ERD

화면 구성

개발 환경

과정

1. 카카오맵API를 사용하여 사용자에게 경로를 입력받는 기능이 있다. 입력받은 경로를 산책로 상세보기 페이지에서 다시 보여주어야 하는데 이 부분을 구현하기 위해 DB일부를 수정하였다. map 테이블의 latlngs, course를 coordinateX, coordinateY라는 x좌표와 y좌표를 받는 것으로 변경하고 walking-paths 테이블의 산책로 게시글의 id를 참조하여 좌표 갯수만큼 생성되게 하였다. 지도를 입력받는 기능은 선의 거리 계산 기능을 이용하여 좌표값과 거리, 시간을 함께 입력받게 했다. 입력받은 지도를 보여주는 기능은 선 그리기 기능을 이용하여 좌표값을 선으로 이어 보여주게 하였다.

2. 산책로 게시글을 검색하고(검색어 없이 전체 조회를 하는 경우도 포함) 사용하는 조건 필터는 Join과 Subquery 중 Join을 활용하였다. 조인과 서브쿼리 비교 링크

3. 조건 필터에 사용할 양방향 슬라이더를 만들었다(참고링크). 실제 입력을 받는 range는 두 개가 있고, 사용자가 보고 동작시킨다고 생각되는 양방향 슬라이더를 div 태그로 만드는 원리이다.

4. 산책로 게시글 DTO에는 게시글의 정보와 사진 DTO 리스트를 가지고 있다. 게시글은 항상 사진과 함께 보여지기에 사진 리스트를 게시글 DTO에 추가하였는데, 지도 정보의 경우 필요한 경우에만 가져오게 하기 위해 산책로-지도 게시글 DTO를 추가하여 지도 DTO 리스트도 가지게 하였다.

5. 산책로 입력폼 제작.

6. 페이지네이션(페이지네이션 정리) 진행.

7. 게시글 수정/삭제하기에 인증된 사용자만 접근할 수 있도록 수정하였다.

8. 게시글 읽기/수정하기에 존재하지 않는 데이터에 접근하지 않도록 수정하였다.

9. 컨트롤러에서 사용되는 중복된 코드를 비즈니스 로직을 수행하는 service 컴포넌트로 분리하였다.

10. 게시글 작성/수정/삭제 후 사용자에게 보여줄 확인메시지를 추가했다.

구현한 주요 내용

맵 그리기

카카오맵 API를 이용하여 사용자가 입력한 값의 좌표 배열을 컨트롤러에서 받아 DB에 저장하게 하였다. 사용자에게 보여줄 때는 좌표 배열에서 값을 하나씩 꺼내 선을 그려 잇게 하였다.

조건 필터

조건 필터 내용을 받아올 DTO를 새로 만들어 지역/최소 소요 시간, 최대 소요 시간/최소 거리, 최대 거리를 사용자에게 입력받고 해당 조건에 해당하는 산책로 게시글을 받아와 AJAX를 이용해 보여주게 하였다.

배운점

DB update시 주의할 점 : 사용자의 입력 값으로 DB에 있는 데이터를 바로 수정하지 않는다. 해당 프로젝트에서는 사용자가 입력한 값 DTO와 DB에서 꺼내온 DTO를 이용해 수정된 부분만 변경하여 update되게 하였다. 수정/삭제 기능에서 주의할 점 : 예상하지 못한 접근 막기. 해당 프로젝트에서는 사용자의 id를 참조하여 수정/삭제 동작 버튼이 보이게 하였는데 버튼을 이용하지 않고 직접 수정/삭제 하는 부분에 대한 방어 코드가 없어 예상하지 못한 동작이 발생할 위험이 있었다. 수정/삭제 기능 전 인증된 사용자인지 확인하도록 수정하였다. 인덱싱(참고링크1, 참고링크2)을 적용하는 방법에 대해 공부하였다. 해당 프로젝트에 적용하고자 했으나 조금 더 학습이 필요하다.

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다

소스

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

public class Main {

    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] visited;
    static Queue<Integer> queue;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 노드 개수
        int M = Integer.parseInt(st.nextToken()); // 엣지 개수
        int start = Integer.parseInt(st.nextToken()); // 시작점
        graph = new ArrayList<>();
        for(int i = 0; i < N + 1; i++)
            graph.add(i, new ArrayList<>());
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int input1 = Integer.parseInt(st.nextToken());
            int input2 = Integer.parseInt(st.nextToken());
            graph.get(input1).add(input2); // 양방향
            graph.get(input2).add(input1);
        }
        for(ArrayList list : graph) // 정렬 필요
            if(!list.isEmpty())
                list.sort(new Comparator() {
                    @Override
                    public int compare(Object o1, Object o2) {
                        return (int) o1 - (int) o2;
                    }
                });
        visited = new boolean[N + 1];
        DFS(start);
        System.out.println();
        Arrays.fill(visited, false);
        queue = new LinkedList<>();
        BFS(start);
    }
    public static void DFS(int num) {
        visited[num] = true;
        System.out.print(num + " ");
        for(int i : graph.get(num))
            if(!visited[i])
                DFS(i);
    }
    public static void BFS(int num) {
        queue.add(num);
        visited[num] = true;
        while(!queue.isEmpty()) {
            int now = queue.poll();
            System.out.print(now + " ");
            for(int i : graph.get(now))
                if(!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
        }
    }
}

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

소스

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 노드 개수
        int M = Integer.parseInt(st.nextToken()); // 엣지 개수
        graph = new ArrayList<>();
        for(int i = 0; i < N; i++)
            graph.add(i, new ArrayList<>());
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int input1 = Integer.parseInt(st.nextToken());
            int input2 = Integer.parseInt(st.nextToken());
            graph.get(input1).add(input2);
            graph.get(input2).add(input1);
        }
        visited = new boolean[N];
        for(int i = 0; i < N; i++) {
            Arrays.fill(visited, false);
            DFS(i, 1);
        }
        System.out.print(0);
    }

    public static void DFS(int num, int depth) {
        if(depth >= 5) {
            System.out.print(1);
            System.exit(0);
        }
        visited[num] = true;
        depth++;
        for(int i : graph.get(num))
            if(!visited[i]) {
                DFS(i, depth);
                visited[i] = false; // 탐색 결과 종료조건에 해당되지 않을 때 visited를 false로 설정해주어야 한다!
            }
    }
}

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1 + 2 + 3 + 4 + 5 = 15 4 + 5 + 6 = 15 7 + 8 = 15 15 = 15 자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항 n은 10,000 이하의 자연수 입니다.

소스

class Solution {
    public int solution(int n) {
        int cnt = 0;
        int sum = 1;
        int indexLeft = 1;
        int indexRight = 1;

        while(indexLeft <= n && indexRight <= n) {
            if(sum < n)
                sum += ++indexRight;
            else if(sum > n)
                sum -= indexLeft++;
            else {
                cnt++;
                sum += ++indexRight;
                sum -= indexLeft++;
            }
        }
        return cnt;
    }
}

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

소스

import java.io.*;

public class Main {
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); //자릿수
        DFS(2, 1); // 일의 자리 소수인 2, 3, 5, 7 DFS 실행
        DFS(3, 1);
        DFS(5, 1);
        DFS(7, 1);
    }

    static void DFS(int num, int leng) {
        if(leng == N) {
            if(isPrime(num))
                System.out.println(num);
            return;
        }
        for(int i = 1; i < 10; i += 2) {
            if(isPrime(num * 10 + i))
                DFS(num * 10 + i, leng + 1);
        }
    }

    static boolean isPrime(int num) {
        for(int i = 2; i <= Math.sqrt(num); i++)
            if(num % i == 0)
                return false;
        return true;
    }

}

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

소스

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); //정점의 개수
        M = Integer.parseInt(st.nextToken()); // 간선의 개수

        graph = new ArrayList<>(); // 그래프 인접 리스트(0부터 N-1까지)
        for(int i = 0; i < N; i++)
            graph.add(i, new ArrayList<>());
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            add(graph, x - 1, y - 1); // 1부터 N까지의 정점 => 0부터 N-1까지
        }
        visited = new boolean[N]; // 방문 기록 저장 배열(0부터 N-1까지)
        int cnt = 0; // 연결 요소 개수

        for(int i = 0; i < N; i++) {
            if(visited[i])
                continue;
            cnt++;
            DFS(i);
        }
        System.out.print(cnt);
    }

    static void DFS(int now) {
        visited[now] = true;
        for(Integer i : graph.get(now))
            if(!visited[i])
                DFS(i);
    }

    static void add(ArrayList<ArrayList<Integer>> graph, int x, int y) { // 양방향 연결
        graph.get(x).add(y);
        graph.get(y).add(x);
    }
}

방향이 없는 그래프이기 때문에 양방향으로 연결해주어야 한다.