매일 조금씩

문제 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 완전탐색 문제로 재귀 함수를 사용하여 가능한 조합을 구한다. k개 수에서 순서 상관 없이, 중복 없이 6개의 수를 뽑는다. 소스코드 package bruteforce; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.Output..

문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 다익스트라 알고리즘 사용 최소 벽 파괴 횟수를 갱신하면서 탐색 소스코드 package dijkstra; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class BOJ..

문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 좌표 영역을 칠하고, DFS로 빈 공간의 개수와 넓이를 구한다. 영역 칸의 개수를 구해야 하기 때문에, 입력된 좌표를 그대로 사용하면 정확한 답을 구할 수 없다.- 이를 해결하기 위해, 칠할 영역 시작 좌표의 x, y 좌표는 +1을 해주어서 좌표의 기준을 우측 대각선 위로 동일하게 맞춰주었다. ex) 칠해야 할 영역의 시작 좌표가 0, 0 일 경우 1, 1로 변경해서..

문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 풀이 분할정복 문제이다. 유사 문제 2021.11.16 - [Problem Solving/BOJ] - [BOJ 2630] 색종이 만들기 (Java) 2021.11.23 - [Problem Solving/Programmers] - [프로그래머스] 쿼드 압축 후 개수 세기 (Java) 2021.11.17 - [Problem Solving/BOJ] - [BOJ 1992] 쿼드트리 (Jav..

문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 연합을 모두 찾은 후에 인구이동이 되어야 하므로, 찾은 연합을 저장해 둘 자료 구조를 생성한다. 1. 맵을 순회하면서 DFS로 연합을 찾아서 저장한다. 2. 연합을 모두 찾은 후에, 연합 내 총 인구/나라 개수를 계산하여 각 나라의 인구를 갱신한다. 이 두 과정을 반복 한다. 연합을 찾았는데 연합의 개수가 0개인 경우 Loop를 종료한다. 반복 횟수를 출력한다. 소스코드 ..

문제 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 풀이 가로수 사이의 간격을 계산하여 저장한 후 , 간격들의 최대 공약수를 구한다. 가로수의 최대 거리와 가로수의 최소 거리의 차이를 구한 후 최대 공약수로 나눠준다. (유클리드 호제법 사용) 양 끝이 모두 포함되므로, 나눈 값에 1을 더한 값이 가로수의 개수가 된다. 이 개수에서 이미 심어져 있는 가로수 개수를 뺀 값이 정답이 된다. 소스코드 package math; import ja..

문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 삼성 문제의 경우 BruteForce 유형이 많은 것 같다. 해당 문제는 각 감시 카메라 타입 별로 가능한 감시 방향을 미리 정의해 놓은 후, 모든 경우의 수를 조합하여 사각 지대의 최소 개수를 구한다. 1. 감시카메라 타입 별로 가능한 방향을 미리 정의한다. 2. 방향에 따른 좌표 증/감분을 미리 정의한다. static HashMap possibleDir = new Hash..

문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 1. 진출 방향에 따른 x, y 좌표 증가분을 미리 정의해 둔다. 2. 현재 파이프의 방향에 따라 진출 가능한 방향을 미리 정의해둔다. static HashMap dir = new HashMap(){{ put('V', new int[]{1, 0}); put('H', new int[]{0, 1}); put('D', new int[]{1, 1}); }}; stati..

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 문제를 대충 읽고 풀다보니 여기 저기 보수 공사가 많이 필요해서 코드가 지저분해졌다. 해당 문제의 기본 접근 방법은 BFS이다. 일단, 먹을 수 있는 물고기가 있는지 체크한다. 만약 있다면 BFS를 진행한다. BFS를 진행하면서 핵심 포인트는, 먹을 수 있는 물고기가 등장했을 때 동일 depth에 있는 칸을 체크하여 먹을 수 있는 물고기 좌표를 모두 저장해 놓고 탐색을 종료하는 ..

문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 DFS + BruteForce 강수량 범위가 적기 때문에 완전 탐색으로 구현하였다. 각 강수량마다 safe영역을 구하면서, max값을 갱신 소스코드 package dfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ2468 { pub..