백준 알고리즘 7615번 해싱 탐색 자바 JAVA 메모리 초과 문제

 

 

 

백준 알고리즘 7615번은 해싱탐색 알고리즘으로 풀어보는 문제다. t,a,b,x,n,c,d,m 총 8개의 입력값이 주어지는데, t번 순회를 돌면서 a부터 m까지 입력된 변수들을 토대로 해싱함수를 정의하게 된다.

 

해시탐색(Hash Search)

해싱함수를 사용해서 데이터를 검색하는 방법이다. 기존의 탐색법과는 다르게 데이터의 내용과 인덱스를 미리 연결해서 짧은 시간안에 탐색이 가능한 알고리즘이다. 적절한 해싱 함수를 이용해서 데이터의 저장 위치를 결정한다. 결정된 저장 위치가 중복 혹은 충돌 되는 경우 다른 조치를 필요로 한다. 해시탐색 알고리즘의 시간복잡도는 n(1)이다. 입력값에 따라 연산의 횟수가 증가하지 않고 일정하다.

 

해싱함수는 6가지 종류로 나뉜다.

• 제산법(Division) : 키를 특정 값으로 나눈 나머지 값으로 저장할 위치를 결정하는 바업이다. 해시 테이블의 크기, 소수, 전체 데이터 수 등을 사용한다.
• 폴딩법(Folding) : 키를 여러 부분으로 나눠서 부분별 숫자의 합연산이나 XOR 연산의 결과로 위치를 결정하는 방법이다.
• 제곱법(Square) :  키를 제곱한 결과의 일부분으로 위치를 결정하는 방법이다.
• 숫자 분석법(Digit Analysis) : 키의 숫자 분포를 파악해서 분포가 고른 부분을 이용하여 위치를 결정하는 방법이다.
• 기수 변환법(Radix Conversion) : 키의 값을 다른 진법으로 변환해서 얻은 결과값으로 위치를 결정하는 방법이다.
• 의사 무작위법(Pseudo Random) : 난수를 이용해서 위치를 결정하는 방법이다.

해싱함수를 사용해서 탐색알고리즘을 설계하는 경우 충돌을 최소하하고 계산이 너무 복잡하지 않고 빠르게 처리되야 한다는 조건이 있다.

 

추가 해시탐색(Hash Search) 알고리즘 용어들

해시테이블(Hash table)	- 해싱 함수를 통해 구해진 위치에 각 데이터(레코드)를 저장한 테이블이다.
슬롯(Slot)	- 하나의 데이터를 저장하는 공간을 말한다.
버킷(Bucket)	- 여럿의 슬롯이 모인 공간을 의미한다. - 하나의 주소를 갖는 파일의 한 구역이다. - 버킷 주소를 홈 주소나 해싱 주소라고도 한다.
동의어(Synonym)	- 같은 버킷에 저장된 서로 다른 값들을 말한다.
충돌(Collision)	- 서로 다른 데이터가 같은 키를 가진 현상이다. - 프로빙(Probing)이란 충돌이 발생한 데이터를 다른 버킷으로 저장하는 방법이다.     1) 1차 조사법 : 순차적으로 비어있는 다음 공간에 저장한다.     2) 2차 조사법 : 조금 더 멀리 떨어진 공간에 저장한다.
오버플로우(Overflow)	- 한 버킷 내에 더 이상의 데이터를 저장할 슬롯이 없는 상태에서 추가 데이터를 저장하는 경우 발생하는 오류 상태를 말한다. - 체인법(Chaining)은 오버플로우를 해결하기 위해 연결 리스트로 버킷을 연결하는 방법이다.

 

백준 알고리즘 7615번은 해시탐색의 제산법을 이용해서 함수값을 구하는 방법이지만, 탐색알고리즘이 아닌 주어진 숫자 범위 중에서 해싱값이 몇개인지만 분석하는 알고리즘 문제다.

 

 

Java Code

 

8개에 달하는 입력값을 Scanner클래스를 통해서 받아온다. for문을 순회하면서 hash(x)부터 hash(x+n)개의 해시 값들을 구해온다. 이 후 해당 해시값이 특정 범위의 숫자 내부에 속하는지 검사한 후 StringBuilder에 저장한 값을 출력한다.

 

VisualCode에서 코드를 테스트 했을 때는 정상적으로 값이 출력되지만, 문제가 발생한다. 백준 코딩 웹에서 제출을 하면 메모리 초과 문제가 발생한다. 동적계획법도 아니고, DFS, BFS도 아닌 간단한 알고리즘인데 메모리 초과 문제가 발생하는게 신선하다. 아직 문제를 해결하지 못했고, 구글링을 해봐도 전역변수나 정적변수를 사용하지 말라는 내용이 있어 수정해봤지만 메모리 초과 문제가 해결되지 않았다.

import java.util.Scanner;

public class A_7615 {  
    public static void main(String[] args){
        // 결과값 출력을 위한 StringBuilder
        StringBuilder sb = new StringBuilder();
        // Scanner 클래스로 입력 받음
        Scanner sc = new Scanner(System.in);
        // 출력값 hashCounter 지역변수 선언
        int hashCounter;
        // t번 수행되는 회수값
        int t = sc.nextInt();
        while(t>0){
            try{
                hashCounter=0;
                // 해싱함수 정의에 필요한 변수값들 입력
                int a = sc.nextInt();
                int b = sc.nextInt();
                int x = sc.nextInt();
                int n = sc.nextInt();
                int c = sc.nextInt();
                int d = sc.nextInt();
                int m = sc.nextInt();

                // 해싱값 정의
                // c<= 해싱값 <=d 조건에 참이면 hashCounter++
                for(int j=0; j<n+1; j++){
                    int X = (a*(x+j)+b)%m;
                    if( X>= c & X<=d) hashCounter++;
                }

                sb.append(hashCounter+"\n");    
                t--;
            }catch(Exception e){
                e.getMessage();
            }
            
        }
        // 결과값 출력
        System.out.println(sb);        
    }
}

출력값

// 입력값
2
2 3 1 3 0 1 7
1 0 0 8 0 8 9
// 출력값
1
9

Error Occured