글 읽기 - 일단 풀긴 풀었는데 시간 복잡도 계산이 잘 안되서 질문드립니다

rmstjd23 5년 전 0

아무렇게나 막 코딩하다가 이제 알고리즘 공부를 제대로 해보려고 하는 학생입니다.

문제분류에 있는 위상정렬이나 우선순위 큐를 잘 몰라서 일단 생각 나는 대로 짜본 코드라 다른분들이 보기 불편하실까 걱정이네요

일단 정답이 뜨긴 했는데 제 계산으로는 최악의 경우가 n(n-1)/2 로 나왔습니다.

그런데 O(n²)임에도 시간이 60ms로 짧게 나와서 놀랐습니다

시간 복잡도 계산이 틀린것 같은데 아래 소스 대로면 시간복잡도가 몇인가요?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct node{
	int value;
	int level;
	bool lose;
	vector<struct node*> downlist;
}Node;


vector<Node*> List;
Node* New;

bool sortrule(Node* a, Node* b)
{
	return a->level < b->level;
}

void link(Node* a, Node* b)
{
	a->downlist.push_back(b);
	b->lose = true; //한번이라도 키재기에서 졌다면 루트가 될수 없음
}
void travel(Node* _node, int _level)
{
	if(_node->level >= _level) //기존에 저장된 깊이가 새로운 루트를 통해 들어온 깊이보다 깊을경우 중지
		return;

	_node->level = _level;
	for(int i=0; i<_node->downlist.size(); i++)
		travel(_node->downlist[i], _level+1);
}

int main()
{
	int N, M;

	scanf("%d %d",&N, &M);

	for(int i=0; i<N; i++)
	{
		New = new Node();
		New->value = i+1;
		New->level = 0;
		New->lose = false;
		
		List.push_back(New);
	}

	for(int i=0; i<M; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);

		link(List[a-1],List[b-1]);
	}
	
	for(int i=0; i<N; i++)
	{
		if(!List[i]->lose)
			travel(List[i], 1);
	}

	sort(List.begin(), List.end(), sortrule);
	
	for(int i=0; i<N; i++)
		printf("%d ",List[i]->value);
	return 0;
}

rhs0266 5년 전 0

맞습니다. 최악의 경우에는 시간초과가 날 코드지만, 그런 데이터가 없어서 나온 것입니다.

rmstjd23 5년 전 0

감사합니다. 한번 더 생각해보고 우선순위큐나 위상정렬을 공부해봐야겠네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

일단 풀긴 풀었는데 시간 복잡도 계산이 잘 안되서 질문드립니다

rmstjd23 5년 전 0

rhs0266 5년 전 0

rmstjd23 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말