문제 URL: https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 다음은 도시의 수와 비용 행렬이 주어졌을 때 외판원의 순회에 필요한 최소 비용을 출력하는 문제로 깊이 우선 탐색(dfs)을 통한 전체 탐색을 진행하는 문제이다. dfs를 통해서 현재 위치에서 갈 수 있는 모든 지점을 탐색해 준다. 이때 최소 비용을 찾아야 하기 때문에 비용 행렬을 더한 값이 현재 최소 비용(total_cost)보다 커진다면..
문제 URL: https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 이 문제는 C개의 문자들이 주어졌을 때, 가능성 있는 암호들을 모두 구하는 문제로 브루트포스 알고리즘과 백트래킹을 이용하는 문제이다. 문제 자체는 어렵지 않았지만 아직 백트래킹 문제에 익숙하지 않아서 다른 사람의 풀이를 찾아보았다. 먼저, 주어진 문자들을 오름차순으로 정렬한 뒤 반복문을 통해 모든 알파벳을 검사하며 조건에 맞는 문자열을 출력하였다. select() 함수에서는 브루트포스 알..
문제 URL: https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 이 문제는 숫자 야구 게임에서 주어진 세자리 숫자와 스트라이크 개수, 볼 개수를 통해 정답이 될 수 있는 세자리 숫자의 가짓수를 구하는 문제이다. 평소에 숫자 야구를 많이 접해봐서 문제를 이해하는데에는 크게 어렵지 않았다. 이 문제는 브루트포스 알고리즘을 사용하는 문제로 일단 모든 수(123~999)를 가능하다고(true) 놓고, 조건을 통해 불가능한 숫자들을 false로 만들면서 ..
문제 URL: https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 다음 문제는 N×N크기의 행렬로 표현되는 종이가 존재할 때, 종이를 규칙에 따라 자르며 -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구하는 문제이다. 문제를 풀기 위해 divide 함수를 사용하여 영역에 존재하는 숫자가 일치하지 않다면 종이를 잘라주었는데 함수 내부에서 재귀를 사용하여 영역의 숫자가 일치할 때까지 종이를 계속 반..
문제 URL: 2839번: 설탕 배달 (acmicpc.net) 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 다음 문제는 3킬로그램 봉지와 5킬로그램 봉지를 사용하여 주어진 N킬로그램만큼의 설탕을 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 문제로 봉지의 최소 개수를 출력해야 한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다. 이 문제를 처음 풀 때는 단순히 N킬로그램에서 계속해서 3을 빼주며 5로 나누어지는 지 확인하는 방식으로 문제를 풀었는데 문제에 다이나믹 프로그래밍을 이용할..
문제 URL: https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 다음 문제는 N ×N 크기의 영상이 주어질 때, 이 영상을 쿼드트리로 압축한 결과를 출력하는 프로그램을 작성하는 문제로 처음 문제를 풀 때 문제에서 나타내는 말이 무엇인지 이해하는데 시간이 걸렸다. 결국 구글링을 해서 알아낸 문제이다. 쿼드트리는 전체를 한번에 나타내지 못하면 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 이렇게 4개의 영역으로 나눠서 압축하는 것을 말..
문제 URL: https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 이 문제는 위의 두 연산을 지원하는 절댓값 힙이 존재할 때 주어진 x값에 따라 배열에 값을 추가하거나 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을..
문제 URL: https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 다음 문제는 문제에서 주어진 해시함수와 입력 문자열을 사용해 해시 값을 계산하여 정수로 출력하는 문제로, 해싱 기법을 이용한 문제이다. 이 문제는 이전에 본 문제들과 다르게 문제 채점이 50점과 100점으로 나뉘는데 제출한 내 코드는 50점을 받아서 100점은 어떻게 받는지 구글링해 보았다. 50점짜리와 100점짜리 코드의 기본적인 원리는 같지만 100점짜리 코드는 아래 두 코드가..
문제 URL: https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이 문제는 숫자 카드 N개가 있고 정수 M개가 주어졌을 때, 주어진 M개의 정수 중 하나와 같은 숫자가 적혀있는 숫자 카드를 가지고 있는지 아닌지를 구하는 문제이다. 이때 정수와 숫자가 같은 숫자 카드를 가지고 있으면 1을, 아니면 0을 출력해준다. 처음에 문제 자체를 이해하는데 많은 시간이 걸렸다. 이 문제는 이분 탐색을 이용해 푸는 문제로 숫자 카드..
문제 URL: https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 이 문제는 원래 가지고 있던 64cm의 막대를 더 작은 막대로 자른 다음, 풀로 붙여서 길이가 Xcm인 막대를 만들 때 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 문제이다. 문제를 보면 X가 가지고 있는 막대 중 길이가 가장 짧은 것(=length)보다 작거나 같을 때 Xcm를 만드는데 필요한 막대를 찾은 것이다. 따라서 위 조건일 때, ans를 1 증가시키고 ..
