대엉코딩

1. 해쉬 테이블이란?

  저장하고자 하는 데이터를 key 와 value 값을 통하여 저장하는 자료구조

  데이터를 저장하고 매우 빠르게 탐색을 수행하기 위한 자료구조 이다.

  여러가지 다양한 컨테이너들 중에 어쩌면 컴퓨터의 저장방식을 가장 닮은 저장방식이라고 생각한다.

  컴퓨터는 결국 모두 숫자(이진수)로 저장을 하고 특정한 규칙에 따라 그 자료를 해석하는 것인데 해쉬 테이블이 

  이와 매우 유사하다.

2. 해쉬 함수 (hash function)

  해쉬 테이블을 구성하는 데 있어 가장 중요한 것이 해쉬 함수(hash function)이다.

  이 해쉬 함수, 즉 알고리즘을 어떻게 짜느냐에 따라 해쉬테이블의 탐색 성능이 좌지우지 된다.

  저장하고자 하는 데이터를 해쉬함수를 이용하여 가공하여 그 결과값을 key로 하여 테이블에 저장한다.

  효율적인 함수를 짜지 못한 경우 최악의 경우 탐색에 O(n)이 소요될 수 있다.

3. 충돌 (Collision)

  우선 해쉬테이블을 만들기 위하여 고정된 크기의 배열을 선언해주는데 저장하고자 하는 데이터의 수가 배열의 크기

  보다 크다면 필연적으로 두개 이상의 데이터간의 충돌이 일어날 수 밖에 없다.

  (물론 위의 경우가 아니더라도 서로 다른 데이터에 대해 동일한 키 값을 만들어 낼 경우 충돌 발생)

  따라서 이 충돌에 대한 것을 어떻게 처리해주느냐가 매우 중요한 문제이다.

  그러면 충돌을 해결하는 방법을 알아보자.

3-1. Chainig 방식

  이름에서 주는 느낌그대로 해쉬테이블 에서 각각의 컨테이너를 링크드 리스트로 선언하여

  저장하고 하는 테이블 인덱스에 이미 다른 데이터가 자리하고 있을경우 그 데이터의 뒤쪽에 연결해서

  체인처럼 매달아 주는 방식이다.

  탐색을 할 때는 찾고자 하는 key값에 해당하는 리스트에서 원하는 값을 탐색한다.

  데이터의 수가 상대적으로 많아질 경우 링크드리스트가 아닌 tree 구조를 이용하여 탐색시간을 줄일 수도 있다.

  공간에 대한 제약이 적다.

3-2. Open addressing 방식

  1. linear probing 

  충돌이 발생했을 때 테이블에서 그 키 값의 뒤쪽 index의 버켓 중 빈 곳을 찾아 넣는 방식입니다.

  탐색을 할 때 찾고자하는 데이터의 key값에 해당하는 버켓에 갔을 때, 원하는 데이터가 아닐 경우 그 뒤쪽으로 탐색을 시작합니다.

  그리고 삭제처리를 할때 신경을 써주어야 하는데 단순히 삭제를 해주는 것이 아닌 dummy 데이터를 넣어 원래 비어있던 곳인지

  다른 데이터가 있었다가 삭제가 된 곳인지 구분을 해주어야 탐색을 할 때 문제가 생기는 것을 방지할 수 있습니다.

  2.double hashing

   단순히 충돌이 발생한 뒤쪽에서 부터 빈 곳에 넣는 linear probing과 달리 2차 해쉬 함수를 통해서 새로운 키 값을 구해서

   첫 번째 key값에서 2차 해싱 값만큼 jump하여

   테이블에 저장하는 방법 이다. (물론, 또 충돌이 발생할 수는 있습니다.)

4. hash function (해쉬 함수)

  결국 좋은 해쉬 함수란 데이터들의 특성에 맞게 데이터를 되도록이면 고르게 분포시킬 수 있도록 하여,

  충돌을 최소화 할 수 있게 해주는 함수 이다.

www.acmicpc.net/problem/14890

1. 풀이방법.

- 말 그대로 그냥 문제 조건을 구현해야 하는데...

- 처음엔 왼쪽으로 쭉한번보고 오른쪽으로 쭉한번보고 위아래도 마찬가지로 하면된다 생각했었는데

- 223322 [L=2] 같은 경우가 안되는 것을 보고 접근 방식을 바꿨습니다.

-높이가 1차이 나는 친구를 만날경우 나보다 큰 친구면 나부터 뒤쪽을 보고

- 나보다 작은 친구면 나의 앞쪽부터 L만큼을 살펴 보았습니다.

2. 주의사항

- 나보다 큰 친구, 작은친구 의 분류로 나눠서 확인할 때, 저는 현재 위치를 INIT 앞쪽 친구를 loadmap[i][j]로 두었기 때문

- 에 비교문에서 값에 신경을 써야했습니다.

- 문제에 다양한 예시입력이 있어서 다행이었습니다.....아니였으면 꽤 오래 답을 찾아야 했을 것 같습니다.

