나그네

1021번: 회전하는 큐 문제 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 자료구조인 덱을 사용해 원형 큐에서 M개의 수를 꺼내는 데 걸리는 최소 횟수를 구하는 문제다. 좌, 우로 움직일 수 있고 가장 앞 원소(front)를 꺼낼 때는 횟수가 증가하지 않는다는 특징이 있다. 1부터 N을 덱에 넣는다. 찾아야 하는 수를 확인한다. 왼쪽부터 꺼내는 경우와 오른쪽부터 꺼내는 경우 중 빠른 경로를 찾는다. 빠른 방향으로 원소를 찾을 때까지..

1018번: 체스판 다시 칠하기 문제 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 입력받은 체스판을 8×8 사이즈로 잘라 올바르게 되기 위해 색칠해야할 가장 적은 횟수를 출력하는 문제. 브루트포스(Brute Force) 문제로 가능한 모든 경우의 수를 계산해본 후 가장 작은 값을 출력하면 된다. 체크할 경우는 흰색으로 시작하는 경우와 검은색으로 시작하는 두가지 밖에 없다. 따라서 이 보드들을 string 배열로 만들어놓으면 된다..

1012번: 유기농 배추 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 잘 알려진 bfs 문제. M×N 배열을 모두 돌면서 값이 1인 동시에 아직 방문하지 않은 점들에 대해 bfs를 시행한다. bfs에선 해당 좌표를 방문처리한 후 상하좌우를 하나씩 체크하며 값이 1인 동시에 아직 방문하지 않았다면 큐에 추가해 준다. 위 방법을 큐가 빌 때까지 반복한다. bfs를 한 번 진행하면 인접해있는 모든 배추는 방문하게 되므로, bfs를 진행한 횟수가 정..

1011번: Fly me to the Alpha Centauri 문제 https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 풀이 문제에서 출발과 도착하기 바로 직전의 이동거리는 1광년만 이동가능하다. 가장 먼저 작동 횟수의 최솟값이기 때문에 이동 거리는 점점 커지다가 줄어야 한다고 생각했다. 출발점과 도착점에서 거리가 1씩 커지면서 출발한다고 생각했고 두 지점 간 거리가 양수인 동안 먼저 (두 지점 간 거..

1010번: 다리 놓기 문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 서쪽의 사이트 개수 N, 동쪽의 사이트 개수 M을 입력받고 두 사이트를 잇는 경우의 수를 구하는 문제다. 조합을 사용하면 쉽게 풀 수 있다. nCr(조합): n개의 카드 중에 r개를 뽑아 나열할 수 있는 경우의 수 (단, 중복은 불가능) nCr = nPr / r! n*(n-1)*(n-2)*...*(n-r+1) 즉, nCr = ──────────── 이다. r*(r..

17087번: 숨바꼭질 6 문제 https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 풀이 수빈이는 좌우로 D칸씩 이동할 수 있고 모든 동생을 찾기 위한 D의 최댓값을 찾는 문제다. 즉, 모든 수빈이와 동생 사이의 거리의 최대공약수를 구하는 문제다. 먼저 첫 번째 동생과의 거리를 D라 하자. 다음 동생의 위치를 입력받을 때마다 입력받은 동생과의 거리와 D의 최대공약수를 D에 저장한다. 따라서 D를 출력하면 정답이다. ..

유클리드 호제법(Euclidean Algorithm) 유클리드 호제법 두 개의 자연수의 최대공약수를 구하는 알고리즘 중 하나 2부터 1씩 늘려가며 두 자연수 중 작은 수까지 모두 나누어보는 방법은 시간복잡도가 O(N)인 반면 유클리드 호제법이란 알고리즘을 사용하면 시간복잡도를 O(logN)으로 줄일 수 있다. 최대공약수(Greatest Common Divisor, GCD) 공약수(Common Divisor)란 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻이다. 최대공약수는 공약수 중 가장 큰 값을 의미한다. 최소공배수(Lowest Common Multiple, LCM) 공배수(Common Multiple)란 두 수, 혹은 그 이상의 수들의 공통인 배수라는 뜻이다. 최소공배수는 공배수 중 가장 작..

1009번: 분산처리 문제 https://www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net 풀이 컴퓨터가 10대이므로, a^b의 일의 자리 수를 출력하면 된다. 따라서 1에 a를 b번 곱해가며 일의 자리 수만 남긴다. 일의 자리 수가 0이 아니라면, 그 수를 출력하고 일의 자리 수가 0이면 10을 출력한다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); in..

1008번: A/B 문제 https://www.acmicpc.net/problem/1008 1008번: A/B 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 두 정수를 입력받은 후 나눈 결과를 출력하면 되는 문제다. 절대오차가 10^-9 이하여야 한다는 조건이 있으므로 정수가 아닌 실수값으로 입력받고 여유롭게 소수점 이하 15번째 자리까지 출력한다. 코드 #include using namespace std; int main() { double a, b; cin >> a >> b; cout

1003번: 피보나치 함수 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 규칙을 찾는 것이 중요한 문제다. N 0의 횟수 1의 횟수 0 1 0 1 0 1 2 1 1 3 1 2 4 2 3 여기서 0의 횟수와 1의 횟수를 각각 살펴보면 0의 횟수: 1, 0, 1, 1, 2, ... 1의 횟수: 0, 1, 1, 2, 3, ... 이므로 각각은 1, 0으로 시작하는 피보나치 수열과 0, 1로 시작하는 피보나치 수열이다. 따라서 각각에 대한 피보나치 수열을 구하는 문제다. 코드 #include using namespace std; int..