글 읽기 - 배열로 문제를 푸는 경우와 리스트로 문제를 푸는 경우 시간 차이 질문.

julysky 4년 전 0

안녕하세요, 친구랑 같이 이 문제를 푸는 도중에 궁금증이 생겨서 글 납깁니다.

평소에 리스트보다 배열이 항상 빠르다고 생각했기 때문에, 용량이 가능하다면 리스트보다는 배열로 문제를 풀곤 했습니다.

물론 이문제에서 다음과 같은 구조로 문제를 푼다면 배열을 사용할 때 메모리를 초과해서 리스트를 이용해서 풀어야하지만, 문제의 input data가 편향되어있지 않은지 배열의 범위를 600으로 잡으면 해결은 되더라고요.

그런데, 리스트로 풀 때 보다 배열로 문제를 풀었을 때 시간이 오히려 2배이상 느리게 나오는 것을 경험했습니다.

제 경험상 배열이 대체로 리스트보다 빠르게 동작 했었는데, 이 경우 왜이렇게 느려진 것인지 궁금합니다.

아래 코드의 구조는 완전히 똑같고 리스트, 배열 차이뿐입니다.

//정적할당을 이용한 리스트 172ms 
//https://www.acmicpc.net/source/17929822

#include <stdio.h>
struct node
{
    int data;
    node* next;
};
node up[100001];
node down[100001];
node arr[1000001];
int idx;
int queue[100001];
int visit[100001];
node* myalloc()
{
    return &arr[idx++];
}
 
int main()
{
    int N, M, X;
    register int i, data, j;
    scanf("%d %d %d", &N, &M, &X);
    for (i = 1; i <= M; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        node* upd = myalloc();
        node* downd = myalloc();
        upd->data = b;
        upd->next = up[a].next;
        up[a].next = upd;
 
        downd->data = a;
        downd->next = down[b].next;
        down[b].next = downd;
    }
    i = 1;
    j = 0;
    queue[0] = X;
    visit[X] = 1;
    while (j < i)
    {
        node* iter = &up[queue[j++]];
        while (iter->next != NULL)
        {
            iter = iter->next;
            data = iter->data;
            if (visit[data] == 1) continue;
            visit[data] = 1;
            queue[i++] = data;
        }
    }
    int downcnt = N - i + 1;
    i = 1;
    j = 0;
    queue[0] = X;
    while (j < i)
    {
        node* iter = &down[queue[j++]];
        while (iter->next != NULL)
        {
            iter = iter->next;
            data = iter->data;
            if (visit[data] == 1) continue;
            visit[data] = 1;
            queue[i++] = data;
        }
    }
    int upcnt = 1 + i - 1;
    printf("%d %d\n", upcnt, downcnt);
}



/* 배열. 484ms
https://www.acmicpc.net/source/17960851

#include <stdio.h>

int up[100001][600];
int ucnt[100001];
int down[100001][600];
int dcnt[100001];
int queue[100001];
int visit[100001];

int main()
{
	int N, M, X;
	register int i, data, j;
	scanf("%d %d %d", &N, &M, &X);
	for (i = 1; i <= M; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		up[a][ucnt[a]++] = b;
		down[b][dcnt[b]++] = a;
	}
	i = 1;
	j = 0;
	queue[0] = X;
	visit[X] = 1;
	while (j < i)
	{
		int d = queue[j++];
		int cnt = ucnt[d];
		for(int k=0;k<cnt;k++)
		{
			data = up[d][k];
			if (visit[data] == 1) continue;
			visit[data] = 1;
			queue[i++] = data;
		}
	}
	int downcnt = N - i + 1;
	i = 1;
	j = 0;
	queue[0] = X;
	while (j < i)
	{
		int d = queue[j++];
		int cnt = dcnt[d];
		for (int k = 0; k < cnt; k++)
		{
			data = down[d][k];
			if (visit[data] == 1) continue;
			visit[data] = 1;
			queue[i++] = data;
		}
	}
	int upcnt = 1 + i - 1;
	printf("%d %d\n", upcnt, downcnt);
}



*/

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

문제

문제

출처

ICPC

배열로 문제를 푸는 경우와 리스트로 문제를 푸는 경우 시간 차이 질문.

julysky 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말