- 후....문제에 대한 아이디어가 생각나면 그 아이디어로 해결이 될 것만 같은 [즉, 예외되는 사항이 발생하는 경우 를 잘

-떠올리지 못하는 것 같습니다]

- 코드를 작성하기 전에 한번 더 생각해보고 천천히 접근하자.....!

3. 나의코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int N;
int loadmap[101][101];
int L;
int result = 0;
int init;
bool check;
bool checkrow[101];

void inputs() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> loadmap[i][j];
		}
	}
}
int gap(int a, int b) {
	if (a > b) return a - b;
	else { return b - a; }
}
void initcheck() {
	for (int i = 0; i < 101; i++) {
		checkrow[i] = 0;
	}
}
void lookr() {
	for (int i = 0; i < N; i++) {
		initcheck();
		init = loadmap[i][0];
		check = true;
		for (int j = 1; j < N; j++) {
			if (init == loadmap[i][j]) { init = loadmap[i][j]; continue; }
			if (gap(init, loadmap[i][j]) == 1) { //높이1차이
				if (init < loadmap[i][j]) { //벽을 만남(나보다 큰)
					if (j - L < 0) { check = false; break; }
					else {
						for (int k = 1; k <= L; k++) {
							if(checkrow[j-k]==true || loadmap[i][j - k] != init)
							 { check = false; break; }
						}
						for (int k = 1; k <= L; k++) {
							checkrow[j - k] = true;
						}
						if (check == false) break;
					}
				}
				else { //나보다 작은 친구를 만남
					if(j+L>N) { check = false; break; }
					else{
						for (int k = 0; k < L; k++) {
							if (checkrow[j+k]==true||loadmap[i][j + k] != init-1)
							{ check = false; break; }
						}
						for (int k = 0; k < L; k++) {
							checkrow[j + k] = true;
						}
						if (check == false) break;
						j += L-1; //앞에다가 경사로를 놓았을 경우 점프가 필요
					}
				}
			}
			else {check = false; break;} //높이1차이 이상
		init = loadmap[i][j];
		}
		if (check == true) { result++;  }
	}
}
void looku() {
	for (int i = 0; i < N; i++) {
		initcheck();
		init = loadmap[0][i];
		check = true;
		for (int j = 1; j < N; j++) {
			if (init == loadmap[j][i]) { init = loadmap[j][i]; continue; }
			if (gap(init, loadmap[j][i]) == 1) { //높이1차이
				if (init < loadmap[j][i]) { //벽을 만남(나보다 큰)
					if (j - L < 0) { check = false; break; }
					else {
						for (int k = 1; k <= L; k++) {
							if (checkrow[j - k] == true || loadmap[j - k][i] != init)
							{
								check = false; break;
							}
						}
						for (int k = 1; k <= L; k++) {
							checkrow[j - k] = true;
						}
						if (check == false) break;
					}
				}
				else { //나보다 작은 친구를 만남
					if (j + L > N) { check = false; break; }
					else {
						for (int k = 0; k < L; k++) {
							if (checkrow[j + k] == true || loadmap[j + k][i] != init - 1)
							{
								check = false; break;
							}
						}
						for (int k = 0; k < L; k++) {
							checkrow[j + k] = true;
						}
						if (check == false) break;
						j += L-1; //앞에다가 경사로를 놓았을 경우 점프가 필요
					}
				}
			}
			else { check = false; break; } //높이1차이 이상
			init = loadmap[j][i];
		}
		if (check == true) { result++;  }
	}
}

void checkingload() {
	lookr();
	looku();
	cout << result;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> L;
	inputs();
	checkingload();
	return 0;
}

* 벡터(Vector) 란 ?

- 배열의 확장 느낌으로서 시퀀스 컨테이너의 대표적인 자료구조이다.

-  동적배열과 유사하다

- 자료들(data)가 구조적으로 인접한 위치에 있기 때문에 접근이 쉽고 메모리를 효율적으로 관리가능하다

- 배열과 같이 index를 통한 요소(data) 접근이 가능하다 .(매우 편리, 접근이 용이)

- 만약 맨뒤에 삽입이 아닌 맨 앞이나 중간, 임의의 위치 등에 삽입을 하려고 하는 경우 다른 요소들도

  재조정을 해야 하기 때문에 느리다 (비 효율적)

- 임의의 위치에 삽입, 삭제 등이 많이 일어나는 경우 벡터보다는 리스트를 활용하는것이 효과적이다.

* 벡터 ADT

- at( x ) (index가 x인 위치의 자료형 리턴)

- set(int x, object o) (index x의 위치에 o라는 객체 assign)

- insert(int i, object o) (index i의 위체서 o라는 객체 삽입)

- erase(int i) (index i에 있는 객체 삭제)

- size() (vector 의 사이즈 리턴)

- empty() (비어있는지 확인 -bool)

- push_back(object o) (vector 맨 끝에 삽입)

* ADT 시간복잡도 분석

