알고리즘 모음(C++)

문제 링크입니다. 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/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net N명이 사람이 있을 때, i번째 사람에게 인사를 하면 L[i]만큼 체력이 줄어들고, J[i]만큼 기쁨이 늘어납니다. 이때, 최대로 얻을 수 있는 기쁨을 구하는 문제입니다. 사람의 수가 따라서 확인할 수 있는 모든 경우를 확인했습니다. i번째 사람을 선택하는 경우와 안하는 경우가 있기 때문에 이를 모두 vector에 넣어준 뒤, 선택하는 경우에서 최댓값을 비교해주면 됩니다. 자세..

문제 링크입니다. 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/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 부분 문자열의 개수를 구하는 문제입니다. 부분 문자열의 개수를 구하는 문제입니다. 문자열의 길이가 1 ~ N까지 있지만 1번 문자부터 마지막 문자까지 문자열을 만들어 가면 됩니다. 예를 들어, ababc의 경우 a에서 시작해 a -> ab -> aba -> abab -> ababc로 만들 수 있습니다. 다음은 b에서 시작해 b -> ba -> bab -> babc가 되며 다음은 a에서 시작해 a -> ab -> abc가 됩니다. 이를 계속 반복해서..

문제 링크입니다. https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 주어진 수를 10진수로 바꾸는 문제입니다. ZZZZ는 36진수인데 이를 10진수로 바꾸는 과정은 Z * (36^(4-1)) + Z * (36^(3-1)) + Z * (36^(2-1)) + Z * (36^(1-1))가 됩니다. 다른 진법도 마찬가지로 바꾸는 방법은 같으니 이를 구현하면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #inc..

문제 링크입니다. https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 수를 뒤집에 같은 수만으로 만들 때, 최소 횟수를 구하는 문제입니다. 어려워보이지만 간단한 문제인데, 전체를 뒤집는다고 하면, 최소 횟수에 + 1을 더하는 행위나 마찬가지입니다. 따라서 0의 구역 갯수, 1의 구역 갯수를 구해 더 적은 갯수를 출력하면 됩니다. 예를 들어 0001100의 경우 0의 갯수는 2개, 1의 갯수는 1개임으로 1번만 뒤집으면 됩니다. 자세한 것은 코드를 ..

문제 링크입니다. https://www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 2진수를 8진수로 만드는 방법은 뒤에서부터 3개씩 끊어서 변경해주면 됩니다. 예를 들어 11001100의 경우 11 / 001 / 100 으로 나누어 각각 3 , 1 , 4로 만든 뒤, 이를 합쳐주는 과정입니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #include using namespace std; string x, y, ans; int main(){ cin.tie(0); ..

문제 링크입니다. https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net N개만큼 문자열이 주어지고 M개만큼 문자열이 주어질 때, M개 문자열에 N개 문자열이 몇개가 들어있는지 구하는 문제입니다. N, M이 최대 10,000이기에 완전 탐색을 했다가 시간초과가 됩니다. 따라서 이분 탐색을 통해 N 속에 M이 들어있는지 확인해줘야 합니다. 자세한 것은 코드를 참고해주세요. #include #include #include ..

문제 링크입니다. https://www.acmicpc.net/problem/25501 25501번: 재귀의 귀재 각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다. www.acmicpc.net 문제에서 주어진 함수를 사용한 뒤, 호출 개수를 세는 것만 추가해주면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include using namespace std; int N; int cnt; int recursion(const char *s, int l, int r){ cnt++; if(l >= r) return 1; else if(..

보호되어 있는 글입니다.