1-N 코드 질문있습니다
안녕하십니까 큰돌님
강의 보기 전에 문제를 풀어봤는데 틀렸다고 나와서 질문드립니다. 최대 범위인 20억 * 20억일 때 long long 범위가 넘는데 pow 반환값을 long long 에 저장해서 틀린게 맞을까요 ?? 그리고 pow함수의 시간복잡도는 어떻게 되는지도 궁금합니다
http://boj.kr/c90ff8da35d3490b859f8ee922c59bf9
답변 3
1
이거 알림이 대댓으로 달면 안떠서 이렇게 답변 드려용.
밑은
log2입니다.
반으로 쪼개지는 걸 생각하시면 됩니다.
답변 수정드릴게 있는데요.
로직 자체는
20억의 20억승이나
pow함수 자체가 log이기 때문에
대기업님이 구축하신 코드의 시간복잡도는 log20억이라고 보시면 됩니다.
1
그리고 pow에 대해 조금 더 자세히 설명드리자면 pow는 다음과 같이 설계되어있습니다.
그렇기 때문에 logb의 시간복잡도를 갖게 됩니다.
int power(int x, unsigned int y)
{
int temp;
if (y == 0)
return 1;
temp = power(x, y / 2);
if (y % 2 == 0)
return temp * temp;
else
return x * temp * temp;
}
1
안녕하세요 대기업님 ㅎㅎ 반갑습니다.
최대 범위인 20억 * 20억일 때 long long 범위가 넘는데 pow 반환값을 long long 에 저장해서 틀린게 맞을까요 ??
>> 네 맞습니다. 근데 조금은 틀려요.
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
자 그러면 20억 * 20억이 아니라 20억의 20억승이 들어갈 수도 있겠죠?
그래서 범위를 초과합니다.
pow함수의 시간복잡도는 어떻게 되는지도 궁금합니다
>> pow(a, b)라고 했을 때 O(logb)가 됩니다.
감사합니다.
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
41
2
2주차 개념#12 트리 순회
0
22
2
백준사이트가 종료된다고 합니다.
0
266
2
백준 서비스 종료
9
840
1
sk 하이닉스 코테 대비
0
366
2
3-G 최댓값 질문
0
50
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
82
2
3-I 코드 질문드립니다.
0
62
2
3-N 질문 있습니다.
0
66
2
학습방법
0
101
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
167
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
64
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
50
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
67
2
함수별 시간복잡도
0
72
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
53
2
1-I 문제 질문 드립니다.
0
76
2
2-P 질문입니다.
0
56
1
mac에서 시작하기 관련
0
91
2
5-Q 질문
0
63
2
풀이 코드 질문
0
64
2