와드의 블로그

문제두 마리의 백조가 호수에 살고 있습니다. 호수는 행 R, 열 C 크기의 직사각형 모양이며, 물('.')과 빙판('X'), 그리고 백조('L')로 이루어져 있습니다. 매일 빙판은 물과 닿아있는 부분이 녹아서 물로 변합니다. 백조는 오직 물을 따라서 상하좌우로만 이동할 수 있습니다. 며칠이 지나야 두 백조가 서로 만날 수 있는지 구하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 R과 C가 주어집니다. (1 ≤ R, C ≤ 1,500) 둘째 줄부터 R개의 줄에 호수의 상태가 주어집니다.출력: 첫째 줄에 며칠이 지나야 두 백조가 만날 수 있는지 출력합니다.풀이: 2개의 큐(Queue)를 활용한 이어 달리기 BFS 최적화이 문제의 맵 최대 크기는 1,500 × 1,500입니다. 만약 매일 얼음을 녹이고,..

문제비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하는 문제입니다. 숫자 $x$의 범위는 1부터 20까지로 매우 작습니다.add x: S에 $x$를 추가합니다. (이미 있는 경우 무시)remove x: S에서 $x$를 제거합니다. (없는 경우 무시)check x: S에 $x$가 있으면 1을, 없으면 0을 출력합니다.toggle x: S에 $x$가 있으면 제거하고, 없으면 추가합니다.all: S를 {1, 2, ..., 20}으로 바꿉니다.empty: S를 공집합으로 바꿉니다.입력: 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)출력: check 연산이 주어질 때마다 결과를 출력합니다.풀이: 비트마스킹을 활용한 메모리 최적화이 문제의 핵심은 4MB라는 극도로 적은 메..

문제1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있습니다. 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 경로를 계획하려고 합니다. 단, 한 번 갔던 도시로는 다시 갈 수 없습니다. (맨 마지막에 출발 도시로 돌아오는 것 제외) 각 도시간 이동 비용이 주어졌을 때, 가장 적은 비용이 드는 순회 경로를 구하는 프로그램을 작성하는 문제입니다.입력: 도시의 개수 N (2 ≤ N ≤ 10), 비용 행렬 W (비용은 1,000,000 이하, 갈 수 없는 경우 0)출력: 외판원의 순회에 필요한 최소 비용핵심 최적화: 시작점 고정이 문제는 모든 도시를 방문하고 다시 처음으로 돌아오는 사이클(Cycle)을 찾는 문제입니다. 순회 경로가 0..

문제1부터 N까지의 수로 이루어진 순열이 주어졌을 때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 N (1 ≤ N ≤ 10,000)이 주어집니다. 둘째 줄에 순열이 주어집니다.출력: 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력합니다. 만약 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력합니다.풀이: O(N) 시간 복잡도의 수학적 알고리즘 (Next Permutation)N이 최대 10,000이므로 모든 순열을 생성하는 재귀(DFS) 방식은 사용할 수 없습니다. 현재 배열의 상태를 뒤에서부터 훑으며 단 한 번의 순회(O(N))만으로 다음 상태를 유추하는 알고리즘을 적용해야 합니다.알고리즘 단계 분석피벗 지점(i) 찾기: 배열의 뒤에서부터 탐색하..

