Programming456 [C/C++] 백준 #1562 계단 수(동적 계획법) 계단 수는 1232나 34545와 같이 인접한 자리수의 숫자 차이가 1인 수를 말합니다. 이러한 자리의 수의 경우의 수를 구하는 것은 크게 어렵지는 않을겁니다. 그런데, 이번문제는 0부터 9까지의 모든 숫자가 포함되어야 합니다. https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 여기서 0부터 9까지 모든 숫자가 다 있어야 한다는 것이죠. 동적계획법을 이용하더래도 최소수, 최대수, 그리고 마지막수가 있어야 합니다. 즉, 123234323 과 같은 숫자는 최소수 1, 최대수 4, 그리고 마지막 수 3이 됩니다. 그러면 이 다음에 붙일 수 있는 수는 2 또는 4가 됩니다. .. 2022. 9. 6. [C/C++] 백준 #1541 잃어버린 괄호(탐욕 알고리즘) 이번 문제는 생각만 간단하게 하면 됩니다. 문제를 풀 때, 어떻게 하면 간단하게 풀 수 있는지 생각하게 해주는 문제입니다. 아래는 백준 사이트에 있는 문제입니다. https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 이 문제는 +, - 연산자만 사용된 수식에서 괄호를 적당하게 넣어 수식의 값을 최소로 만드는 것이다. 이 문제에서는 - 기호가 있느냐가 핵심입니다. 괄호를 마음껏 칠 수 있기 때문에, +로만 이루어진 수식은 괄호가 아무런 의미가 없.. 2022. 9. 2. #1535 안녕 이번 문제는 효율적으로 풀려면 백팩 알고리즘을 이용하셔야 합니다. 백팩 알고리즘은 유명한 문제로, 일반적으론 결정 트리를 이용해서 예측 값이 가장 좋은 것을 먼저 선택해서 처리합니다. 그리고 결정된 값보다 나쁜 것은 제거함으로써 그나마 빠르게 계산할 수 있습니다. https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 문제 자체는 Silver II 문제입니다. 배낭 문제로 해석을 하자면 99만큼의 무게를 넣을 수 있는 배낭에 무게 \(h_i\)이고 .. 2022. 9. 2. #1525 퍼즐 우리는 4x4짜리 슬라이딩 퍼즐은 자주 갈지고 놀게 됩니다. 슬라이딩 퍼즐은 아래의 그림과 같이 생겼는데요. 비어있는 칸이 있고, 이 칸의 주변 상하좌우에서 숫자를 옮길 수 있습니다. 이번 문제는 4x4 슬라이딩 퍼즐이 아니고 3x3 슬라이딩 퍼즐입니다. 슬라이딩 퍼즐이 주어지면, 가장 빠르게 맞출 때 최소의 이동횟수를 푸는 것입니다. 불가능한 경우도 생깁니다. 이건 숫자가 있어야할 곳과 비어있는 칸의 위치로 원래 판단할 수 있습니다. 하지만, 그것을 이용해서 프로그램하지는 않았습니다. https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmi.. 2022. 9. 1. #1521 랜덤 소트(dynamic programming) 이번 문제는 꽤 재미있는 주제입니다. 인공지능 마르코프 체인을 이야기하다보면, 기대값을 계산하는 부분이 있습니다. 이 부분을 잘 활용하고, 그리고 잦은 중복 호출이 발생하니 동적 계획법도 이용해야 합니다. 문제는 아래와 같습니다. https://www.acmicpc.net/problem/1521 1521번: 랜덤 소트 첫째 줄에 순열의 크기 N이 주어진다. 둘째 줄에 순열에 들어있는 수 N개가 주어진다. 이 수는 모두 1보다 크거나 같고, N보나 작거나 같으며, 같은 수는 2번 이상 주어지지 않는다. 또, N은 8보다 www.acmicpc.net 마르코프 프로세스에 의하면 우리가 현재 상태(\(S_c\))의 기대값은 다음과 같이 구할 수 있습니다. \[ E(S_c) = \sum_{p} P_{c, p} \.. 2022. 8. 31. #1520 내리막 길 내리막 길 문제는 나올 수 있는 모든 경로의 개수를 구하는 프로그램입니다. 일반적으로 이렇게 경우의 수를 물어보는 문제는 동적 계획법(dynamic programming)을 이용하면 풀기 쉬워집니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 그러면 어떻게 하면 좋을까요? 상하좌우로 움직일 수 있으니, \((i, j)\)에서의 경우의 수 \(d_{i, j}\)는 주변의 값들의 합으로 나타낼 수 있습니다. \[ d_{i,.. 2022. 8. 29. 이전 1 ··· 35 36 37 38 39 40 41 ··· 76 다음 728x90
