[백준/C++] 1016번. 제곱 ㄴㄴ 수
문제 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 1. 첫 번째 풀이 사고 과정 - 가장 먼저 떠올린 방법은 범위 내의 수를 모든 제곱수를 나눠보는 것이다. min의 최댓값이 1,000,000,000,000(1조)이기 때문에, 가장 큰 제곱수는 1,000,000(백 만)의 제곱인 1조이다. 최악의 경우 1,000,001개의 수를 각각 1,000,000번씩 나눠봐야 한다. 시간복잡도로 따지면 O(n^2)겠지만, 최대 1조 번의 연산이 필요하므로 다른 방법을 찾기로 했다. - 그 다음으로 떠올..
[백준/C++] 1015번. 수열 정렬
문제 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 1. 첫 번째 풀이 사고 과정 - 설명을 이래저래 돌려놨지만, 결국 가장 작은 수부터 0, 1, 2, ..., N-1을 대입한다는 소리 - 가장 간단한 방법은 min_element를 사용하는 것이다. 1. 배열 A, P를 생성한다. 2. 정수 i, c = 0을 선언한다. 2. 배열 A를 입력받는다. 3. A 내에서 min_element를 적용, 최솟값의 인덱스 i를 얻는다.. 4. P[i]에 c를 대입하..
[백준/C++] 1094번. 막대기
문제 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 1. 첫 번째 풀이 (마지막 풀이) 사고 과정 - 막대기의 크기는 2의 지수승만 가능하다. (64, 32, 16, 8, 4, 2, 1) - 몇 번 잘랐는 지가 아닌, 몇 개를 붙였는가를 묻는 문제. - 2진수로 표현 후 1의 개수를 세는 문제. 1. 입력 값을 2진수로 변환 2. 2진수의 1의 개수를 세서 반환 코드 #include int main() { int x, count = 0; scanf("%d", &x); for (int i = 0; i < ..
[백준/C++] 1009번. 분산 처리
문제 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net 1. 첫 번째 풀이 사고 과정 - 길게 늘여썼지만, 결국 a^b의 1의 자리 수를 구하는 문제. - 단, b가 최대 1,000,000인 만큼 연산자만 사용하면 계산할 수 없다. - 모듈러 연산을 안다면 순식간에 풀 수 있다. 어렵게 말할 것 없이 풀어쓰자면 아래와 같다. - 7을 10번 곱했을 때 1의 자리 수는 얼마인가? - 7, 9, 3, 1, 7, 9, 3, 1, 7, 9... 이처럼 1의 자리 수는 계속 반복되는 것을 알 수 있다. - 우선 간단하게 구현해보자..
