알고리즘 분류: 구현, 문자열 문제 링크: https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기 첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 【 풀이 】 앞으로 읽으나 뒤로 읽으나 똑같은 문자열인지 판단하는 문제이다. 문자열의 절반까지만 반복을 설정하고, 앞과 뒤가 같은 문자이면 횟수를 카운트하면 된다. 그 횟수가 문자열의 절반과 크기가 같다면 '1'을 출력하고, 아니라면 '0'을 출력한다. 【 코드 】 #include #include using namespace std; int main(void) { string s; cin >> s; int c..
알고리즘 분류: 이분 탐색, 매개 변수 탐색 문제 링크: https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 【 풀이 】 2805번과 비슷하게 구할 수 있는 문제이다. 2023.05.06 - [백준 [BAEKJOON]] - [백준] 2805번: 나무 자르기 [C++] [백준] 2805번: 나무 자르기 [C++] 알고리즘 분류: 이분 탐색, 매개 변수 탐색 문제 링크: https://www.acmicpc.net/probl..
알고리즘 분류: 이분 탐색, 매개 변수 탐색 문제 링크: https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 【 풀이 】 자를 수 있는 나무의 마지노선 길이를 구하는 문제이다. 이분 탐색으로 구하면 쉽게 해결할 수 있다. start(최소 길이, 즉 0), end(최대 길이, 즉 배열에서의 최댓값) 두 변수를 이용해서 mid(중간값)를 설정하고 배열 요소에서 mid를 뺀 값을 모두 더한 값을 저장한다. 모두 더..
알고리즘 분류: 수학 문제 링크: https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 【 풀이 】 N! 의 뒤에서부터 처음 0이 아닌 수가 나올 때까지 0의 개수를 구하는 문제이다. 딱 보자마자 N! 을 구하여 저장한 후, 문자열로 변환시킨 후 맨뒤에서부터 0의 개수를 세는 알고리즘을 생각했다.그러나 N이 20 언저리를 넘어가는 순간부터 답이 이상해진다. 이는 N의 범위가 500까지이므로 파이썬이 아닌 이상 가장 큰 자료형으로도 N! 을 담을 수 없기 때문이다. (저장한 값이 중간에 잘려버림) 따라서 N! 을 소인수 분해하여 해결해야..
알고리즘 분류: 구현 문제 링크: https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 【 풀이 】 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 가 저장되어 있는 배열(세트)을 이용해 몇 개의 세트로 주어진 방 번호를 만들 수 있는지를 구하는 문제이다. 우선 각 숫자들의 등장 횟수를 세기 위한 배열을 하나 선언한다.그 후 각 숫자들을 문자로 저장, 입력받은 숫자를 반복문을 통해 검사하며 각 숫자의 등장 횟수를 센다.그런 다음 그 배열에서 최댓값을 출력해주면 끝이다. 다만 6과 9는 각 수가 세트에 존재하지 않을 때(이미 썼을 때) 바꿔 쓸 ..
알고리즘 분류: 수학, 구현, 정수론 문제 링크: https://www.acmicpc.net/problem/9506 9506번: 약수들의 합 어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다. n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라. www.acmicpc.net 【 풀이 】 수를 하나 입력받고, 그 수의 약수들의 합이 입력 받은 수와 일치하면 그 합을 출력하는 문제이다. 숫자 n을 입력받고, 1부터 n까지 숫자를 돌려가면서 n과 나누어 떨어지는 수가 있다면 배열에 저장한다. 그 후 배열에 저장된 수의 합을 구하고, n과 같은지 다른지 조건문으로 예제와 같이 출력하면 된다. 【 코드 】 #includ..