'알고리즘'에 해당되는 글 287건

N이 0일경우 정답은 1이 나와야 하는데, 이 경우를 처리 안해줬었다.

더 깊게 고민하자.

나머지 처리만 잘해주면 크게 어려울게 없었다.

다이나믹 프로그래밍 문제다.

많은 사람들이 풀어서 많은 해법이 나와있었다.

하지만 이해하기 힘든 문제였다.

혼자서는 도저히 생각 할 수 없었고 정답을 보고 이해하는 방법을 택했다.

N개 종류의 동전을 가지고 K원을 만들때,

처음에는 한개종류의 동전을 가지고 0 ~ K원을 만들고

그다음에는 두개종류의 동전을 가지고 0~ K원을 만든다.

그다음에는? 당연히 3개의 동전을 가지고 0 ~ K원을 만든다.

이렇게 만들때에는 당연히 이전에 사용한 값을 이용한다.

만약 1을 이용해 0 ~ K원을 만들었다 치자.

그리고 1 과 2를 이용해서 다시 0~ K원을 만들때를 생각해보자.

1과 2원을 이용해 K가 2원인 경우까지 세었고, 

이제 3원을 만들고 싶다. 현재 1원으로는 만들어봤다.

1원으로 만든경우는 111일테니 이 경우를 더해주자.

2원을 활용해 3을 만들어야하므로 1과 2원을 활용해 1을만든거에 이번에 활용할 2를 추가해주면 3이된다.

그러면 1과 2를 활용하여 3을 만든 것이다.

다시해보자.

1로 0 ~ K 까지 만들었다 생각하자. 

1과 2를 이용해 3까지의 경우의 수를 세었고, 이제 4를 만들고싶다.

1만을 이용한 1111이 있을 것이다.

이 경우를 더해주자. ( + 1)

그리고 1~2를 이용해 2를 만든것에서 (11, 2)에서 2를 추가해주면 4가된다.  ( + 2)

총 세 경우가 저장된다.

다시 다시 다시 해보자.

1과 2원으로 0 ~ K원을 전부 만들었다.

이제 5원을 활용하여 0~ K원을 만들차례이고 K-1원까지 만들었다 생각해보자.

K원을 만들려면 일단 1~2원으로 K원을 만든 경우를 더해주면된다.

그리고 1,2,5로 K-5원까지 만든 경우(경우의 수가 아님)들은 5만 추가하면 K원이 되므로 그 경우의 수도 더해주면 된다.

처음에는 dp를 [100][10001] 을 선언하였었는데, 메모리 초과가 났다.

메모리 제한은 4MB로 4*100*10001에 이것저것 하면 4메가에 넘게된다.

따라서 dp를 dp[2][10001]로 선언하고, 토글변수 next로 이전 값만 저장하도록 구현하였다.

아래는 코드다.

쉬운줄 알았는데, 걸림돌이 많았다.

먼저 seed를 만듣는것에서 실수가 있었다. unsigned long long형을 통해 시드를 만들었는데

1번케이스만 나오고 나오질 않았다. 종만북을 보고, seed구하는 곳을 보았고 감탄쓰!

unsigned int로 선언하여 그냥 곱하고 더하면 자동으로 %2^32가 된다...

그럼 나는 어느곳에서 틀렸을까?

바보같이 2^32가 

unsigned long long MOD = (1ULL << 31);

요거라 생각했다...32번째 비트를 세팅해야겠다는 생각에 사로잡혀있었다.

사실 2^32는 33번째 비트를 세팅해야 값이 나오고 이값을 %하게되면 1~32비트의 값이 되는 것이었다.. 바보였다. 왜몰랐지.. 사실 지금도 약간 헷갈린다. 2^32은 int형으로 표현이 불가능하다는 것을 기억해야겠다.

다음 실수는 list였다. list를 이용하여 푸쉬는 뒤를 해주었고, pop은 앞을해주었다. 사실 pop은 무조건 앞에서만 일어나기 때문에 큐 자료구조가 맞다. 데큐에 꽂혀있던 것 같다. 큐가 생각이 나질 않았다. 실제 list를 쓰니 시간초과가 발생했고, 큐로 고치니 AC를 받았따. 큐는 배열로 구현되어있고 리스트는 동적할당이 들어가 속도 차이가 나는 것 같았다. (아님 말구..)

