전자공학 및 알고리즘

문제 링크입니다. https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 유명한 모형입니다. 이를 코드로 작성하라는 문제인데, X번째 수를 구하긴 위해서 일단 X번의 행과 열을 알아야합니다. 이를 각각 N, M이라고 했을 때, 값은 다음과 같습니다. arr[N][M] = arr[N-1][M-1] + arr[N-1][M] 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #in..

문제 링크입니다. https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 연속된 수를 곱할 때, 나올 수 있는 최댓값을 구하는 문제입니다. N은 10,000이하의 수이기에 2중 for문을 사용하면 시간초과가 생길 수 있습니다. 따라서 DP를 사용해서 지금까지 곱한 값의 최댓값을 저장해주면서 풀어나가면 됩니다. 문제를 풀기 위해 예시를 생각해보겠습니다. 4번까지 곱한 값의 최댓값을 구하기 위해선 2가지 방법이 있습니다. 1. 3번까지 곱한 ..

문제 링크입니다. https://www.acmicpc.net/problem/9656 9656번: 돌 게임 2 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1 or 3개씩 돌을 가져갈 때, 누가 이길 수 있는지 구하는 문제입니다. 돌을 마지막으로 가져가는 사람이 지기 때문에 언제 가져갔는지를 확인할 필요가 없습니다. 따라서 현재 값인 i에서 i-1 or i-3의 값을 확인만 해주면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include using namespace std; int N; int dp[1001][2];// 0 -> SK 1 - > CY void solve..

문제 링크입니다. https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net 변형된 피보나치 문제입니다. 기존의 피보나치처럼 풀면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include using namespace std; int N, M; long long dx[70]; void solve(){ dx[0] = 1; dx[1] = 1; dx[2] = ..

문제 링크입니다. https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 증가하는 수열 or 감소하는 수열을 둘 다 확인할 때, 가장 긴 길이를 확인하는 문제입니다. 2개의 수열을 확인해야하니 2차원 배열을 이용해서 풀었습니다. 처음 1번은 길이가 둘 다 1이니 1로 저장한 뒤, 다음 값부터 비교해주기 시작합니다. 1. 다음 값이 이전값보다 클 때 -> 증가하는 값을 1을 더한다, 감소하는 값을 1으로 바꾼다. 2. 다음 값이 이전값보다 작을 때 -> 증..

문제 링크입니다. https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 볼륨이 주어졌을 때, 마지막 곡을 연주할 수 있는지 확인하는 문제입니다. 시작 볼륨이 주어지고, 변경할 수 있는 볼륨이 주어집니다. 시작 볼륨에서 변경할 수 있는 볼륨을 더하고 뺀 값을 전부 확인하면 경우가 너무 많아집니다. 따라서 2차원 배열을 이용해 N번 째 볼륨을 바꿀 때, M번 볼륨을 만들 수 있는지를 확인하는 2차원 배열을 만들었습니..

문제 링크입니다. https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 간단한 다이나믹 프로그래밍을 이용해 푸는 문제입니다. 몇일과 해당 날짜에서 먹은 떡의 개수가 주어질 때, 첫째, 둘째날에 떡을 몇개를 줬는지 구하는 문제입니다. 문제를 읽다보면 떡을 주는 갯수가 피보나치 수열과 같이 늘어나는 것을 볼 수 있습니다. 1일차 -> X, 2일차 -> Y개라고 한다면 3일차는 X + Y 4일차는 X + 2Y ... 이와 같은 방법으로 구해집니다..

문제 링크입니다. https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 2차원 배열을 이용한 Dp로 풀 수 있는 문제입니다. 1, 2, 3을 통해 수를 만드는 경우의 수를 구하는 문제입니다. 수를 만들 때, 같은 수가 2번이상 중복되면 안됩니다. 따라서 수를 만들 때 마지막으로 더한 수를 저장해줘야합니다. -> 이를 2차원 배열을 통해 만들었습니다. [X][1~3]은 X의 수를 만들 때, 1~3의 수로 끝났다는 의미입니다. 따라서 K라는 수를 만들 수 있는 경우는 [K][1] = [K-1][2] + ..

문제 링크입니다. https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 2차원 다이나믹으로 풀 수 있는 문제였습니다. 1, 2, 3을 더함으로써 X라는 수를 만들 수 있는 경우의 수를 구하는 문제입니다. 중복된 경우를 없애는 방법은 오름차순으로서 경우를 관리하는 것입니다. 예를 들어, 1 + 1 + 2와 2 + 1 + 1을 오름차순으로 바꾸면 같은 경우가 됩니다. 모든 수의 합 경우를 저..

문제 링크입니다. https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 배낭 문제를 이용한 DP 문제입니다. 원하는 메모리를 얻기 위해 지워야할 메모리를 최소비용으로 구하는 문제입니다. 저는 dp[x][y] = k 를 이용했습니다. 의미는 X개의 앱까지 확인했을 때, Y 비용으로 얻을 수 있는 최대의 메모리입니다. 문제의 예제 입력으로 확인해보겠습니다. 배열의 값이 다음과 같이 나옵니다. 첫번째 줄을 보면, 1번 앱만을 확인했을 때, 얻을 수 있는 최대의 ..

문제 링크입니다. https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net Dp를 이용한 문제입니다. 자연수 N개와 질문 M개가 주어졌을 때, 질문이 옳은지를 구하는 문제입니다. 펠린드롬은 수열의 중간을 기준으로 양옆이 같은 것입니다. 그렇다면 간단하게 얻을 수 있는 값들이 있습니다. 1. 자기 자신만을 범위로 가지면 무조건 펠린드롬이다. 2. 길이가 2일 경우에는 옆만 확인해보면 된다. -> 2개의 경우는 값을 쉽게 얻을 수 있습니다. 그렇다면 3개 이상부터는 어떻게 구해야할까요? 예를 들..

문제 링크입니다. https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 그래프와 DP가 합쳐진 문제였습니다. 1로 만드는 연산의 최소 횟수 및 과정을 출력하는 문제입니다. 연산의 최소 횟수를 구하는 방법은 간단합니다. 1부터 시작해 N까지 값을 증가하면서 저장해주면 됩니다. 1. 1을 뺏을 때 2. 3을 나눴을 때 3. 2로 나눴을 때 3가지 방법으로 나오는 값을 전부 비교해 가장 작은 값을 가져오면 됩니다. 이때 연산 과정은 하나의 과정을 추가해주면 되는데, 배열에 자신이 어떠한 값에서 도출되었는지를 저장해주면 됩니다. 예를 들어, 10의 최소값이 9에..