'알고리즘'에 해당되는 글 2건
- 2009/01/11 [Algorithm] JAVA로 구현한 해싱(Hashing) - 1
- 2008/02/05 기본기능만 있는 테트리스 프로그램 완성~!! (1)
* 해싱의 원리
해싱(Hashing)은 데이터의 규묘에 관계없이 삽입, 검색, 삭제를 일정시간 내에 할 수 있는 알고리즘 이다. 키값을 데이터가 저장된 위치(배열의 첨자)에 직접 연관 짓는 것이 해싱의 원리로 선형탐색, 이진탐색과는 근본적으로 다르다.
100개의 사이즈를 가지는 배열안에 데이터를 저장한다고 했을 때를 생각해 보자. 여기에 들어갈 수 있는 키값(배열의 첨자)은 0~99 까지의 정수이다. 그러나 이 것은 어디까지나 인위적인 설명을 하기위한 설정으로 실제로 키값을 배열의 첨자로 바로 쓰는 경우는 거의 없다. 그래서 키값 X를 배열의 첨자로 변환하는 함수 h(x)를 사용한다. 이 함수를 해시함수(hash function)라 한다. 또 해시함수가 반환하는 값을 해시 값(hash value)이라고 한다.
해시함수 h(x)가 준비되면 키값을 이용하여 배열에 데이터를 저장할 수 있다. 데이터를 저장할 배열 table이 있다고 하면 table[h(x)] 와 같은 방식으로 저장된다.
* 충돌
해싱의 원리를 설명했지만, 해싱에는 중대한 결함이 있다. 그것은 키값은 다르지만 해싱함수에 의해 같은 해시값을 생성할 가능성이 있다는 것이다.
다음은 100개의 배열에 저장하기 위해 간단 해시함수를 만들어 one ~ ten 까지의 키를 테스트 한 결과이다.
|
public class HashTest { public static void main(String[] args) { HashTest hash = new HashTest(); System.out.println("one
= " + hash.hash("one")); System.out.println("two
= " + hash.hash("two")); System.out.println("three
= " + hash.hash("three")); System.out.println("four
= " + hash.hash("four")); System.out.println("five
= " + hash.hash("five")); System.out.println("six
= " + hash.hash("six")); System.out.println("seven
= " + hash.hash("seven")); System.out.println("eight
= " + hash.hash("eight")); System.out.println("nine
= " + hash.hash("nine")); System.out.println("ten
= " + hash.hash("ten")); } int hash(String key) { int sum = 0; for (int i = 0; i < key.length(); i++) { sum += (int) key.charAt(i); } return sum % 100; } } |
위 예제에 대한 결과값은 다음과 같다.
| one = 22 two = 46 three = 36 four = 44 five = 26 six = 40 seven = 45 eight = 29 nine = 26 ten = 27 |
위 결과에서 five, nine의 값이 26이 되어버렸다. 이와 같이 다른 키에 대해 같은 해시값을 얻는 경우를 충돌 이라고 한다. 충돌이 일어났을 때 대책을 세우지 않는다면 해싱은 사용 할 수 없다.
충돌에 대한 대책은 두가지가 있다. 첫번째로 같은 해시값을 가지는 데이터를 연결리스트로 연결시켜 두는 것이다. 이를 체인화(Chaining)이라 부른다. 두번째 방법은 해시값에 대응하는 배열이 이미 차있다면 어떤 절차에 따라 다른 배열에 데이터를 저장하는 것이다. 이를 오픈어드레싱(open Addressing) 이라 부른다.
Tetris.java9시부터 6시까지 빡센 수업이 계속됐고.. 첫달은 자바 기초부터 스윙까지 엄청나게 빠른속도로..
수업이 진행되었다.. -0-;;
그 와중에 어떻게든 뭐하나 만들어보려고 발악했으니~!!
쉽다면 쉽고 어렵다면 어려운 테트리스를 만들어보려고 시작한지 일주일-_-;;
만들다 실패해서 설계를 뒤집어 드디어 테트리스의 기본기능만 있게 완성 -_-V
아래는 그 캡쳐사진~.~;;
테트리스 Beta Ver 0.5
처음엔 paint를 이용하여 repaint메서드를 이용해서 아이템블록이 이동할때마다 다시 그리는방식으로
하려고 하였으나 버그가 많이나와서 G-_-G치고 설계를 뒤집었음 -0-;;
그래서 각 블록하나를 JPanel로 만들어서(무식하게-_-) Thread를 이용하여 이동시키는 방식으로 바꿨음~
첨부파일에는 Tetris.java와 Item.java 파일 두개가 올라가 있습니당~
Item.java 파일..
1. Block 클래스
-> 블록의 X, Y정보를 담고 있는 클래스 X,Y를 계산하거나 좌표를 반환한다.
2. Item 클래스 : (아이템이 아이템이 아니라 모양하나하나를 말함-_-; 일자, 사각형 ...)
-> 블록객체와 판넬객체의 정보로 아이템을 만든다.
-> 아이템의 각 기능들을 명시 ( 밑으로이동, 회전, 오른쪽이동, 왼쪽이동 등)
3. Rect, OneThree 등등..
-> Item클래스를 상속받아 포인트정보를 입력하여 아이템을 완성.
Tetris.java 파일..
- Tetris 클래스
-> ArrayList를 이용하여 아이템객체와 컬러리스트를 생성.
-> 아이템의 현재위치정보를 받아 이동할 곳의 위치가 이동가능한 곳인지를 체크하는 메서드 아래,왼쪽,오른쪽,회전
-> 아이템 새로 나오는 함수, 줄없애기 체크 함수, 줄없애기 함수 등..
-> 키리스너로 이동함수 호출 (좌, 우, 아래, 위, 스페이스)
- 구현한 주요 알고리즘을 대략 설명하면..
* 1~4 생성자부분
1. JPanel을 블럭 갯수만큼 백그라운드에 2차원 배열로 생성후 위치셋팅 ( 하얀색으로 셋팅)
2. boolean 변수에 2차원 배열 grid 생성. (해당위치에 블록이 있고없음을 체크하기 위함.)
3. 아이템클래스에서 상속받은 각각의 객체들을 생성하여 ArrayList에 셋팅.
4. 아이템중 랜덤으로 대기위치셋팅, 다음나올아이템 셋팅.
5. 쓰레드 생성후 스타트.
* 6~7 run() 함수로 인하여 게임 종료때까지 루프
6. 셋팅한 시간마다 현재선택된 아이템을 한칸씩 밑으로 내린다. (체크후 내림)
1)
7. 밑으로 내릴때 더이상 내릴곳이 없다면
1) 현재아이템정보를 백그라운드에 셋팅
가) 현재아이템의 색정보를 받아와 백그라운드 해당 위치에(판넬) 색을 바꿈
나) 현재아이템의 위치정보를 받아와 grid 배열의 해당위치 변수를 true로 바꿈.
2) 줄없애기 체크
가) grid배열을 한줄씩 체크, 한줄모두 true함수면 해당 줄 번호로 줄없앰 함수 호출
나) 해당줄을 템프변수에 담고 그 위의 백그라운드판넬과 grid함수를 한칸씩 내림.
다) 템프에 담겨놓은 것을 맨 위에줄로 올림.
3) 다음 아이템 셋팅
가) 현재아이템을 안보이는(Ready) 위치로 옮김.
나) 다음위치에 있던 아이템을 시작(Default)위치로 옮김
다) itemList에 있던 아이템을 랜덤으로 추출하여 랜덤으로 색을 입히고 다음(Next)위치로 옮김.
8. 키이벤트 리스너를 등록하여 이벤트가 발생할때마다 해당 이벤트 함수 호출
스페이스바 -> Down이벤트 호출 (끝을 만날때까지)
왼쪽 -> Left이벤트 호출
오른쪽 -> Right이벤트 호출
위쪽 -> Rotate이벤트 호출
나름 객체지향적으로 설계하려고 최대한 노력하였으나 곳곳에 삽질흔적이 발견되는군요 -0-;;
코드에 문제점이나 보완할점 발견되면 가차없이 이의제기해주세용 ^^;
Prev
Rss Feed
