알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2789 2789번: 유학 금지 아주 멀리 떨어져 있는 작은 나라가 있다. 이 나라에서 가장 공부를 잘하는 학생들은 모두 다른 나라로 유학을 간다. 정부는 최고의 학생들이 자꾸 유학을 가는 이유를 찾으려고 했다. 하지만, www.acmicpc.net 문자열 중 CAMBRIDGE에 속하지 않은 알파벳을 출력하는 문제입니다. CAMBRIDGE에 사용된 알파벳들을 저장 후, 출력할 알파벳이 이에 속하면 출력하지만 않으면 됩니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #define P pair #define F first #defi..

문제 링크입니다. https://www.acmicpc.net/problem/11945 11945번: 뜨거운 붕어빵 입력으로 주어지는 각 행을 반전시켜서 출력하면 됩니다. 입력의 1행 1열은 출력의 1행 M열로, 입력의 1행 2열은 출력의 1행 M-1열로 … 입력의 1행 M열은 출력의 1행 1열로 … 입력의 N행 M열은 출력 www.acmicpc.net 뒤집어서 출력해주면 되는 문제였습니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #define P pair #define F first #define S second #define INF 987654321 using namespace std; int N..

문제 링크입니다. https://www.acmicpc.net/problem/27866 27866번: 문자와 문자열 첫째 줄에 영어 소문자와 대문자로만 이루어진 단어 $S$가 주어진다. 단어의 길이는 최대 $1\,000$이다. 둘째 줄에 정수 $i$가 주어진다. ($1 \le i \le \left|S\right|$) www.acmicpc.net N번째 문자를 출력하는 문제입니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #define P pair #define F first #define S second #define INF 987654321 using namespace std; string arr; ..

문제 링크입니다. https://www.acmicpc.net/problem/2864 2864번: 5와 6의 차이 첫째 줄에 두 정수 A와 B가 주어진다. (1

문제 링크입니다. https://www.acmicpc.net/problem/10102 10102번: 개표 입력은 총 두 줄로 이루어져 있다. 첫째 줄에는 심사위원의 수 V (1 ≤ V ≤ 15)가 주어지고, 둘째 줄에는 각 심사위원이 누구에게 투표했는지가 주어진다. A와 B는 각각 그 참가자를 나타낸다. www.acmicpc.net 문자열을 이용해 A. B의 갯수를 세는 문제입니다. 문자열을 입력받아 A와 B의 갯수를 비교하는 문제입니다. 반복문을 통해 문자열 안에 A와 B의 갯수를 센 뒤, 조건문을 통해 마지막에 비교해주면 됩니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #define P pair ..

문제 링크입니다. https://www.acmicpc.net/problem/10824 10824번: 네 수 첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000) www.acmicpc.net 두 수를 합친 후, 합친 수들끼리의 합을 구하는 문제입니다. 문자열 2개 씩을 이어준 뒤, 이를 long long형의 변수에 넣어줍니다. 두 개의 변수를 더해주면 됩니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #define P pair #define F first #define S second #define INF 987654321 using namespace ..

문제 링크입니다. https://www.acmicpc.net/problem/10798 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 세로로 읽었을 때의 문자열을 구하는 문제입니다. 5개의 문자열이 주어질 때, 이를 세로로 읽는 문제입니다. 가장 긴 문자열의 길이를 X라고 할 때, 1~X까지 5개의 문자열을 순서대로 확인합니다. 해당 길이가 N번 째 문자열의 길이보다 클 경우는 그냥 넘어가면 됩니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #inc..

문제 링크입니다. https://www.acmicpc.net/problem/1100 1100번: 하얀 칸 체스판은 8×8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램 www.acmicpc.net 하얀 칸 위에 말이 몇개가 있는지 구하는 문제입니다. 흰색칸과 검은색 칸이 번갈아가면서 나타날 때, 흰색 칸 위에 말이 몇개가 위에 있는지 구하는 문제입니다. 1번, 3번, 5번.. 과 같이 홀수 줄에는 흰색 칸이 홀수번째 칸에 존재합니다. 2번, 4번, 6번.. 과 같이 짝수 줄에는 흰색 칸이 짝수번째 칸에 존재합니다. 이를 생각해 말이 어디 있는지 판별하면 됩니다. 자세한 ..

문제 링크입니다. https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net N개의 문자열이 주어질 때 겹쳐지는 문자를 확인할 수 있는지 물어보는 문제입니다. N개의 문자 중, 겹치는 문자는 그대로, 다른 문자는 ?로 표시해야합니다. 따라서 1~N개의 문자열을 비교해, 다른 문자가 나타날 때마다 ?로 바꿔주면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #..

문제 링크입니다. https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기 첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 입력 받은 문자를 거꾸로 뒤집어도 같은지를 확인하는 문제입니다. 펠린드롬이란 문자를 거꾸로 뒤집어도 원래의 문자와 같은 것을 의미합니다. 따라서 for문을 통해 원래 문자열과 뒤집은 문자열을 동시에 비교해주면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #define P pair #define F first #define S..

문제 링크입니다. https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 최소 공통 조상을 물어보는 문제였습니다. 연결된 노드가 주어졌을 때, 두 노드의 최소 공통 조상을 구하는 문제입니다. 문제에서 N과 M이 크기 때문에, 조상을 구하는 과정을 반복하면 시간초과가 생기게 됩니다. 따라서 트리를 만든 뒤, 깊이를 통해 조상을 구하는 방식을 사용해야합니다. 트리를 만드는 코드입니다. void make_tree(){ queue q; q.push(1)..

문제 링크입니다. https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 플로이드 와샬을 이용해 푸는 문제입니다. 2-친구를 찾는 문제입니다. 2-친구가 되기 위해서는 X와 Y가 서로 친구이거나, X와 Y가 한다리 건너서 이어져 있으면 됩니다. X에 대해 남은 사람들이 몇번을 건너서 친구가 될 수 있는지를 확인하기 위해서 플로이드 와샬 알고리즘을 이용하면 됩니다. 플로이드 와샬 알고리즘을 사용한 후, Distance[i][j]의 값이 2이하라면, 2-친구..