https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 완전탐색으로 CCTV의 방향이 될 수 있는 모든 경우의 수를 구하여 그 중 사각지대가 최소인 경우의 크기를 구하였다. 완전탐색(재귀)로 모든 경우의 수를 구하므로 다음 변수들을 전역변수로 선언하였다. - 사무실 크기 n, m - 사무질 정보를 저장하는 rooms[n][m]을 생성 - 사각지대의 최소 크기를 저장하는 minUnwatchRoomCnt를 64로 초기화 - CCTV의 번호..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 다음과 같은 흐름으로 문제를 풀었다. 1. 조합(mC3)을 사용하여 궁수 3명의 위치를 정한다. 2. 각 위치에 따라 처치하는 적의 수를 구한다. 2-1. 각 궁수마다 처치할 적을 선택한다. 2-2. 적을 처치한다. 2-3. 적을 한 칸 아래로 이동한다. 모든 적을 처치하거나, 적이 성으로 모두 이동할 때까지 2-1 ~ 2-3을 반복한다. 3. 모든 경우의 수에서 처치하는 적의 최대 수를 구한다. ma..

https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 풀이 DFS(재귀함수)를 사용하여 풀이하였다. main() 로직 1. 수식에서 숫자와 연산자를 구분하여 각각 ArrayList numbers, ArrayList operators에 저장한다. 2. 재귀함수를 호출하여 DFS를 수행한다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = In..

https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 - 완전탐색 완전탐색으로 만들 수 있는 모든 문자열을 순서에 맞게 탐색하며 카운팅하고, 정답을 찾으면 탐색을 모두 중단한다. 코드 class Solution { static char[] alphabet = {'A', 'E', 'I', 'O', 'U'}; static int cnt = 0; // 정답 static boolean flag; // 정답을 찾았을 때 true로 변경 public in..

https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 - 순열(DFS) 던전을 탐험할 수 있는 모든 경우를 구하고, 탐험한 던전 수를 구한다. 탐험한 던전 수가 모든 던전의 개수와 같다면 더 이상 탐색하지 않는다. 던전을 탐험할 수 있는 모든 경우는 순열(DFS)을 사용하여 구했다. 코드 class Solution { static int size; static int[] pm; static boolean[] check; static boolea..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구해야 한다. 즉, 최댓값을 구해야 하므로 벽 3개를 세울 수 있는 모든 경우의 수를 구해 그 중 안전 영역 크기의 최댓값을 구해야 한다. 문제를 풀기위해 전체 로직을 3단계로 나누었다. 1. 빈 칸 중 3개 선택(DFS/완전탐색) 2. 바이러스 전파(BFS or DFS) 3. 안전영역 크기 세기(이중 for문) 먼저 main 함수에서..

https://www.acmicpc.net/problem/20164 20164번: 홀수 홀릭 호석 호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 www.acmicpc.net 풀이 위 문제는 다음과 같은 연산을 반복한다. 입력받은 숫자 -> 홀수 개수 카운트 숫자를 짜름 -> 짜른 각각의 숫자를 모두 더한 숫자 -> 홀수 개수 카운트한 다음 이전 카운트에 더함 숫자의 홀수 개수를 카운트한 다음 이전 카운트에 더하는 로직이 반복되므로, 재귀호출 또는 반복문을 사용해야 한다. 또한 만들 수 있는 모든 경우의 수를 구해 그중 최솟값과 최댓값을 구해야 한다. 즉, 재귀호출을 ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.www.acmicpc.net풀이상담을 할 수 있는 가능한 모든 경우를 구한 다음 그 중에서 최대 수익을 구해야 한다. 예시를 들어 설명하겠다. 먼저 1일에 상담을 한다고 가정했을 경우(현재 수익 10), 2, 3일은 할 수 없으므로 4일로 넘어간다. 4일에 상담을 한다고 가정하면(현재 수익 30), 5일로 넘어가고 또 이때 5일에 상담을 한다고 가정하면(현재 수익 45), 7일로 넘어간다. 7일에는 상담을 할 수 없으므로 총 수익은 45가 된다.총 수익을 구한 다음 가장 최근 분기였던 5일째로 돌아간다. 5일에 상담을 하지 않는다고 가정하면(현재 수익 30), 6일..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 DFS를 사용하여 스도쿠의 빈 칸에 모든 수를 집어넣고 각 경우마다 스도쿠가 될 수 있는지 체크한다. 로직 1. 스도쿠의 빈 칸 좌표를 ArrayList points에 넣는다. 2. sudoku(idx:0)을 호출한다. 이 때 idx는 points의 인덱스다. 3. points에서 좌표를 꺼내고, for문으로 1~9까지 해당 좌표에 들어갈 수 있는지 check() 함수를 통해 체크한다. 들어..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 말이 지날 수 있는 최대의 칸 수를 구하기 위해, DFS를 사용해서 모든 경우를 탐색해야 한다. 이 때 같은 알파벳이 적힌 칸을 두 번 지날 수 없으므로, 중복되는 알파벳이 있는지 체크하기 위해 map을 사용한다. 칸을 이동할 때마다 그 칸의 알파벳을 map의 key로 저장하고, 다음 칸으로 이동하기 전 map.containsKey() 메서드를 호출하여 다음 칸의 알파벳이 map에 있..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 문제를 보고 조합을 이용해야겠다는 생각이 들었다. 암호에는 알파벳을 중복하여 사용할 수 없고, 암호를 이루는 알파벳이 증가하는 순서로 배열되어야 한다. 즉, 입력받는 C개의 문자를 배열에 저장하여 알파벳 순으로 정렬하고, 배열 인덱스(0 ~ C-1)의 모든 조합의 경우의 수를 구하면, 가능성 있는 암호의 모든 경우를 구할 수 있다. 조합은 DFS로 구현한다. 조합을 구현하는 기본 틀은 다음과 같다..