https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 💡IDEA 수학, 브루트포스를 사용하는 문제이다. 주어지는 L, C가 15 이하인 수이기 때문에, 브루트포스로 해결할 수 있을 것 같았다. 바로 itertools의 combinations 함수, 즉 조합 함수를 사용하여 C개의 문자 중 L개를 선택한 조합들을 찾는다. 이 암호들 중 자음이 두개 이상, 모음이 하나 이상인 암호만 출력하도록 한다. 📌CODE import sys from itertools ..
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 먼저 모눈종이의 사각형을 표시하기 위해 2차원 배열에 입력받은 사각형의 왼쪽 아래 좌표와 오른쪽 위 좌표를 사용하여 사각형이 존재하는 부분은 1로, 그렇지 않은 부분은 0인 상태로 둔다. 모든 사각형을 표시했다면, 사각형이 없는(0) 지점을 찾아서 BFS를 수행하며 상하좌우로 연결된 영역의 넓이를 세며 방문 확인을 해준다. BFS를 수행한..
https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 규칙을 찾기 위해 N이 1, 2, 3인 경우를 생각해보자. 먼저 N=1인 경우, 오르막 수는 0~9까지 각 1개씩 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]으로 모두 10개이다. N=2인 경우, 오르막 수는 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]으로 모두 55개이다. N=3인 경우, 오르막..
https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 💡IDEA 수학을 사용하여 푸는 문제이다. 소수인 수를 구하기 위해 에라토스테네스의 체 방법을 이용했다. 이는 소수인 2부터 시작한다. 2의 배수인 값을 모두 소수가 아님을 체크하고, 체크되지 않은 값 중 가장 작은 3은 소수로 여긴다. 이후 3의 배수를 모두 체크하는 식으로 반복된다. 이런 방법을 사용하여 2*n까지의 소수를 모두 구하고, 그 중 n과 2*n 사이의 소수의 개수를 센다. ..
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 처음 값부터 연속해서 합을 구하는데, 이전까지 연속합에 현재 값을 더한 것과 그냥 현재 값을 비교하여 큰 값을 dp 배열에 저장한다. 이렇게 되면 연속하는 수 중에서 가장 큰 합을 구할 수 있다. 예를 들어, n = 10, numbers = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1] 인 경우를 생각해보자. dp 배열은 5번째 인덱스까지 [1..
https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. dp[i]는 카드 i개를 구매하는 최대 비용, Pi[i]는 i개가 들어있는 카드팩 가격이다. 예를 들어, 카드를 1개 구매하는 최대 비용은 dp[0] + Pi[1]이다. 카드를 2개 구매하는 최대 비용은 dp[1] + Pi[1], dp[0] + Pi[2] 이다. 카드를 i개 구매하는 최대 비용은 dp[i-1] + Pi[1], dp[i-2] + Pi[2], .....
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 일정 높이만큼 비가 내렸을 때, 잠기지 않는 영역의 개수의 최대값을 구하는 문제이다. 높이는 입력받은 높이 값들 중 가장 작은 값부터 시작하여 가장 큰 값까지 bfs 함수를 수행하며 개수를 센다. 가장 작은 값 min_height와 가장 큰 값 max_height는 파이코닉한 방법으로 구할 수 있다는 점을 유의한다. bfs에서는 일정 높이보다 높은, 즉 안전한 높이..
https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 💡IDEA 수학을 사용하는 문제이다. 처음엔 BFS로 푸는 문제인 줄 알았으나 시간초과로 실패했다. 오히려 규칙을 찾아서 수학적으로 접근해야한다. 처음 시작하는 수와 마지막 끝나는 수는 1이어야 한다는 점을 주의한다. 거리(y-x) 방법 최소 횟수 1 1 1 2 11 2 3 111 3 4 121 3 5 1211 4 6 1221 4 7 12211 5 8 ..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 동적계획법 문제는 쉽게 동적계획법으로 풀어야 하는 문제라고 판단하기가 어렵다. dp 배열을 0~9까지 길이 10의 배열을 총 N+1번 가지는 이차원 배열로 설정한다. N=1 인 경우는 한 자리 수인 계단 수를 찾는 것으로, [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]로 설정되어 총 9개를 가진다. N=2 인 경우는 두 자리 수인 계단 수를 찾는 것으로, N=1인 경우의 dp를 사용하여 [1, 1, 2, 2, 2, 2, 2, 2, 2, 1]로 총 17개이다. ..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 💡IDEA 동적계획법을 사용하는 문제이다. 입력받은 wines를 사용하여 dp를 구성하는데, 0번째 값과 1번째 값은 초기화 해준 후 2번째 값부터 어떻게 계산해야 할지 점점 복잡해진다. 2번째 값은 0번째+1번째 or 1번째+2번째 or 0번째+2번째 중 가장 큰 값으로 설정해준다. 3번째 값 부터는 앞에서 2번째까지 계산해둔 dp를 사용하여 계산해나간다. 연속해서 3잔을 마실 수는 없으므로, 2..
