dev study-log

조금 쉽지만 새로운 유형의 문제를 풀어봤다. https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 문제 해석: 문제에서 64cm인 막대에서 시작하여 Xcm인 막대기를 이어붙여 만들어야한다. 이 때, 막대의 합이 Xcm보다 크다면 막대 를 절반으로 자른다. 이렇게 자른 막대 중 하나를 제외하고 남은 막대의 길이의 합이 Xcm보다 여전히 크다면 자른 막대 중 하나를 버린다. 그리고 이렇게 과정을 반복한다. 예를 들어 X가 23인 막대를 만든다면 64..

이 문제는 필자가 좋아하는 문제 유형이다. 백트래킹을 연습하기 좋은 문제 같다. https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 해석: 이 문제는 만들 수 있는 모든 암호를 출력해주는 문제이다. 정수 L은 만들어야 하는 암호의 길이이고, 정수 C는 주어지는 알파벳의 수이다. 두 정수 모두 최대 크기는 15이다. 암호는 반드시 모음을 하나 이상 포함하고 자음을 두개 이상 포함해야 한다. 그 말인 즉, 모음을 하나 이상 포함하고 자음을 두개 이상 ..

이 문제는 ICPC 2021 기출문제이다. https://www.acmicpc.net/problem/23567 23567번: Double Rainbow Let $P$ be a set of $n$ points on the $x$-axis and each of the points is colored with one of the colors $1, 2, \dots , k$. For each color 𝑖 of the 𝑘 colors, there is at least one point in $P$ which is colored with $i$. For a set $P'$ of consecutive p www.acmicpc.net 투 포인터를 공부하기 아주 좋은 문제라고 생각된다. 문제 해석: 영어 해석에 어려움..

이번 문제는 자료구조에 관한 문제이다. https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 해석: 문제에서 테스트 케이스의 수 T 가 주어지면 주어진 수 만큼 연산을 실행해야한다. T는 최대 100이며 함수 P는 최대 100,000이다. 함수 P에서 R이 나오면 배열을 반대로 뒤집고, D가 나오면 배열에서 원소를 삭제해야한다. 만일 모든 R 함수 에 대해 배열을 하나하나 뒤집으려 한다면 시간 초과는 당연할 것이다. 그렇다면 어떻게 접근하는가? 바로 데큐(Double- Ended Queue)를 사용하..

한동안 여행을 다녀와서 문제를 풀지 못해 업로드 하지 못했다.. 이번 문제는 다이나믹 프로그래밍 연습 겸 해서 풀어봤다. 상당히 쉬운 문제였다. https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 문제 해석: 이번 문제는 동전 1과 비슷한 문제이지만 최소로 사용되는 동전의 수를 구하면 되는 문제이다. 최소로 동전을 사용하여 어 떤 값을 만들려면 최솟값에 최솟값을 더하여 만들면 자연스레 최솟값이 될 것이다. 이러한 관점..

이 문제는 오랜만에 푼 실버 문제이다. 동적계획법 연습겸해서 풀어봤다. https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 해석: 이 문제는 계단 수의 갯수를 구하는 문제이다. 계단 수란 각각의 자리에서 인접한 수가 1씩만 차이가 나는 수를 말한다. 이 말인 즉, 인접한 수는 +1 혹은 -1을 해야한다는 의미이다. 이런 과정을 거치려면 길이가 1인 계단 수에서 각각 +1, -1 한 수 를 뒤에 붙여주면 길이가 2인 계단 수가 완성되는데 앞에는 수 0이 오면 안되고 9에서는 +1이 불가능하므로 만약 0이 뒤에 붙으면 그 다음 길이의 계단 수에서 뒤에는 무조건..

이번 문제는 DP 연습 겸 해서 풀어본 문제이다. 이 문제와 연관된 문제들도 풀어볼 예정이다. https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 해석: 문제는 LCS (Longest Common Sequence)와 비슷하고 다른 여타 순열 문제와 마찬가지로 동적 계획법(Dyanamic Programming. 이하 DP)로 풀어나가는 문제이다. 문제에서 주어진 수열의 최대 길이는 1,000으로 비교적 작은 편에 속하므 로 모든 경우의 수를 탐색해도 1초 안에 충..

이번 문제 또한 전에 필자가 다뤘던 문제들과 같은 문제이다. https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 바로 문제 해석으로 들어가보자. 문제 해석: 이 문제의 로봇청소기가 움직이는 조건을 살펴보자. 로봇청소기는 우선 현재 있는 곳을 청소하고, 그 다음에 2번 탐색을 실행한다. 문제는 크게 생각할 것 없이 이러한 조건을 따라가기만 하면 풀린다. 로봇청소기는 움직일 수 있는 경우의 수가 오직 1가지 이므로 너비우선탐색(BFS)와 같은 탐색을..