문제10부터 10까지의 정수로 이루어진 N개의 수열 A가 있습니다. 이 수열의 i번째 수부터 j번째 수까지의 합의 부호(+, -, 0)가 주어질 때, 부호 조건들을 모두 만족하는 수열 A를 찾는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 수열의 크기 N (1 ≤ N ≤ 10)이 주어집니다. 둘째 줄에는 N(N+1)/2 길이의 문자열 형태의 부호 배열이 주어집니다.출력: 부호 조건을 만족하는 수열 A를 공백으로 구분하여 출력합니다. (조건을 만족하는 수열이 여러 개일 경우 아무거나 하나만 출력합니다.)풀이: 백트래킹을 활용한 부분 합 유효성 검사이 문제는 10개의 자리에 -10부터 10까지 21개의 숫자를 무작위로 채우면 21^10 번의 탐색이 필요하여 시간 초과가 발생합니다. 따라서 백트래킹(DFS..

문제축구를 하기 위해 모인 N명을 스타트 팀과 링크 팀으로 나누려고 합니다. 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 합니다. 사람마다 다른 사람과 같은 팀이 되었을 때 더해지는 능력치 S[i][j]가 주어질 때, 스타트 팀의 능력치와 링크 팀의 능력치 차이를 최소로 하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 N (4 ≤ N ≤ 20)이 주어집니다. 둘째 줄부터 N개의 줄에 능력치 배열 S가 주어집니다.출력: 첫째 줄에 스타트 팀과 링크 팀의 능력치 차이의 최솟값을 출력합니다.핵심 차이점: 인원수 제한(N / 2)의 해제이전 문제인 '스타트와 링크'는 N명 중 정확히 N/2명을 뽑아야 했으므로 매개변수로 depth를 넘겨 조합(Combination)을 구했습니다. 하지만 이번 ..

문제상담원으로 일하는 백준이는 퇴사를 앞두고 남은 N일 동안 최대한 많은 상담을 하여 최대 이익을 얻으려고 합니다. 각 상담은 소요되는 시간 T_i와 받을 수 있는 금액 P_i로 이루어져 있습니다. 하루에 하나의 상담만 진행할 수 있으며, 상담이 끝나는 날까지는 다른 상담을 할 수 없습니다. 또한 N+1일째에는 퇴사를 하므로, 상담이 N일을 넘어가는 경우에는 진행할 수 없습니다.입력: 첫째 줄에 N (1 ≤ N ≤ 15)이 주어집니다. 둘째 줄부터 N개의 줄에 T_i와 P_i가 주어집니다. (1 ≤ T_i ≤ 5, 1 ≤ P_i ≤ 1,000)출력: 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력합니다.풀이: 비트마스킹을 활용한 완전 탐색 (Brute Force)상담을 '한다' 또는 '하지 않는다'의..

문제서로 다른 L개의 알파벳 소문자들로 구성된 암호를 추측하는 문제입니다. 암호는 다음과 같은 조건을 만족해야 합니다.최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있습니다.암호를 이루는 알파벳은 오름차순으로 배열되어 있습니다. (예: abc는 가능하지만 bac는 불가능)C개의 문자가 주어졌을 때, 가능성 있는 모든 암호를 사전식으로 출력하는 프로그램을 작성해야 합니다.입력: 첫째 줄에 두 정수 L, C가 주어집니다. (3 ≤ L ≤ C ≤ 15) 둘째 줄에는 C개의 문자들이 공백으로 구분되어 주어집니다.출력: 각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력합니다.풀이: 정렬을 동반한 조합 탐색 및 유효성 검사배열을 정렬하여 탐색 순서를 강제하고, 시작 인덱스..

문제크기가 N×M인 격자판의 각 칸에 정수가 하나씩 적혀 있습니다. 이 격자판에서 칸 K개를 선택하려고 합니다. 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하는 프로그램을 작성하는 문제입니다. 단, 선택한 두 칸이 인접하면 안 됩니다. (상하좌우로 붙어있는 칸은 인접한 칸으로 간주합니다.)입력: 첫째 줄에 N, M, K가 주어집니다. (1 ≤ N, M ≤ 10, 1 ≤ K ≤ min(4, N×M)) 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어집니다. (각 수는 -10,000 이상 10,000 이하)출력: 선택한 칸에 적힌 수를 모두 더한 값의 최댓값을 출력합니다.풀이: 2차원 조합 탐색을 활용한 인접 방지 백트래킹단순히 K개의 칸을 순열로 고르면 겹치는 조합이 너무 많아 시간 초과가 ..

문제1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있습니다.123456789101112131415...이렇게 만들어진 새로운 수는 총 몇 자리 수인지 구하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 N (1 ≤ N ≤ 100,000,000)이 주어집니다.출력: 첫째 줄에 새로운 수의 자릿수를 출력합니다.링크: https://www.acmicpc.net/problem/1748풀이: 자릿수의 기여도(Contribution)를 활용한 수학적 최적화N이 최대 1억이므로 1부터 N까지 순회하며 문자열을 이어 붙이거나 자릿수를 일일이 더하면 무조건 시간 초과가 발생합니다. 이 코드는 '각 숫자가 전체 자릿수에 몇 번 기여하는가?'를 수학적으로 분해하여 단 몇 번의 연산만으로 정답..