1. 문제 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 2. 풀이 뭔가 주어진 수열의 연속된 부분합의 최대를 구하는 것이 수학적인 공식으로 해결할 수 있을 것 같기도 한데... 귀찮아서 백트래킹으로 풀었읍니다... 백트래킹을 시도할 수 있는 근거는, 문제에서 주어진 정수 배열의 범위가 최대 8로 8!의 경우의 수만 해결해주면 되기 때문이다. 따라서 배열에서 중복되지 않는 순열을 만드는 기법을 이용해 합을 산정해주었다. 이 때 매개변수로 이전 idx를 넘겨줌으로써 연속된 idx들의 합을 계속해서 더해나갈 수 있도록 처리하였..

1. 문제 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 2. 풀이 구현 문제이지만 주사위를 굴리는 방법을 구현하는 과정에서 실수를 범하기 좋은 유형의 문제다. 하지만 문제는 꽤나 단순하게 접근할 수 있는데, 그 이유는 주사위 6면에 대해서는 1차원 배열로 선언이 가능하며 네 방위(동, 서, 남, 북)로 움직이는 행위만 잘 정의해주면 되기 때문이다. 따라서, 각 배열의 index에 대해 위치를 사전에 정의해두고, 이를 네 방면으로 굴렸을 때 인..

1. 문제 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 2. 풀이 해당 문제를 요약하자면 주어진 수열에서 연속된 부분수열의 합이 C를 만족하는 경우의 수를 찾으라는 내용이다. 가장 단편적인 방법으로는 brute-force로 해당 문제를 해결해도 될 것으로 보인다. 하지만 연속된 부분수열의 합을 매번 구해야 한다면 O(N²)의 시간복잡도가 발생할 것이다. 그렇다면 부분 수열의 합을 어떻게 하면 효율적으로 계산할 수 있을까를 먼저 해결해보자. 1.1 누적합 연속된 부분..

1. 문제 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 2. 풀이 단순한 구현 문제이지만, 로봇의 동작이 다소 복잡하게 정의되어 있어 난이도가 올라간 것으로 보인다. 하지만 문제에서 정의한 청소기의 동작 방식을 순차적으로 잘 구현만 한다면, 큰 어려움은 없다. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우, 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌..

1. 문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 2. 풀이 전형적인 백트래킹 유형의 문제로, 백트래킹(backtracking)을 이용한 순열만들기 유형의 문제라고 보면 된다. 그렇다면 중요한 것은 어떠한 조건을 만족시켜야 하는가를 잘 정의해야 하며, 해당 조건들은 아래와 같다. 모음 1개 이상 자음 2개 이상 사전 순으로 출력 길이 C의 문자열 생성 사전 순으로 출력해야 하는 조건이 있기 때문에 입력 받은 문자 배열을 오름차순 정렬을 먼저 해주고, 모음 및 자음의 개수는 backtracking 메서드의 ..

1. 문제 2642번: 전개도 입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지의 정수들이 여섯 개 있고, 숫자 사이에는 빈칸이 하나씩 있다. 1에서 6까지의 숫자는 전개도의 면을 나타내고, 0은 전개도의 바깥 부분을 나 www.acmicpc.net 2. 풀이 문제에서 요구하는 것은 간단하다. 전개도가 주어졌을 때, 정육면체를 만들 수 있는 전개도인지 판단하고 가능하다면 숫자 1이 써져 있는 면의 반대 면에 위치한 숫자를 출력하는 것이다. 그렇다면 당연하게도 우리는 주어진 전개도가 정육면체를 만들 수 있는지 여부를 어떻게 판단할 것인가를 고민해야 한다. 2.1 정육면체 전개도의 종류 먼저 정육면체를 만들 수 있는 전개도의 종류는 아래 이미지와 같이 총 11가지가 있다. 그럼 첫 번째로, 11가지 유..

1. 백트래킹? DFS? 백트래킹과 DFS는 어떻게 보면 분리하기가 애매한 개념이다. 굳이 분리해서 의미를 부여하자면 끝까지 가느냐 돌아오느냐로 간단하게 생각해볼 수 있다. DFS 역시 재귀를 통해서 구현하므로 시작 기점으로 돌아오는 개념이 들어가 있기는 하지만, 백트래킹의 경우 현재 가는 길이 더 이상의 해가 아니라고 판단되면 되돌아오는 것을 의미한다. 간단하게 DFS 개념을 정리하자면, 가능한 모든 경로를 깊이 우선으로 탐색하는 것을 의미한다. DFS에 대한 자세한 내용은 아래 게시글을 통해 알아보자! DFS(Depth-First Search) + BFS 복습 깊이 우선 탐색(DFS, Depth-First Search)을 알아보기 이전에 그래프에 대한 개념을 이해해야 하므로, 먼저 아래 포스팅을 참고..

1. 문제 20304번: 비밀번호 제작 서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부 www.acmicpc.net 2. 풀이 결과적으로 어떤 답을 만들어내야 하는가가 다소 헷갈릴 수 있는 문제의 유형이라 생각한다. 그 중 먼저 문제의 핵심인 안전거리와 안전도를 판단하는 방법을 알아본다. 2.1 안전거리와 안전도 3, 4 두 가지의 비밀번호가 입력된 적 있을 때, 2라는 비밀번호를 설정했을 때의 안전거리를 알아보자. 먼저 2, 3, 4를 이진수로 변환하면 아래와 같다. 3: 0011 4: 0100 2: 0010 (2,3)의 경우 서로다른 비트가 한 개이기 때문에 안전거리는..

1. 문제 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 2. 풀이 본 문제는 크게 두 가지 방법으로 풀이가 가능하다. 다만, 두 가지 경우 모두 사전 작업이 한 가지 필요한데 이는 바로 주어진 쿼리가 수행 가능한 쿼리인지 먼저 확인하는 것이다. 여기서 수행 가능한 쿼리란 어떤 것을 의미하는 것일까? 문제에서 주어진 순열의 인덱스가 과연 존재하는 인덱스인지 검증이 필요하다는 것이다. 서로 다른 문자로 이루어진 문자열로 순열을 만드는 방법은 (순열의 길이)! 이다. 즉, 입력 받은 순열의 길이 팩토리얼 값을 가지고..

1. 문제 14534번: String Permutation First line of the input contains T (1 ≤ T ≤ 200), the number of test cases. For each test case, there will a string of characters, L (1 ≤ L ≤ 5). www.acmicpc.net 2. 풀이 백트래킹의 가장 기본적인 유형인 순열 만들기 문제다. 집합의 요소를 사용했는지를 판단할 boolean 배열을 선언하여, 각 요소들의 사용여부를 변경해가며 순열을 만들면 해결할 수 있다. 다만 현재 문제는 조합(Combination)이 아닌 순열(Permutation)이므로, 백트래킹을 할 재귀 함수 내에서 시작지점은 항상 첫 요소로 설정해야 한다. 시..