알고리즘 모음(C++)

문제 링크입니다. 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/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1, 2, 3의 합을 통해 수를 만들 때, 경우의 수가 몇개가 나오는지 구하는 문제입니다. 같은 개수를 사용해도 위치가 다르다면 다른 경우로 봅니다. 예를 들어, 1 + 1 + 2와 2 + 1 + 1은 서로 다른 경우입니다. 1, 2, 3을 통해 만드는 것이기에 이전의 수들로 부터 +1, +2, +3을 한다면 수를 만들 수 있습니다. 만약, 7이라는 수를 만들려고 할 때, 6에 +1을 하면 됩니다. 그렇다는 것은 6의 경우의 수에..

문제 링크입니다. 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/25314 25314번: 코딩은 체육과목 입니다 오늘은 혜아의 면접 날이다. 면접 준비를 열심히 해서 앞선 질문들을 잘 대답한 혜아는 이제 마지막으로 칠판에 직접 코딩하는 문제를 받았다. 혜아가 받은 문제는 두 수를 더하는 문제였다. C++ www.acmicpc.net 주어진 수를 4로 나눈 값만큼 long 을 출력하면 되는 문제였습니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #include using namespace std; int x; int main(){ cin.tie(0); cout.tie(0); cin >> x;..

문제 링크입니다. 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(..

보호되어 있는 글입니다.

문제 링크입니다. https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 종이 몇% 있는지 구하는 문제입니다. map을 사용해 중복된 종은 1씩 증가하며, 새로운 종은 추가해줍니다. 마지막에 X번째 종의 개수와 전체 개수의 백분율을 구해 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #include using namespa..

문제 링크입니다. https://www.acmicpc.net/problem/1212 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net 8진수를 2진수로 바꾸는 문제입니다, 8진수를 2진수로 바꾸는 방법은 한자리마다 3개의 2진수로 바꾼 뒤, 합쳐주면 됩니다. 314의 경우에는 3, 1, 4로 나눈 뒤, 각각의 2진수를 3자리 구해줍니다. 011, 001, 100이 되는데, 이를 합쳐줍니다. -> 011001100, 여기서 시작이 0이 되면 안되니, 11001100을 출력하면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #in..