https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 - 전형적인 격자형 그래프 탐색 문제 - 방문배열을 사용하여, 방문하지 않고 배추가 심어져 있는 경우 상하좌우 방문처리하면서 그룹 카운팅 수행 - 가로, 세로 (5≤N≤25) 길이가 최대인 경우 시간복잡도는 O(N^2) = O(625) 이므로 Integer 처리 가능 제출 코드 - bfs, dfs 둘 다 정의 import java.util.*; import java.io.*; public cl..

문제 링크 https://www.acmicpc.net/problem/11724 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 풀이 - 전형적인 그래프 탐색 문제 - 방향없는 그래프 키워드에서 양방향 그래프라 생각하고 인접 리스트에 정점, 간선 데이터 입력 - 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) - 최대 N = 1,000, M = 1000*999/2 = 499500 ..

문제 링크 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 - 전형적인 격자형 그래프 탐색 문제 - 방문 배열과 배추가 심어져 있는 배열을 가지고 그룹 카운트 수행 - 방문하지 않고, 배추가 심어져 있는 경우 카운터를 하나 올리고 상하좌우 탐색하면서 방문처리 - Test Case별 시간복잡도 : O(N^2) 제출 코드 DFS의 경우 import java.io.*; import java.util.*; public class Main { static St..

문제 링크 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 - 전형적인 격자형 그래프 탐색 문제 - 테스트 케이스별로 초기화 및 섬의 개수 카운팅 수행 - 정점에서 움직일 수 있는 방향은 8가지 (상하좌우, 대각선 양방향) - N은 최대 50 - 시간 복잡도 : O(N^2) , 테스트 케이스별로 O(2500) 씩 걸림 w, h 입력 값이 조금 헷갈리고, 테스트 케이스 처리만 번거로웠지 나머지는 그래프 탐색 기본 유형과 동일했음 제출 ..

문제 링크 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 - 첫번째 줄에 맵의 크기 R, C 주어짐 (최대 50) - 비어있는 곳은 '.' / 물이 차있는 지역은 '*' / 돌은 'X' / 비버의 굴은 'D' / 고슴도치의 위치는 'S' 로 표시 - 격자형 그래프 탐색 문제 (상하좌우) - 물 '*'은 매 분마다 비어있는 인접 칸으로 확장 - 물(*)과 고슴도치(S)는 돌을 통과할 수 없음 - 고슴도치(S)는 물(*)이 차있는 구역으로 이동할 수 없..

문제 링크 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 - 현재 위치, 상태(숫자)를 정점으로 보고 +1 , -1, *2 를 간선이라 정의하여 문제 풀이 - BFS 문제 풀이 - N = 100,000 이고, K = 0 인 경우 -1 을 10만번 하면 K에 도착함 => 최대치 100,000 이므로 Integer 풀이 가능 제출 코드 import java.util.*; import java.io.*; public..

문제 링크 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 - 첫번째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8) - 0은 빈 칸, 1은 벽, 2는 바이러스 위치 아래의 절차와 같이 진행한다 1) 빈칸(0) 위치에 벽을 3개 세운다 2) 바이러스를 전파(방문)한다 3) 바이러스가 전파(방문)하지 않은 빈칸(0) 영역을 카운팅하여 최대 결과값을 찾는다. 최대 맵의 크기가 8 * 8 = 64일때 3개의 벽을 찾는 조합의 수 ..

문제 링크 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 풀이 - 문제에는 표현되어 있지 않지만, 물통의 상태(=정점), 물을 붙는 행위 (=간선) 으로 정의하여 풀어야 하는 그래프 문제 1) 입력으로 A B C 물통의 사이즈가 정해짐 2) 초기 C 물통만 가득찬 상태이고, 나머지 비어있는 상태에서 시작 3) 각각 다른 물통에 물을 붙는 행위를 하여 A = 0 일때 C 물통의 상태(결과)값을 구해 오름차순으로 출력 이때 정..

문제 링크 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 풀이 - 시간복잡도 O(NlogN) = 정렬 O(NlogN) 후 투 포인터 O(N) 수행 - Integer 범위 내이긴 하지만, 초기화시 일부 long 선언 처리 - M 만큼의 차이가 날 때까지 R을 먼저 탐색, A[R] - A[L] > M 조건 성립시 결과값 갱신 (최소값) 제출 코드 import java.util.*; import java.io.*; public ..

