프로그래밍 공부 노트

https://www.acmicpc.net/problem/1330 1330번: 두 수 비교하기 두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오. www.acmicpc.net 두 수 a와 b를 입력받아 그 대소를 비교하는 문제이다. #include int main() { //두 수를 입력받아 두 수의 관계에 해당하는 부등호를 출력한다 int a, b; scanf("%d %d", &a, &b); if (a == b) printf("==\n"); if (a > b) printf(">\n"); if (a < b) printf("

https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 각 단어에서 어느 글자가 연속해서 나오지 않는지를 확인하는 문제이다. 각 단어마다 글자가 나왔는지 여부와 직전에 나온 글자를 저장하고, i번째 글자가 직전의 글자와 다르면서 이전에 나온 단어라면 그룹 단어가 아니다. #include // 입력받은 단어가 그룹 단어라면 true, 아니라면 false bool test_case() { // chk[i]: 각 알파벳이 이..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 사자는 한 칸에 한 마리씩 가둬야 하고, 연속된 칸에 사자를 동시에 둘 수 없으므로 각 줄에 사자를 둘 수 있는 방법은 왼쪽에만 가두는 방법, 오른쪽에만 가두는 방법, 어느 쪽에도 가두지 않는 방법 둘 뿐이다. 또한 i번째 줄에 한 방법으로 가두었다면, 연속된 칸에 사자를 동시에 둘 수 없으므로 i + 1번째 줄에는 i번째 줄에 사용한 방법 이외의 방법으로 가두어야 한다. 이 조건을 만족하는 방식으로 다이나믹 프로그래밍을 이용해 문제를 풀면 된다. #include #define MAX_N 100000 #define RMN 9901..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 주어진 그래프를 각각 깊이 우선 탐색, 너비 우선 탐색을 하는 문제이다. 깊이 우선 탐색은 호출 스택을, 너비 우선 탐색은 STL을 이용해 계산하는 것이 편하다. #include #include using namespace std; #define MAX_N 1000 // edge[i][j]: 노드 i와 j가 연결되어 있다면 true, 아니라면 false // ..

https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 입력되는 수를 수가 아닌 문자열이라고 생각하자. 문자열 str의 길이 len에 대해, 0

https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 문자열 K의 뒤에 문자 K개를 추가해서 팰린드롬을 만든다는 말은, 문자열 S를 뒤집은 문자열 S'에 문자 K개를 추가해 팰린드롬을 만드는 것과 같다. 이 떄 S'의 앞에서부터 시작하는 부분 문자열 S'p가 팰린드롬이라면, K는 곧 S'의 길이에서 Sp의 길이를 뺀 값과 같다. 따라서 이 문제는 문자열 S가 뒤에서 얼마나 긴 팰린드롬을 가지고 있는지를 알아내는 문제와 같다. #include using n..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 각 마을을 노드, 도로를 에지로 보면 그래프 탐색 문제임을 알 수 있다. 그래프에서 특정 노드로 이동하는 최단 비용을 구하는 문제이므로, 다익스트라 기법을 이용해 풀 수 있다. 이 때 중요한 점은, 도로가 단방향 도로이므로 갈 때의 비용과 올 때의 비용이 다르기 때문에 도로를 두 종류로 따로 저장해서 다익스트라를 두 번 실행해야 한다는 것이다. 갈 때의 도로와 올 때..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 스패닝 트리를 만드는 알고리즘은 크루스칼(Kruskal) 기법과 프림(Prim) 기법이 있는데, 두 방법 모두 이용해서 풀어보도록 하자. - 크루스칼 기법 크루스칼 기법은 모든 에지를 가중치가 작은 순으로 트리에 추가하고, 사이클이 생기는 에지는 버리며 모든 노드에 방문했을 때 트리 생성을 종료하는 알고리즘이다. 이 때 크루스칼 기법은 각 노드를..

https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net i번째 대각선의 분수의 개수는 i개이고, 분모와 분자의 합은 i + 1이므로 이를 이용해서 분수를 빠르게 검색할 수 있다. 우선 i를 1부터 차례로 X가 음수가 될 때까지 빼고, 이렇게 얻은 음수 X'는 목표 분수의 현재 대각선에서의 순서이므로 이를 이용하면 쉽게 답을 구할 수 있다. #include int main() { // X : 분수의 위치를 특정할 때 사용할 변수 // i: 각 대각선에 있는 분수의 개수 // up, down : 각각 분수의 분자와 분모 int X, i = 0, up, down; // X가 음수로 변한 ..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 단어를 입력받아 길이순, 사전순으로 출력하는 문제이다. 단어를 길이에 따라 나눠 저장한 뒤 각 단어를 정렬하면 된다. #include #include #include using namespace std; #define MAX_LEN 50 int main() { // 입출력 속도 향상 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)..