나그네

1071번: 소트 문제 https://www.acmicpc.net/problem/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 풀이 N개의 수를 입력받아 A[i]+1 ≠ A[i+1]를 만족하게 정렬하여 사전순으로 가장 앞서는 것을 출력하는 문제다. 그리디 알고리즘으로 풀면 된다. 두 시간 정도 들여서 AC 받았다. 가장 중요한 두가지가 있는데 첫 번째는 사전순으로 가장 앞서는 것이기 때문에 수를 정렬해 주고 시작해야 한다. 둘째는 남아있는 수의 (최댓값 - 최솟값)이 1이면 큰 수를 먼저 모두 출력..

17609번: 회문 문제 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 문자열을 입력받아 이 문자열이 회문인지, 유사 회문인지, 둘 다 아닌지를 판단하여 각 0, 1, 2를 출력하는 문제다. 여기서 유사 회문이란 문자열에서 한 글자를 제거하여 회문이 되는 문자열을 말한다. 투 포인터(two pointer)를 사용해 풀었다. 문자열을 s라 하면, left는 0번 index부터 차례로 증가, right는 문자열의 마지막 문자 index부터 차례로 감소하며 left < r..

1264번: 모음의 개수 문제 https://www.acmicpc.net/problem/1264 1264번: 모음의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 영어 대소문자, ',', '.', '!', '?', 공백으로 이루어진 문장이 주어진다. 각 줄은 최대 255글자로 이루어져 있다. 입력의 끝에는 한 줄 www.acmicpc.net 풀이 getline 함수를 사용해 줄 단위로 입력을 받고 모음(a, e, i, o, u)의 개수를 세는 문제다. 대/소문자 모두 세어야 함에 주의하자. 코드 #include using namespace std; int main() { string str; char arr[] = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I..

1260번: DFS와 BFS 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 dfs와 bfs의 기본 사용 방법을 연습할 수 있는 문제다. 간선이 양방향이므로 x, y를 입력받아 graph[x][y] = 1, graph[y][x] = 1로 해준다. 시작 정점부터 dfs를 돌리면 방문처리를 한 후 정점에서 연결된 위치가 아직 방문하지 않았다면 해당 정점으로 dfs를 다시 진행한다. 이를 반복하여 계속..

1259번: 팰린드롬수 문제 https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 풀이 문자열 S를 입력받고 왼쪽 끝과 오른쪽 끝에서부터 차례대로 문자가 같은지 확인하며 같은 개수를 센다. 하나라도 틀리다면 "no"를 출력한다. 아니라면 탐색을 모두 끝내면 "yes"를 출력한다. 오래전에 푼 문제라 너무 어렵게 푼 것 같다. 그냥 문자열을 복사해 두고 헤더의 reverse() 함수를 사용해 뒤집어서 같은지 비교만 하면 풀 수 있는 간단한 문제다. 코드 #includ..

1237번: 정ㅋ벅ㅋ 문제 https://www.acmicpc.net/problem/1237 1237번: 정ㅋ벅ㅋ 우주를 정ㅋ벅ㅋ할 사람에게는 예제 입력과 예제 출력이 필요하지 않다. www.acmicpc.net 풀이 첫째 줄에 문제의 정답을 출력한다. 라고 되어 있으므로 "문제의 정답"을 출력하면 된다. 코드 #include using namespace std; int main() { cout

27467번: 수학 퀴즈 문제 https://www.acmicpc.net/problem/27467 27467번: 수학 퀴즈 문제에서 설명한 두 실수 $p$, $q$를 출력한다. 단, 정답과의 절대/상대 오차는 $10^{-9}$까지 허용한다. www.acmicpc.net 풀이 복소근에 대한 개념을 알고 있다면 쉽게 풀 수 있는 문제. x^2+x+1=0의 한 복소근 w이므로 w^3 = 1, w^2 = -w-1이다. 따라서 3의 N승일 때, N을 3으로 나눈 나머지로 바꾸어 계산해도 된다. 이후엔 pw + q 의 형태로 계산하여 p와 q를 출력하면 된다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL..

27465번: 소수가 아닌 수 문제 https://www.acmicpc.net/problem/27465 27465번: 소수가 아닌 수 이 대회의 운영진 중 한 명인 KSA 학생은 $17$시와 $19$시를 구별할 수 없다. 이는 당연하게도 $17$과 $19$가 모두 소수이기 때문일 것이다. 시간을 제대로 구별해서 KSA의 명예를 지키기 위해 정수 $N$ www.acmicpc.net 풀이 N부터 증가시켜 가며 소수가 아니면 출력하고 종료하면 되는 간단한 문제다. (범위가 10^9까지이므로 이 이상인 짝수를 그냥 출력해도 된다. - 텍스트로 제출해도 됨) 코드 #include using namespace std; bool isPrime(int n) { if (n < 2) return false; for (in..

27445번: Gorani Command 문제 https://www.acmicpc.net/problem/27445 27445번: Gorani Command 도망친 고라니가 숨어있는 칸의 좌표를 $(r,c)$라 할 때, $r$과 $c$를 순서대로 출력한다. www.acmicpc.net 풀이 N×M 크기의 배열에서 (1,1)에서 시작해 (N,1)을 거쳐 (N, M)까지 'ㄴ'자 모양으로 탐색하고 각 위치에서 도망친 고라니까지의 거리가 주어진다. 두 칸 (a1, b1)과 (a2, b2) 사이의 거리는 |a1 - a2| + |b1 - b2|로 정의된다. 예제 입력 1은 아래와 같다. 4 5 4 3 4 5 4 3 2 3 위에서 N개의 수 4, 3, 4, 5 중 3이 가장 작으므로 고라니의 위치는 2행에 있다. M..

1193번: 분수찾기 문제 https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 풀이 나열된 분수는 1/1, 1/2, 2/1, 3/1, 2/2, 1/3,... 과 같은 순서로 이루어져 있다. 순서대로 1번, 2번, 3번,... 분수라고 할 때, X번째 분수를 구하는 문제다. 표에서 대각선마다 규칙이 있는데 홀수번째 줄은 위로, 짝수번째 줄은 아래로 향한다. 또 N번째 줄에는 N개의 분수가 있다. 따라서 X번째 수가 있는 줄까지 가기 위해 X에서 각 줄마다 있는 분수의 수만큼 빼주다가(X -= line) 더 이상 뺄 수 없을 때까지 줄을 이동한다. 그리고 홀수번째 줄일 때는 아래에서..