비트연산 검색 결과

해당 글 5건

[백준 1562] 계단 수

문제 : https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 쉬운 계단 수 (https://www.acmicpc.net/problem/10844) 문제의 비트 마스크 버전이라고 보면 된다. 처음 봤을 때 DP인 것을 눈치채고 또한 0부터 9까지 모든 숫자가 한 번씩은 다 나와야 한다고 하기에 비트 마스크를 이용하면 되겠구나 생각했다. 처음에는 메모이제이션을 위해 생각한 배열은 아래와 같았다. int memo[len][situation]; 여기서 len은 현재 문자열의 길이, situation은 0~9까지 등장한 숫자를 비트로 표현한 비트 마스크이다. 그러나 문제가 생겼다..
PS/백준 문제풀이 2019. 8. 6. 21:21

[백준 1102] 발전소

문제 : https://www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다. 발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다 www.acmicpc.net 비트 마스크를 이용하는 DP 문제. 처음에는 현재 방문 중인 발전소의 노드 번호가 필요한 줄 알고 삽질했다. 코드를 작성하다보니 ..
PS/백준 문제풀이 2019. 8. 6. 18:16

[백준 11723] 집합

문제 : https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 비트마스크 연습하기 딱 좋은 문제 :) #include #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int m, bits = 0, op; string order; // op가 1부터 20이므로 그냥 0부터 19비트를 사용한다. cin >> m; while(m--){ cin >> order; if(order ..
PS/백준 문제풀이 2019. 8. 6. 17:16

[백준 2098] 외판원 순회

알고리즘을 배우다보면 피할 수 없이 만나는 tsp문제이다. 이 문제의 입력인 N의 크기가 최대 16으로 극히 작은 문제이기 때문에 dp를 이용하여 문제를 풀 수 있다. 하지만 dp 사용에 있어서 tsp(currentCity, visited) 를 나타낼 때 visited를 배열(벡터)를 사용하기가 어려워진다. 메모이제이션을 해야하는데 visited 를 통째로 메모하기도 어렵고 공간 복잡도도 굉장할 것이다. 그래서 N이 작기때문에!!!!! 할 수 있는 방법으로 비트마스크를 사용한다. 0번째 도시를 이미 갔다. == 0번째 비트가 1 0번째 도시를 아직 안갔다. == 0번째 비트가 0 이런식으로 0번째부터 n-1번째 도시까지 총 n개의 도시를 비트로 체크할 수 있다. 여기서 메모이제이션을 위한 배열은 다음과 ..
PS/백준 문제풀이 2019. 8. 6. 17:04

[비트연산] 비트연산자 & 비트마스크

아주 쉬운 연습문제 : https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제 풀이는 여기! 2019/08/06 - [PS/백준 문제풀이] - [백준 11723] 집합 [백준 11723] 집합 문제 : https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진.. hyeonnii.tistory.co..
PS/Tip 2019. 8. 6. 12:45