문제 링크 : https://www.acmicpc.net/problem/13023 이 문제는 5개 이상의 정점이 이어져있는지를 묻는 문제이다.모든 경우의 수를 다 봐야 하며 정점(사람의 수) = 최대 2000간선(친구관계의 수) = 최대 2000 이기 때문에 만약 모든 정점을 기준으로 DFS 탐색을 실시한다고 하면 O((2000 + 2000) * 2000)으로 시간복잡도상 충분히 시간 내에 풀 수 있다. 추가로 가지치기를 통해서 연산량을 줄이고단순 DFS를 이용하면 풀 수 있다. package boj;import java.util.*;import java.io.*;public class BOJ13023 { static List> graph = new ArrayList(); static bool..

문제 링크 : https://www.acmicpc.net/problem/2023  이번 문제는 N의 자리의 숫자 중 문제의 조건에 만족하는 소수를 출력하는 문제이다.먼저 문제의 조건을 보면 7331 이라는 소수는 맨 앞인 7, 두 번째 자리까지인 73, 세 번째 자리까지인 733, 전체 7331 모두 소수라는 특징을 가지고 있다. 자기 자신과 1을 제외하고는 나누어지지 않는다는 소수의 특징을 보면 N이 몇이든 맨 앞자리의 수는 2,3,5,7 이 되어야 한다.그다음 숫자부터는 1,3,5,7,9 중 골라야 한다. 따라서 처음에는 2,3,5,7 중에서 그다음에는 1,3,5,7,9 중에서 골라 한 자리씩 추가될 때마다소수인지 아닌지를 미리 확인하면서 가지치기를 하면 시간 안에 풀 수 있다.하지만 처음부터 1,2..

문제 링크 : https://www.acmicpc.net/problem/1377 문제를 접근하면 C++ 을 이용하여 정렬을 하는데 이때 버블 소트 알고리즘을 이용해서 정렬 하였다.위 문제에서는 오름차순 정렬을 하고있다.버블 소트 알고리즘은 배열에서 arr[i] 값과 arr[i+1] 값을 비교하여 만약 arr[i] 값이 더 크다면arr[i]와 arr[i+1] 의 값을 swap 한다. 이런식으로 하나하나 값을 비교하며 정렬하기 때문에정렬에 필요한 시간복잡도는 O(N^2)이 된다. 해당 문제에서 C++ 로 작성된 코드를 보면스왑이 한번도 일어나지 않는경우의 i의 값을 출력하는것을 알 수 있다. 단순히 위의 C++ 코드로 구현된 버블 소트 알고리즘을 자바로 옮겨서 풀 수 있지만문제는 문제의 입력값이 최대 500..

링크 : https://www.acmicpc.net/problem/1874 문제의 이름부터 대놓고 스택 수열 이기 때문에 스택을 이용해서 해결하면 된다.자연수 1부터 N까지 순차적으로 stack에 push 해야 한다는 조건이 있으므로이 부분만 유의하면 된다. 로직을 간단히 생각해보면 자연수를 num = 1; 로 선언하고,주어진 수열을 4,3,6,8,7,5,2,1 이라고 했을때수열을 하나씩 순회하면서 현재 값을 now 라고 한다면 1. stack 이 비어있을땐 num넣고, num++;2. stack의 마지막 값이 now 보다 작다면 num넣고, num++;3. stack의 마지막 값이 now와 같다면 pop();4. stack의 마지막 값이 now보다 작다면 -> 이 경우에는 스택연산으로 해당 수열을 만들..