무튼 적합한 자료구조를 생각하는 연습 및 실수를 줄이는 연습을 계속 해야겠다.

에라토스테네스의 체를 이용하여 풀었다.

비트연산도 연습할겸, 비트연산을 넣어보았다.

비트연산에 익숙해지는 것이 생각보다 어려운 것 같다.

기회되는대로 다양한 구현을 해봐야겠다.

사용한 비트연산 기법으로는 

나누기 대신 >> 연산자를 이용하였고

% 연산 대신 & 7을 사용하였다.

전체 배열의 비트를 1로 세팅하였고,

char 배열에 넣었으므로, 1/8 압축했다.

비트는 1로 채워져있고 0으로 세팅해야하기에

a &= ~(1 << (k & 7)) 을 활용하여 0으로 클리어하였다.

비트가 세트되어있는지 확인은 & 를 활용하였다.

소수를 체킹하면서 소수를 배열이나 벡터에 따로 저장 할 수도 있다.

그렇게 하려면 i를 루트n이 아니라, n까지 돌면 된다. 

하지만 이렇게 할 경우 j = i * i 연산에서 오버플로우가 발생할 가능성이 있다. 

때문에  j = i + i 로 시작하여 오버플로우를 방지하자!

이전과 문자가 같을경우와 같지 않을 경우로 나누었다.

같지 않을경우 기존에 문자가 나왔는지 체크한다.

피보나치 90번째 값이 int형이 넘어갈 줄 몰랐다.

틀렸습니다를 확인 한 후 범위넘어가는지 궁금하여 90을 넣어보니 넘어갔다.

유의하자.. 더 깊게 생각하자..

1. 공집합 꽉 찬 집합 구하기

0 ~ 19 가 집합의 크기일 경우

unsigned int a = (1 << 20) - 1;

2. 원소 추가

15번째 원소 추가

a |= (1 << 15)

3. 원소의 포함 여부 확인

15번째 원소가 켜져있는지 확인(켜져있으면 1이아니라 1<<15의 값이 된다.)

if(a & (1 << 15)) 

4. 원소의 삭제

15번째 원소 삭제

a &= ~(1<<15);

5. 원소의 토글

15번째 원소 토글

a ^= (1 << 15);

6. 두집합의 합집합, 교집합, 차집합, 교집합을 제외한 여집합

a | b, a & b, a & ~b, a ^ b

7. 집합의 크기구하기

int bitCount(int a){

if(a == 0) return 0;

return a % 2 + bitCount(a >>1 );

}

8. 최소 원소 찾기

int a = 1 << 3;

a |= 1 << 5;

int m = a & -a;

printf("%d", m);   -> 8

9. 최소 원소 지우기

int a = (1 << 3);

a &= (a - 1);

10. 모든 부분집합 순회

for(int subset = pizza; subset; subset =((subset - 1) & pizza){

}

-> 공집합은 방문하지 않는다..

11. 2의 n승으로 나눌경우, 쉬프트 연산을 활용하자

a = a/8   -> a = a >> 3;

12. 2의 n승으로 %연산을 할 경우, 앤드 연산을 활용하자

a = a% 8  -> a &= (8 - 1)

JM북 공부중.

1. 연산자 우선순위

비트연산의 우선순위는 ==, != 연산자보다 낮다.

따라서 비트연산에는 괄호를 꼭 해주는 습관을 해줘야한다.

 a & 1 == b  이 연산은 1 == b를 먼저 수행하고 a & 1 을 수행한다.

2. 연산자 오버플로우

64비트 자료형을 사용할 경우 unsigned long long a;

a |= (1 << 60) 을 하게되면 원하는 값과 다른 결과가 나오게 된다.

1은 32비트 정수형이기때문에 60 만큼 쉬프트하게되면 0이된다.

따라서 1ull 로 정수임을 꼭 알리는 코딩을 하자.

3. 부호

부호가 있는 자료형을 선언할 경우 쉬프트로 부호비트를 킬 수 있다. 음수를 오른쪽으로 쉬프트할경우 1이 채워지는 버그가 생길 수 있다. 조심하자!

 by JM북