19.12.05 (힙, c++ 절대값, mem 시리즈, boj11286, boj1655)

우선순위큐를 해결하기 위한 힙문제를 풀어 보았다. 개념을 잡고 구현하려고 끙끙하다가 구현하니깐 이후부터는 쉽더라.

 

c++ 절대값은 int 형일 떄에

#include <cstdlib>

선언 후에 

 

abs(n) 이렇게 붙여주면 된다. double 형일 경우에는 

 

#include <cmath> 이므로 구분하자.

 

boj11286을 하는데 최소힙 베이스로 두고 절대값들을 비교하고 일반 값들을 비교하는 식으로 풀어보았다.

런타임에러가 나왔다... 아직 해결 못했다.... 해결되는대로 수정해서 올리겠다..

 

이렇게 짜보았다.

 

 

 

boj1655

 

boj1655 를 그 다음에 푸는데 어떤식으로 헤쳐나갈지 몰라서 일단 정말 단순하게 생각해서 heap 배열을 temp배열에 복사를 하고 temp로 pop을 무작정 반복해서 값을 구해서 비교하고 출력하는 식으로 해보았다.

여기서 까먹고 있었던 memcpy를 사용하였다.

 

mem 시리즈 간단히 보자.

 

memset 

 

#include <cstring> 선언

void* memset(void * ptr, int value, int size);

배열 초기화할 때에 많이 쓰인다. 

 

char str[]="hello";

memset(str,'*',strlen(str));

하고 출력하면 ***** 나온다.

만약 hello 아니고 한글이면 한글 1글자당 2byte 여서 

 

char str[]="가나다라마바사";    (7글자임 세지마셈 ㅋㅋ)

memset(str,'*',10);

하면 **********바사 이렇게 나온다. 

 

char 배열이니깐 printf("%s  로 출력 가능하지 string 으로 썼으면 바보같이 printf 쓰진않겠쥐? cout 사용하자 ㅋㅋ

 

int 배열 초기화 할 때에 memset 사용 시에 0,-1 제외한 값으로 초기화하려고 memset 사용하면 혼란 일어날거임

이 2개 값 이외에는 16진수 계산에 의해서 이상한 값 나오니깐 0,-1 말고 다른 값을 초기화 하고 싶을 때에는

c++ 기준 std::fill_n 사용하자. 시작주소값,배열의 자리 수,초기화하려는 값 을 입력하면 된다.

 

memmove는 귀찮아서 패쓰

 

쓰려고 했던 대망의

 

memcpy

 

#include <memcpy>

void* memcpy(void * a, const void * b, size_t num);

 

a는 목적지

b는 복사하려고 하는 것

num은 바이트 수

 

char a[]="가나다라마바사";

char b[20];

char c[20];

 

이렇게 있을 때에

memcpy(b,a,strlen(a)+1);

하면 b 출력했을때에 가나다라마바사 가 나온다. 

+1빼면 널 안들어가서 이상한 값 나온다. 마찬가지로 정수도 널 값이 들어가게끔 입력해야할 것이다. 

 

int도 할 때에 통채로 sizeof(배열이름) 이러면 상관 없겠는데 어줍잖게 정수 넣어서 실수하지말자. 정수 넣을거면 바이트계산 똑바로해서 넣자. int 4byte이다... 4개라고 4, 쓰고 1개만 들어가는 대참사 벌어지지 않도록 하자.

 

어쩃든 이렇게 해서 1655 풀었더니 시간초과가 떴다.(예상한 결과지만 ㅠㅠ ) 게시판 찾아보니 running median을 이용하면 될 것 같다. 일단 이거 공부하고 풀고 해봐야겠다. 풀면 내용추가하겠다.

 

=>

1 2 3 4 5 6 7 이라는 값이 있다고 보자. 중앙값은 4일 것이다. 중앙값과 가까운 값인 3과 5 가 나오게끔 하려면 어떻게 해야할까? 중앙값 기준으로 1,2,3 은 maxheap 5,6,7 은 minheap에 있으면 3,5 가 튀어나올 것이다. 이를 이용한다. 

 

기준을 maxheap 으로 잡든 minheap으로 잡든 상관없다. maxheap top값을 기준으로 잡고 설명해보겠다.

 

문제의 테스트케이스인 1 5 2 10 -99 7 5 를 두고 해보겠다. 

 

하기 전에 간단한 알고리즘 설명을 하자면

 

1. 처음 값 maxheap 에 넣는다. 

2. 들어간 값의 개수가 홀수면 maxheap의 top 값이 중앙값이다. (홀수니깐), 짝수면 maxheap과 minheap top 중 작은 값을 판별하면 될 것이다.

3. minheap의 개수가 maxheap보다 높아져서는 안된다.(maxheap을 기준으로 잡았기 때문에.) 만약 커진다면 그 top값을 maxheap으로 옮긴다.(pop하고 그거를 max에 push).  쉽게말해서 개수는 maxheap이 minheap과 같거나 아니면 딱 1 만큼만 클 수 있다.(minheap기준이면 반대가 되겠다.) 고러 maxheap의 개수가 minheap보다 2이상 크면 maxheap에서 pop 하고 그 값을 minheap에 넣어주면 될 것이다. 왜 딱 1만 커야되냐라고 의문을 가진다면 지금 중앙값을 구하려는 것을 상기하자.

4. maxheap top보다 작으면 maxheap으로 크면 minheap에 집어넣는다. 위에 맨첫줄 3,5 예시 처럼말이다.

 

대충 이 3개만 기억해두자. 아직 무슨말인지 이해 안갈 수 도 있다. 일단 해보자

 

1 

처음 값이므로 maxheap에 넣는다.  개수가 홀수이니 maxheap의 top값인 1 출력

5

maxheap의 top인 1 보다 크므로 minheap에 넣는다. 개수가 짝수이니 1,5 중 작은 값 출력해서 1

2

1보다 크므로 minheap에 넣는다. minheap이 maxheap보다 크므로 pop후 그 값 max에 push (곧, 2를 pop그 값을 max에 push 따라서 maxheap의 top 값은 2가된다.) 2출력

 

이런식으로 반복이다~~ 이해하느라 너무 오래걸렷다 나는.. ㅠ

 

main만 올리겠다. 나머지 pop insert(push) 는 최대힙 최소힙 코드 그대로 가지고 오면된다. 

최소힙 pop push 최대힙 pop push  그리고 각각의 count 변수 따로 해주었다. 

 

사실 이것말구 stl 에 있는 우선순위 큐를 이용하면 그냥 편하게 할 수 있다고 한다.. 하지만 연습이니 직접구현이 좋을듯