인프런 커뮤니티 질문&답변
작성한 질문수
666영화제목 - 시간복잡도 질문
작성
·
313
0
for 무한루프가 1,000,000 (백만번) 크기 규모로 실행되므로
(실제로는 2,666,799번, 어림잡아서 6,660,000번)
총 연산이 1억이 되지 않으려면 for내부에서는 100번 이하 규모로 연산이 이뤄져야만 한다고 판단했습니다.
모범답안 for문 내부에 있는 string.find("찾을문자열") 의 연산횟수를 100이하로 보신건지 궁금합니다.
답변 1
0
안녕하세요. 원진님. ㅎㅎ
총 연산이 1억이 되지 않으려면 for내부에서는 100번 이하 규모로 연산이 이뤄져야만 한다고 판단했습니다.
#include<bits/stdc++.h>
using namespace std;
int n;
int main() {
cin >> n;
int i = 666;
for(;; i++){
// 이 연산은 O(i의 자릿수)짜리입니다.
if(to_string(i).find("666") != string::npos)n--;
if(n == 0)break;
}
cout << i << "\n";
}주석을 달았는데요. 100번이하라는 게 좀 애매한데요. 시간복잡도를 기준으로 보시는게 좋습니다.
저 i가 만약에 엄청나게 큰 자릿수라면 문제가 되지만 저 i자체가 그렇게 커지지 않기 때문에 해당 find연산은 O(1)이라고 봐도 무방합니다.
예를 들어 10000이라고 하면
2666799
가 나오게 되는데 이는 7자릿수밖에 안되거든요. 따라서 해당 연산은 O(1)이라고 봐도 무방했기 때문에 해당 연산에 대한 고려는 안해도 무방하다 생각했고 for반복문의 횟수만을 생각했습니다.
감사합니다.
양심고백하자면 O(n)인지 몰랐습니다ㅠㅠ
구글링해보니( https://rein.kr/blog/archives/373 )
대상문자열 길이 n, 찾을문자열"666"의 길이m 이라하면
O(n*m)이라고 하더라고요. 여기서 n=최대 7 , m=3 인데 그럼 O(21)이란 소린가.... 엉뚱한 길로 빠졌습니다ㅎㅎ
답변을 통해 다시 길 찾았습니다.
감사합니다^^
배열의 경우 n번째 요소를 찾기위해 0번 위치부터 n번의 탐색없이 단번에 A[n-1] 위치에 값을 조회할 수 있어서 O(1) 인 것처럼
string의 find도 O(1)이라고 하신다면, 위와 같은 맥락으로 이해해보려해도 어렵네요ㅠㅠ
O(1)이라면 문제의 풀이법은 당연하게도 이해가 됩니다.
하지만 "7자리수밖에 안되거든요. 따라서 해당연산은 O(1)이라고 봐도 무방" 하다는 설명이 잘 이해가 되지 않습니다.
7자리수가 넘어가면 O(1)이 아닌 다른 시간복잡도를 갖을 수도 있는데 find의 시간복잡도를 진단하는 방법을 더 자세히 알수있을까요? 관련 링크가 있다면 그것으로 참고하겠습니다.
감사합니다.