글 읽기 - C에서 Segmentation Fault - Out of Bound 질문입니다

unta 1년 전 0

C에서 직접 해시 맵을 구현해서 풀이를 해보고 있습니다.

그런데 보기에는 잘못될 구석이 없고 테스트 케이스에서도 정상적으로 동작하는 것을 확인했는데 33% 부근에서 Out of Bound 처리가 되어서 제가 놓친 부분이 있을까 싶어 질문 올립니다.

조건문과 exit(1)을 이용하면 특정 구문에서 조건이 만족할 때 NEZC를 발생시켜 문제가 되는 지점을 추측해볼 수 있습니다.

이를 이용해 배열의 인덱스가 초과될 법한 부분을 확인해 보았지만 그럴 듯한 결론을 내지 못하고 있습니다.

문제가 될 것 같은 부분을 대강 추려보자면,

해싱에서 TABLE_SIZE 이상의 인덱스를 반환 -> % 연산으로 범위를 제한하므로 문제 없음.

닫힌 주소 기법에 의한 sub_index의 SUB_TABLE_SIZE 이상의 인덱스 -> 주어진 입력의 개수에 맞추어 설정했으므로 문제 없음.

기타 문자열 관련 인덱스 문제 (최대 20일 때 '\0'를 고려하지 않고 문자열의 길이를 20으로 설정 등) -> 추가로 확인했지만 문제 없음.

+ 배열의 크기 등을 넉넉하게 설정하여 재시도해도 동일한 문제 발생.

으로 감을 못잡고 있는 상태입니다.

감사합니다.

Out of Bounds 발생: http://boj.kr/ba525453095047c1...

동일한 내용을 C++의 라이브러리를 활용해 풀이: http://boj.kr/fb159725fefc4816...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define TABLE_SIZE 100000
#define SUB_TABLE_SIZE 10

#define POKEMON_LEN 100000
#define INPUT_LEN 21

char table[TABLE_SIZE][SUB_TABLE_SIZE][2][INPUT_LEN];

long long hash_string(char* input)
{
    long long hash = 0;
    long long r = 1;
    for (int i = 0; i < strlen(input); i++)
    {
        hash = (hash + (input[i] - 'a' + 1) * r) % 1234567891;
        r = (r * 31) % 1234567891;
    }
    return hash;
}

int get_index(char* input)
{
    return hash_string(input) % TABLE_SIZE;
}

void push(char* input, int num)
{
    int index = get_index(input);
    int sub_index = 0;

    while (sub_index < SUB_TABLE_SIZE && table[index][sub_index][0][0] != '\0')
        sub_index++;

    if (sub_index == SUB_TABLE_SIZE)
        exit(1);

    sprintf(table[index][sub_index][0], "%s", input);
    sprintf(table[index][sub_index][1], "%d", num);
}

void* find(char* input)
{
    int index = get_index(input);
    int sub_index = 0;

    while (sub_index < SUB_TABLE_SIZE && strcmp(table[index][sub_index][0], input))
        sub_index++;

    if (sub_index == SUB_TABLE_SIZE)
        exit(1);

    return &table[index][sub_index];
}

int N, M;
char pokemons[POKEMON_LEN][INPUT_LEN];

int main(void)
{
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++)
    {
        scanf("%s", pokemons[i]);
        push(pokemons[i], i + 1);
    }

    char temp[INPUT_LEN];
    for (int i = 0; i < M; i++)
    {
        scanf("%s", temp);

        if (isalpha(temp[0]))
        {
            char* f = find(temp);
            printf("%s\n", f + INPUT_LEN);
        }
        else
        {
            int n = strtol(temp, NULL, 10);
            printf("%s\n", pokemons[n - 1]);
        }
    }

    return 0;
}

unta 1년 전 0

위의 글을 쓰면서 문득 해시값이 오버플로로 인해 음수가 될 수도 있다는 생각을 했습니다.

확인해보니 오버플로가 발생하여 인덱스가 음수가 됨을 확인하고 unsigned 형을 이용해 문제를 해결했습니다.

그렇다면 hash 함수에서 음수가 발생하지 않도록 조치하는 방법에는 어떤 것이 있을까요?

(첨부한 소스는 unsigned를 이용해 문제를 해결한 소스입니다.)

*사용한 hash 함수는 백준 문제 중 하나인 Hashing에서의 함수를 이용했습니다.

해당 문제에서도 오버플로를 방지하는 차원에서 mod 연산자를 이용했습니다. 때문에 더 큰 입력에 대해서도 큰 문제가 없을 거라고 생각했는데 아니었군요.

해결한 C 소스: http://boj.kr/b567a3eeda964aad...

Hashing: http://boj.kr/b567a3eeda964aad...

unsigned long long hash_string(char* input)
{
    unsigned long long hash = 0;
    unsigned long long r = 1;
    for (int i = 0; i < strlen(input); i++)
    {
        hash = (hash + (input[i] - 'a' + 1) * r) % 1234567891;
        r = (r * 31) % 1234567891;
    }
    return hash;
}

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

문제

문제

출처

ICPC

C에서 Segmentation Fault - Out of Bound 질문입니다

unta 1년 전 0

unta 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말