https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1
Java
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 사용한 알고리즘 : 스택 풀이전략 1. 탑의 높이 입력이 들어올 때마다 입력 값이 stack의 top에 저장된 값보다 크면, 기존 stack에서 top 원소가 더 큰게 있을 때까지 pop하고 입력 값이 stack의 top에 저장된 값보다 작으면, stack의 top 인덱스를 resut에 저장하고 기존 stack의 원소들을 유지한다. 2. stack에 현재 입력값을 push 하고 1번 과정을..
https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 사용한 알고리즘 : DFS 풀이전략 싸이클이 발생하는 노드들을 모아 오름차순으로 출력해주면 되는 문제다. 1. DFS를 통해 각 노드마다 싸이클이 발생하는지 판단한다. - DFS 탐색 중, 탐색의 첫 번째 노드와 동일한 노드로 탐색을 하게 되면 싸이클이다. 2. 싸이클이 발생하면 탐색과정의 모든 노드 번호들을 TreeSet에 삽입한다. 3. 첫번째 노드부터 마지막 노드까지 2번 ..
https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 사용한 알고리즘 : 투 포인터 풀이전략 1. 문자열의 시작점 인덱스를 start, 끝점 인덱스를 end로 둔다. 2. start 인덱스에 해당하는 문자와, end 인덱스에 해당하는 문자를 비교하여 일치하면 ++start, --end를 수행한다. 3. 만약 start 인덱스에 해당하는 문자와, end 인덱스에 해당하는 문자가 일치하지 않는다면 count를 1 증가시키고 start를 1 증가시켜 문자 하나를 제외한 경우와 e..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 사용한 알고리즘: BFS 풀이전략 문제를 풀기 앞서 이분 그래프가 어떤 구조인지 알고 있어야 문제 풀이가 가능하다. 위와 같은 그래프가 있을 때, 인접한 노드끼리 서로 다른 색을 지니는 그래프를 이분 그래프라고 한다. 노드끼리 모두 연결되어 있지 않아도, 서로 인접한 노드끼리만 다른 색으로 구분될 수 있어도 이분그래프다. 이런 이분 그래프의 성질을 이용하여 BFS를 사용하면 문제를 풀 수 있..
목표 xml 대신 Java 코드를 통해 설정파일을 작성한다. 기존 xml 설정 파일 작성방식 위와 같이 xml로 작성된 설정파일을 Java 코드로 만들면 아래와 같다. Java 코드로 작성한 설정 파일 @ComponentScan("spring.di.ui") @Configuration public class NewlecDIConfig { @Bean public Exam exam() { return new NewlecExam(); } } @Configuration : Java로 작성한 설정 파일임을 알림 @ComponentSacn("spring.di.ui") = @Bean public Exam exam(){return new NewlecExam()} = 으로 똑같이 작성할 수 있다. @Bean 어노테이션은 ..
https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 사용한 알고리즘: 플로이드 워셜(Floyd Warshall) 풀이전략 플로이드 워셜 알고리즘을 사용하여 모든 출발지에서 도착지까지의 최단 거리를 구한다. 단, 기존 플로이드 워셜 알고리즘에서는 자기 자신에게 가는 거리를 0으로 두고 알고리즘을 실행했지만 이 문제에서는 거리가 아닌 경로의 유무 판단이 중요 쟁점이기 때문에 모든 배열의 원소를 INF(무한)으로 초기설정한다. 그리고 입력에서 1로 경로가 있는 경우에만 배열 ..
https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 사용한 알고리즘 : 플로이드 워셜 알고리즘(Floyd Warshall) 풀이전략 전형적인 플로이드 워셜 알고리즘을 사용한 문제이다. 플로이드 워셜은 A에서 B로 가는 거리를 D(AB)라고 할 때, 다른 노드 K를 지나쳐 가는 것과 현재 거리를 비교하여 더 짧은 거리를 D(AB)에 저장시키는 알고리즘이다. 예로 D(AB) = Math.min(D(AB),D(AK)+D(KB))처럼 특정 노드 K를..
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 사용한 알고리즘 : 데익스트라(Dijkstra) 풀이전략 전형적인 데익스트라 알고리즘을 사용한 최단거리 문제이다. 다만 계속해서 시간초과가 발생해서 골머리였는데, 이유는 ArrayList가 아닌 LinkedList 사용 때문이었다. ArrayList / LinkedList 검색 최대 시간 복잡도 ==> O(1) / O(..
https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 사용한 알고리즘 : 데익스트라(Dijkstra) 풀이전략 전형적인 데익스트라 알고리즘 문제이다. 우선순위 큐를 사용하지 않고, 각 노드에서 최단거리 노드를 구할 때 함수를 사용하면 시간초과가 발생했다. 따라서 우선순위 큐를 구현하고 거리에 따라 오름차순 정렬되도록 해야한다. 1. 시작 노드를 우선순위 큐에 먼저 inqueue하고 해당 노드를 방문처리, dis..