문제 링크 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 풀이 - 시간복잡도 O(N) - 1 (라이언 인형) 인 경우에만 카운팅 처리를 해주고, K개이상이 되는 연속된 인형의 집합의 길이는 L, R범위로 측정 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, K; static int[] A; static void input() throws Excep..

문제 링크 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 - 정렬 후 투 포인터 로직 수행 - 시간 복잡도 : O(NlogN) - 배열 순차적으로 순회하여 기준 값과 나머지 영역에서 투 포인터로 두 값을 정하고 다 더했을 때 0에 가까운 최대 값을 구하면 됨 참고 [BOJ 2470] 두용액 (Java, 투 포인터) [BOJ 1253] 좋다 (Java, 투 포인터) 제출 코드 - 입력 배열 A 의 데이터 타입을 lon..

문제 링크 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 풀이 - 알파벳(26자) 카운팅 배열을 활용하여 투포인터 문제 풀이 - 시간복잡도는 O(N) *알파벳 인덱스 구하기 int index = TEXT.char(i) - 'a'; 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, CNT; static String TEXT; static int[] ALPHABET ..

문제 링크 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 - 두 용액 문제 풀이 방법을 응용하여 풀이 - 시간 복잡도 O(NlogN) - 순차 조회하면서 해당 값을 다른 두 수의 합으로 만들 수 있는지 확인 (이때 탐색과정에서 자기자신의 경우 제외, targetIdx) 제출 코드 import java.util.*; import java.io.*; public class Main { static int N; static int[] A; static void input..

문제 링크 https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 풀이 - 투 포인트 기법과 카운팅 배열을 활용하여 1 ~ N 까지의 모든 경우의 수 합을 더하면 됨 - 시간복잡도 O(N) 이때 최대값의 경우 1 2 3 ... 100,000 1 2 3 ... 100,000 1 ~ 100,000까지의 합을 나타내기 때문에 100000(99999) / 2 = 대략 50억이기 때문에 long으로 풀이 해야 함 L = 1인 경우 100,000 L = 2인 경우 99..

문제 링크 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 - 투 포인터 문제 - 시간 복잡도 O(N) - 정답의 최대 길이는 100,000 , 구하려는 S의 최대는 10^9 이므로 Integer로 풀이 가능 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, S; static int[] NUMBERS; static void input()..

문제 링크 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 - 투 포인터로 문제 풀이 (이진탐색으로 풀이 가능하나 개념적으로 조금 어려움) - 두 용액을 더 했을 때 0에 가까운 두 수를 구하는 문제 - 양 끝에서 투 포인터를 시작해서 서로를 향해 이동 - sum 의 값이 양수인 경우 R을 감소, 음수인 경우 L을 증가 0 1 2 3 4 -99 -2 -1 4 98 -99, 98 = -1 이므로 L증가 -2..

문제 링크 https://www.acmicpc.net/problem/13702 13702번: 이상한 술집 프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용 www.acmicpc.net 풀이 - 이진탐색(매개변수 탐색) 문제 - 시간복잡도 O(NlogN) - long 타입 변수를 사용해야 하는 경우 있음 뒤집은 문제 용량(ml) 을 정했을 때, 친구(K)명에 막걸리를 골고루 분배 가능한가 ? 이때 용량(ml)는 최대인가? 부등호 헷갈리는 경우 주전자(N) 1개 이고 그 안에 21억ml가 담겨 있고, 친구(K) 100만명 있을 때 - 1000ml 로 나눌 경우 주전자에 1..

문제 링크 https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 풀이 - 이진탐색(매개변수 탐색) 문제 - 시간복잡도 O(NlogN) - 굴다리 길이 N (1 ≤ N ≤ 100,000) 일 때 0번 위치에 가로등 한 개 세울 경우 H는 100,000(최대)이 되야 모두 비추는게 가능하므로 Integer로 연산가능 뒤집은 문제 가로등 높이 H일 때 굴다리 길이 N을 모두 비추는게 가능한가? 가능한 경우 가로등 높이 H는 최소 높이인가? 예제 입력 1 5 ..