문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 알고리즘 C++로 이런 기초 BFS 문제를 많이 풀어봤으나 JAVA로는 처음 풀어서 큐에 저장하는 방식이나 스트링을 문자열로 바꾸고 이를 다시 이차원 배열에 저장하는 과정이 조금 까다로웠다. 알게된 점을 정리하자면, 먼저 BFS를 진행할 때 큐에 해당 좌표를 삽입하는데, 이때 Queue q = new LinkedList(); 이처럼 int[]의 형식으로 좌표를 저장하게 된다. 그리고 이 큐에 push를 진행할 때면 q.ad..

문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 알고리즘 BFS, DFS 두 가지 방식으로 해결할 수 있다. BFS, DFS 두 가지의 풀이를 작성해 두었다. arr을 전역변수로 선언하고 초기화하고 할당하는게 아직도 헷갈리지만, new이후 ArrayList()를 하는 것이 객체를 생성하는 것이라고 생각하니 조금 더 이해가 잘 되는 것 같다. 우선 값을 입력받고 arr에 값을 저장한다. 그리고 bfs나 dfs를 모든 정점에서 진행할 필요 없이 1..

문제 https://acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 알고리즘 DFS 코드 package algo0317; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class B13023_ABCDE { static int n, m; static StringBuilder sb = new StringBuilder(); static ..

문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 알고리즘 이진 탐색을 이용한다. 중간 값을 찾은 뒤, 찾아야하는 수가 중간 값보다 크다면 뒷쪽을 탐색하고, 작다면 앞쪽을 탐색한다. 뒷쪽을 탐색하기 위해서는 시작점을 중간값 + 1로 옮기고 앞쪽을 탐색하기 위해서는 끝점을 중간값 - 1로 옮겨준다. 코드 package algo0317; import java.io.BufferedReader; im..

문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 알고리즘 그리디 서로 겹치지 않는 회의에 대해 종료시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아진다 끝나는 시간을 기준으로 오름차순 정렬을 진행한다. 이때 끝나는 시간이 동일하다면 시작 시작이 더 빠른 것이 앞쪽으로 오게된다. 코드1 package algo0317; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.Str..

문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 설명 자바로 dfs를 구현하는 것은 처음인데, 이때 ArrayList를 활용했다. ArrayList를 배열형태로 만들어서 인접리스트를 구현하였다. 우선 인접 리스트를 초기화 한 뒤, 인접 리스트에 그래프를 저장한다. 이때 양방향이기 때문에(방향이 없는 그래프) a[s].add(e)와 a[e].add(s)를 둘 다 추가해 주었다. 방문하지 않은 경우 카운팅을 하고 dfs를 재귀 방식으로 호출한다. ..

문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 설명 N과 M(1)이 백트래킹을 이용한 순열 문제라면 N과 M(2)는 백트래킹을 이용한 조합 문제이다. 조합은 순서가 상관없다. 또한 오름차순으로 구하게되면 이전에 했던 문제와 달리 중복 체크가 필요 없다. 처음에 combination(0,1)을 호출하는데, 이후에는 combination(cnt+1, i+1)을 호출한다. 오름차순으로 구하면 중복체크 하지 않아도 되므로, visited 배열..

문제 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 가장 기본적인 백트래킹 문제이다. func라는 함수의 역할은, k번째 수를 정하는 것이다. k번째 수를 정하고, k+1의 수를 재귀적으로 정해준다. 코드 package algo0314; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class B15649_N과M1 {..

https://www.acmicpc.net/problem/9742 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 백트래킹을 사용한 문제. 테케 갯수가 정해져 있지 않기에 읽은 라인이 null일때까지 반복 package algo0314; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class B9742_순열 { static..

12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 슬라이딩 윈도우 사용! 첫 슬라이딩 윈도우 생성 - 입력받은 문자열의 0~p-1번째 요소에 A,C,G,T가 있는지 확인 후 정답 계산 첫 슬라이딩 윈도우 생성 이후 s-p개의 부문 문자열 생성 가능 → for문을 통해 모든 부분 문자열 검사. 한 칸씩 이동하면서 검사 가능. 이전 부분문자열의 시작은 빠지고, 추가될 부분은 더해져야함. idx = i (이전 부분 문자열의 시작 인덱스), idx = i+p (이전 부분 문자열의 시작 인덱스 + ..