작성한 질문수 79

1

안녕하세요 유태님 ㅎㅎ

	for (ll i = 0; i < N; i++)
	{
		cnt++;
		for (ll j = i + 1; j < N; j++)

이 코드의 시간복잡도는 O(N^2)이고 N의 시간복잡도는 10만이라 100억정도의 시간복잡도를 가지는 코드입니다.

시간복잡도를 개선해주셔야 합니다.

		for (ll j = i + 1; j < N; j++)
		{
			if (arr[j] != arr[i]) cnt++;

그리고 이 로직만으로는 1 2 2 와 같은 경우의 수를 체크하지 못합니다.

{1, 2}

{1, 2, 2}

의 경우의 수 다 카운트 되지 않을까요?

감사합니다.

0

안녕하세요, 인프런 AI 인턴입니다.

한유태님, 완전탐색을 이용하여 문제를 해결하려 하였으나 올바른 결과가 나오지 않아서 고민이시군요. 완전탐색은 모든 가능한 경우를 고려하여 답을 찾는 방법으로, 특정 유형의 문제에서는 효율적이지 않을 수 있습니다.

문제를 해결하기 위해 다음 몇 가지를 고려해 보시면 좋겠습니다:

1. 시간 복잡도: 완전탐색은 일반적으로 비효율적이기 때문에, 입력 크기에 비해 시간이 많이 걸릴 수 있습니다. 문제에서 요구하는 시간 내에 수행 가능한지 확인해 보세요.

2. 잘못된 구현: 코드에서 인덱스 범위 또는 조건문에서 실수가 있을 수 있습니다. 예를 들어, 배열 인덱스 범위를 초과하거나 잘못된 조건으로 인해 논리적 오류가 발생할 수 있습니다.

3. 다른 접근법: 만약 완전탐색이 비효율적이라면, 다른 알고리즘적 접근이나 최적화가 필요한지 고민해 보세요. 가능한 데이터 구조의 활용을 고려해 보세요.

이 문제와 유사한 문제나 다른 학습자의 토론을 참고하고 싶으시면, 약간의 수정 또는 최적화 기법을 공유한 게시물을 참고하시면 도움이 될 수 있습니다:
- 5-D 질문드립니다 :)

위의 질문에서 해결했던 방식이나 제안된 코드가 도움이 될 가능성이 큽니다. 해결책을 보완하여 적용해 보시기를 권장드립니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.