문제 링크 : 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/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보다 작다면 -> 이 경우에는 스택연산으로 해당 수열을 만들..

다형성 개념다형성의 특징유연하고 변경에 용이하다.역할과 구현으로 세상을 구분한다.자동차 예시 위의 그림은 다형성을 설명할때 가장 흔하게 등장하는 예시중 하나인 자동차 예시입니다. 자동차역할을 인터페이스라고 한다면 k3, 아반테, 테슬라 모델3는 각각 인터페이스(자동차 역할)의 구현체(자동차)라고 할 수 있습니다.운전자는 차마다 별도의 운전법을 배울 필요 없이 여러종류의 차를 운전할 수 있다. 운전자는 각각의 차량이 아닌 자동차의 역할(운전)에 의존한다.이것이 다형성의 핵심입니다.운전자를 클라이언트라고 하고, 자동차를 서버라고 한다면새로운 자동차(다른 서버)가 나왔다고 해서운전자(클라이언트)가 면허를 다시 따야할 필요(클라이언트 수정)는 없습니다.   공연 예시또 다른 예시인 공연 예시를 살펴보도록 하겠습..