자세히 보진 않았지만

질문자 님의 코드는

O(n^3) 의 시간복잡도를 가질 것 같네요.

A1 이란 함수 자체가 O(n^2)인데

그걸 for 문 안에서 또 호출하니까요.

정확히 로직이 어떻게 돌아가는지는 모르겠지만

일단 문제를 보시면 입력으로 주어지는 값이

매우 큰 것으로 보아 이 문제는 최소한 

O(n)으로 풀어야 할 것 같아요.

그리고 1, 2, 3... 번째 수를 나열하다 보면

규칙을 찾으실 수 있을 거에요.

친절한 답변 정말 감사드립니다 ! 그런데 말씀하신 O(n)이 무엇인지 질문드려도 될까요 ?

그리고 제가 1번쨰 2번째 수를 나열해봤는데... 이렇다 할 규칙을 못찾아서 홀수 짝수 나눠서 홀수는 나눴을때 나머지를 기준으로 코드를 작성했고

짝수는 배열로 집어넣어서 작성했습니다... 제가 봐도 제 코드가 정말 어렵긴하네요. 이해 안되시는 부분 있으면 답변 드리겠습니다..

O 는 알고리즘의 시간 복잡도를 나타내는 방법인

Big-O Notation 을 뜻해요.

입력 개수, 혹은 수에 따라 연산이 어떻게 변화할지를 나타내는 (notate) 표기법이에요.

예를 들어 O(n) 은 n 개의 입력 데이터가 들어온다면 그만큼 연산을 해야 한다는 거고

O(n^2) 은 그 제곱만큼 연산을 해야한다는 거에요.

Big-O Notation (빅오 표기법) 은

O(1), O(log n), O(n), O(nlog n), O(n^2) ... 등 다양하게 있어요.

왼쪽으로 갈 수록 빠르고, 오른쪽으로 갈 수록 느린 알고리즘이에요.

O 라는 건 쉽게 말해서

연산의 형태를 의미해요.

n개인 데이터가 있을 때

해당 알고리즘대로 계산하면 연산을 얼마나 수행할까 하고 나타내는 척도지요.

O(n) 이라고 하면, 입력이 n 개면 n 번의 형태로 연산한다는 뜻이에요.

왜 형태라고 했냐면 정확히 n 번 연산한다는 게 아니기 때문이에요. 

2n 번 연산한다 해도 O(n) 이라고 말하거든요. (n의 차수, 그러니까 형태 자체가 바뀌지 않는다면)

그래프를 생각해보시면 이해가 편하실 거에요.

저 문제가 제가 말씀드린대로 O(n^3) 의 시간 복잡도를 가진다면

문제 입력의 최대값인 10,000,000 을 넣었을 때 그 연산 횟수는 대충

10,000,000^3 = (10^7)^3 = 10^21로, 문제가 0.5초만에 끝나지 않을 것 같네요.

(연산 1억번이 대략 1초라고 하네요.)

입력값이 1000만인데, 이걸 0.5초만에 끝내려면

심지어 O(n) 의 알고리즘도 시간 초과를 벗어나기 힘들 것 같네요.

만일 문제의 규칙을 찾는다면

O(1) 의 연산으로 끝날 것 같아요.

왜냐면 입력으로 어떤 수가 들어오든

일정한 수의 연산으로 출력을 만들 수 있잖아요.

자연수 중 n번째 홀수를 구하는 예를 생각해보세요.

이 문제의 답은 n이 몇이 들어오든 n 에 2를 곱하고 1을 뺀 수거든요.

1 이 들어오든 10이 들어오든 10^21 이 들어오든 연산 단 두 번만에 결과가 나와요.

이런 걸 O(1) 혹은 상수 시간 복잡도라고 해요.

만약 이 문제를

1부터 시작해서 2를 n-1번 계속 더해나간다면

O(n) 이 되겠죠?

근데 아무도 이렇게 안 풀죠. 

이미 딱 두 번의 연산으로 푸는 방법이 있는데 누가 n번 연산해서 풀겠어요.

문제는 항상 여러가지 풀이가 있어요.

홀수 구하는 문제를 O(1) 의 방법으로 풀 수도, O(n) 의 방법으로 풀 수 있듯이요.

그 중 항상 최선의 방법을 찾아야 해요. 

최선의 방법이 아니면 문제를 풀었다고 인정하지 않기 위해 

입력 범위와 시간, 메모리 제한이 있는 거에요.