분류 전체보기

문제 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 어떤 문제인가? 백 트랙킹의 대표적인 문제로 들었다. N * N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 물어보는 문제이다. 접근 방법 N이 4일 때 (1, 1)부터 퀸을 놓으면서 진행한다. 퀸은 대각선과 직선을 모두 공격할 수 없으므로 한 줄에 퀸이 놓이면 무조건 다음 줄로 넘어가야 한다. 그래서 두 번째 줄로 이동해서 다음 퀸을 놓을 자리를 찾는다. (2, 1), (2, 2)는 ..

문제 : https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 어떤 문제인가? 아주 간단한 문제이다. 그냥 가장 큰 첫 번째 링의 반지름과 각 링들의 반지름들을 비교한 다음 기약 분수 형태로 출력하면 된다. 접근 방법 int n; cin >> n; 링의 개수 n을 입력 받는다. int arr[n]; 링들의 반지름을 저장할 배열을 선언한다. for (int i = 0; i > arr[i]; } n번 만큼 링의 반지름을 입력받는다. 기약 분수로 나타내기 위..

문제 : https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 어떤 문제인가? 골드바흐라는 분께서 추측하신 정수론의 미해결 문제를 구현하는 문제이다. 다만, 입력된 n에 대한 골드바흐 파티션이 여러 개일 경우 두 소수의 차이가 가장 작은 것을 출력해야 한다. 접근 방법 이 문제에서도 에라토스테네스의 체가 사용된다. 잘 모른다면 에라토스테네스의 체에 대한 이해를 하고 이 글을 보는 것을 추천한다. bool arr[10000 + 1]..

문제 : https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 어떤 문제인가? 베르트랑과 채비 쇼프라는 분께서 만드신 명제를 구현하는 것이다. 입력한 수 n에 대해 n초과~2n이하의 범위에 존재하는 소수의 개수를 출력하면 된다. 접근 방법 여기서 에라토스테네스의 체라는 개념이 사용된다. 에라토스테네스의 체에 대해 모른다면 이해가 안 될 것이니 보는 것을 추천한다. bool arr[123456 * 2 + 1]; for (int i = 2; i

문제 : https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 어떤 문제인가? 전화번호 목록에 여러 개의 전화번호가 존재한다. 문제의 예시처럼 선영이에게 전화를 걸기 위해선 911을 눌러야 하지만 911이란 번호가 긴급전화라 전화 버튼을 누르지 않아도 바로 전화가 걸린다. 따라서 선영이에게 전화를 거는 것은 불가능하다. 이러한 전화번호 목록을 일관성이 없다고 문제에서 표현했다. 문제는 어떠한 전화번호 목록이 일관성이 있는지 없..

문제 : https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 어떤 문제인가? 문자열과 폭발 문자열이 있다. 문자열에 폭발 문자열이 있으면 문자열에서 폭발 문자열을 지워 나가면 된다. 더 이상 폭발이 일어나지 않으면 남아있는 문자열을 출력하면 된다. 접근 방법 string s, bomb; cin >> s >> bomb; string ans = ""; 먼저 기준 문자열과 폭탄 문자열을 입력받는다. ans는 빈스 트링으로 여기에 기준 문자..

문제 : https://www.acmicpc.net/problem/19638 19638번: 센티와 마법의 뿅망치 마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수 www.acmicpc.net 어떤 문제인가? 때리면 키가 키/2가 되는 뿅망치를 n번 때려 거인들의 키가 센티보다 작게 할 수 있는지 여부 할 수 있다 -> 뿅망치 사용 횟수 출력 할 수 없다 -> 가장 큰 거인의 키 출력 간단하게 정리해보면 위와 같다. 접근 방법 문제에서 키가 가장 큰 거인부터 때리라고 알려줬다. 그러면 일단 거인들을 키가 큰 순서대로 정렬해야 했다. 키를 다 입력하고 정렬을 한다면 ..

문제 : https://www.acmicpc.net/problem/14713 14713번: 앵무새 자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 www.acmicpc.net 어떤 문제인가? n가지의 문장과 기준이 되는 문장을 입력받는다. n가지 문장의 단어들은 뒤죽박죽 섞여있다. 이때, n가지 문장들의 단어들의 순서를 잘 조합해서 기준 문장을 만들 수 있는지의 여부를 묻는 문제이다. 접근 방법 기준 문장의 첫 단어와 n가지 문장들의 첫 단어가 일치하는지를 확인해가며 만약 일치한다면 pop 시켜주는 방법을 떠올렸다. vector와 queue를 사용해..

문제 : https://www.acmicpc.net/problem/25192 25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net 어떤 문제인가? 채팅방에 새로운 사람이 들어왔을 때 유저의 닉네임의 첫 번째 등장만이 신입에게 인사를 한 채팅이다. 그 외의 나머지는 잡답이다. 따라서 ENTER가 입력된 후에 처음 등장한 닉네임의 숫자만 세주면 된다. 접근 방법 문제를 읽자마자 map을 써야겠다고 생각했다. map user; 유저의 이름을 key로 인사 여부를 value로 저장하는 map을 선언했다..

문제 : https://www.acmicpc.net/problem/17952 17952번: 과제는 끝나지 않아! 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이 www.acmicpc.net 어떤 문제인가? 참 공감되는 문제다ㅎㅎ 입력받은 N분동 안 해결한 과제의 총점을 출력하는 문제이다. 기존 과제를 끝내지 않고 새로 받은 과제부터 끝내는 로직이 존재한다. 실제로 저렇게 하면 효율이 많이 떨어질 텐데ㅎㅎ.. 하지만 문제니까^^ 접근 방법 1이 입력됐을 때는 가장 최근의 과제를 해야 한다. 처음엔 stack을 사용해보려고 했는데 stack에 과제 해결 점수와 남은 시간..