https://www.acmicpc.net/problem/25585 25585번: 86 ─에이티식스─ 1 첫 번째 줄에 전장의 크기 $N$이 주어진다. 전장은 $N \times N$ 크기 좌표로 이루어져 있다. 다음 $N$개의 줄에는 전장의 정보가 주어진다. 각 줄마다 $N$개의 좌표 정보가 주어지며 0은 빈칸, 1은 레기 www.acmicpc.net 난이도 : 골드 5 태그 : 백트래킹, 브루트포스 설명 대각선으로만 이동할 수 있는 장기말로, 다른 적들을 다 잡을 수 있는지, 잡을 수 있다면 얼마만큼의 시간이 소요되는지 구하는 문제입니다. 처음엔 n이 꽤 작길래, 대각선 방향으로 이동하는 모든 경우의 수를 다 확인하였으나, 당연하게도 시간초과. n이 최대 100이여도 n이 1 만큼 증가할때마다 말도안..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 난이도 : 실버 2 태그 : 브루트포스, 백트래킹 설명 배열의 순서를 적절히 섞어 위 식의 최댓값을 찾는 문제였습니다. 처음에는 위 식을 |A[0] - A[1]| + |A[2] - A[3]| 과 같이 두 식의 차이의 절대값 인줄 알고 그리디로 접근하면 되겠지? 싶었는데 |A[0] - A[1]| + |A[1] - A[2]| 였습니다 ㅎㅎ; 😭 흠... 그럼 두 번째 방법으로, 백트래킹으로 모든 경우의 수를 탐색하..

https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 난이도 : 골드 2 태그 : 브루트포스, 백트래킹 설명 처음엔 그리디적으로 생각해, 큰 색종이 부터 붙이면 되겠구나! 생각했으나, 6x6의 경우, 3x3 색종이를 쓸 경우 4장이면 가능한 것에 비해, 5x5를 쓸 경우, 5x5 색종이 한개와, 1x1 색종이 11장이 필요하기 때문에, 색종이 개수를 초과하여, 붙이는게 불가능합니다. 흠... 그리디는 아니겠고, 그럼 백트래킹 + 브루트포스인..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 난이도 : 골드 4 태그 : 구현, 백트래킹, 브루트포스, 시뮬레이션 설명 기업 코테에서 정말 자주 나오는 문제 유형은 뭘까요? 사실 저도 기업코테를 많이 본 사람은 아니지만, 구현은 일단 안나온 적은 없었던 것 같고, DFS/BFS/백트래킹도 정말 굉장히 자주 나왔던 것 같습니다. 구현 문제 중에서도 시뮬레이션 역시 단골 유형 중 하나인 것 같습니다. 분리집합/다익스트라 등도 좀 있던..

https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 난이도 : 골드 5 태그 : 수학, 정수론, 백트래킹, 소수 판정 설명 백트래킹 + 소수판정 문제입니다. 백트래킹으로 수열을 구한 뒤, 수열을 숫자로 바꿔 해당 숫자가 소수인지 판단하였습니다. 소스코드 시간초과 var n = -1 lateinit var nums: Array val sb = StringBuilder() fun main() { n = readln().toInt() nums..

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 난이도 : 골드 3 태그 : 수학, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 조합론, 백트래킹 설명 DFS를 사용해 풀면 되겠네! 라는 생각이 바로 떠올랐지만, 생각해보니 순수 DFS만으로 풀기에는 조금 무리가 있었습니다. 결국... 이게 뭐지??? 하는 생각에 태그를 펼쳐봤습니다. 그렇습니다. 이 문제는 1. 5 x 5 = 25명의 자리 중 7명을 뽑고(..

https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 난이도 : 실버 3 태그 : 백트래킹 설명 N과 M 시리즈. 대망의 마지막 문제입니다. 9번의 소스에 10, 11번의 변형이 가해진 문제네요. 소스코드 import java.io.BufferedReader import java.io.InputStreamReader import java.util.StringTokenizer lateinit var arr: Array var n = 0 var m ..

https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 난이도 : 실버 3 태그 : 백트래킹 설명 N과 M 시리즈. 11번째 문제입니다. 이번에도 9번의 소스에 약간의 변형을 가해 풀어보겠습니다. 소스코드 import java.io.BufferedReader import java.io.InputStreamReader import java.util.* lateinit var arr: Array var n = 0 var m = 0 val sb = St..

https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 난이도 : 실버 3 태그 : 백트래킹 설명 N과 M 시리즈 10번째 문제입니다. 이제 이 시리즈도 얼마 남지 않았군요. 다들 예상하셨듯, 9번 문제에 2, 6번과 같 변형을 가한 문제입니다. 소스코드 import java.io.BufferedReader import java.io.InputStreamReader import java.util.StringTokenizer lateinit var ..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 난이도 : 실버 3 태그 : 백트래킹 설명 이번엔 새로운 변화구입니다. 5번의 문제 처럼 배열이 주어지지만, 5~8번은 n개의 자연수가 서로 다른 수 였습니다. 하지만 이번 문제부터는 중복될 수 있는 n개의 자연수가 주어집니다. 소스코드 import java.io.BufferedReader import java.io.InputStreamReader import java.util.StringTok..