- at(i),  set(i,0)   ----> O(1) ( vector는 index로 접근 가능 하므로 at, set은 모두 직접 접근하여 O(1) 타임에 가능하다.

- insert(i,o)  ----> O(n) (임의의위치 i에 자료를 삽입하는 경우 원래의 i위치 부터 끝까지 있던 자료들을 모두 한칸씩 뒤로 밀린다.)

-erase(i)  ----> O(n) (역시 비슷한 느낌입니다 ---앞으로 땡겨줘야함 )

* 벡터 활용의 예

- 정렬된 객체들의 집합들을 관리 해야할 때

* 벡터의 구현

<잘못된 부분이 있을 수 있습니다>

<알려주시면 수정 하겠습니다>

기본 크기를 64(index) 로 하고 만약 입력을 받다가 이크기를 넘어가게 되면

배열의 크기를 두배로 늘리고 기존의 자료구조들을 모두 옮기는 식으로 구현하였습니다.

* 스택이란 ?

- LIFO(Last In First Out)

- 떠올리기 쉬운것은 주방에 쌓여있는 식기를 놓으면 좋다. 

- 설거지를 해서 위에 쌓으면 사용을 할 때는 위에서 부터 하나씩 가지고 간다.

* 스택의 연산

- 삽입, 삭제, 비어있는지 확인, 상단 확인, 크기 등의 연산이 있다.

- 객체 : 후입선출(LIFO)의 접근 방법을 유지하는 요소들의 모임

   연산 : push(x)

               pop()

               size()              

               peek() -> 스택 상단에 위치한 요소를 반환(봄) (스택이 비어있지 않으면)

    시간복잡도 : size()를 제외하고는 모드 O(1)이라고 할수 있습니다.

                            size()는 어떻게 구현하느냐에 따라 다를 수 있습니다.( 배열이나 연결리스트)

- 말이 나와서 하는 것이지만 추상자료형 (Abstract Data Type)은 사실 어떻게 구현하느냐는 사용자는 알 수 없습니다.

   제가 배웠던 것을 항상 떠올릴 때는 문 밖에서 어떠한 입력을 넣고 요구를 하면 안에서는 어떤식이던지 구현을 하여

   정확한 결과만을 문 밖으로 다시 보내주는 것 입니다. 사용자는 결과를 받지만 내부에 어떤식으로 이를 처리 하였는지는

   알 수 없지요

* 스택 활용의 예

- 문서나 그림, 수식 등의 편집기에서 되돌리기 기능

   (최근 사용했던것 부터 다시 되돌리기를 합니다. -스택을 사용하면 편하겠죠????)

- 함수 호출에서 복귀주소 를 기억 할 때

   (예를 들면, main 함수에서 작업을 수행하다가 다른 함수를 호출해서 그 함수로 이동한다고 하면

     그 함수가 끝나고 났을 때 다시 main 함수로 돌아와서 그 다음 작업을 진행 하여야 합니다.

     그럼 그때 복귀주소를 스택에 넣어 놓습니다.)

- main에서 function A를 호출하고 function A에서 function B 를 호출 한다고 가정을 한다면????

    (스택에 우선 main으로 돌아오기 위한 복귀 주소가 먼저  push될 것입니다. 그다음 function A로 가고

      function B가 수행될 때 function A로 돌아오기 위한 복귀 주소가 그 위에 삽입 될 것 입니다.

      function B가 끝나면 스택에서 맨위 (TOP)을 pop해서 function A 나머지를 수행하고 다시 POP 을

      하면 main함수로 돌아올 수 있습니다.)

* 스택의 구현

 - 1. 배열을 이용

 - 2. 연결리스트를 이용

   직접 구현은 하지 않았지만 연결리스트를 사용하면 처음에 스택 사이즈를 지정 해 줄 필요도 없을 것입니다.

     배열을 이용해서 연결리스트 처럼 구현을 하려면 사이즈를 넘어 갈경우 max사이즈를 두배로 증가시켜서

     다시 배열을 만들고 모든 요소들을 새로운 배열로 이동시키고 원래 배열을  delete 시키고 하는 그런 복잡한

     작업을 해야할 것 입니다. 

https://www.acmicpc.net/problem/10989

- 시간제한은 널널, 반면 메모리 제한이 타이트한 문제이다.

- 즉 n의 숫자가 매우 크므로 이걸 배열로 받아서 정렬을 하면 메모리초과가 발생한다는 뜻

- 그래서 다른 조건을 찾아봤다.

- 눈에 들어온 건 # 이 수는 10,000보다 작거나 같은 자연수이다. #

- 즉 배열에다가 입력 숫자들을 넣는것이 아니라

- 입력숫자들을 배열의 index라고 생각을하고 그 입력숫자가 들어올때 마다 arr[입력숫자]의 값을 1증가시켜주는 식으로

- 체크가 가능하다.

- 그리고 마지막 출력을 index순서대로 하면서 그 배열[index]의 값만큼 반복 출력을 하면 된다.