알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net Dp를 이용해 푸는 문제입니다. 주어진 2개의 문자열에서 공통으로 가장 긴 문자열을 찾는 문제입니다. 위의 문자열을 X, 아래 문자열을 Y라고 할 때, X문자열의 문자를 1번부터 하나씩 늘려가면서 Y와 비교했습니다. 사용된 논리는 LCS와 비슷합니다. 아래를 확인해주세요. https://junseok.tistory.com/170 백준 9251 - LCS(C++) 문제 ..

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

문제 링크입니다. https://www.acmicpc.net/problem/4999 4999번: 아! 입력은 두 줄로 이루어져 있다. 첫째 줄은 재환이가 가장 길게 낼 수 있는 "aaah"이다. 둘째 줄은 의사가 듣기를 원하는 "aah"이다. 두 문자열은 모두 a와 h로만 이루어져 있다. a의 개수는 0보다 크거 www.acmicpc.net 두 문자열의 길이를 비교하면 되는 문제였습니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #include #include using namespace std; string x, y; int main(){ cin.tie(0); cout.tie(0); cin >> x..

문제 링크입니다. https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net A의 앞과 뒤에 원하는 알파벳을 추가해 B와 같은 길이로 만들 때, A와 B의 차이를 구하는 문제입니다. 문제를 푸는 키는 원하는 알파벳을 추가한다는 것이였습니다. 따라서 A와 B를 비교해 차이가 가장 작은 위치를 찾습니다. 해당 위치에서 남은 길이를 B와 똑같이 추가하면 되니 이때의 차이가 답입니다. 자세한 것은 코드를 참고해주세요 #in..

문제 링크입니다. https://www.acmicpc.net/problem/1213