# 비트마스킹
[백준] 1052번 물병
물병의 개수를 2진법으로 나타냈을때, 만약 1의 개수가 K보다 작다면 while문을 멈추고 상점에서 사야 하는 물병의 개수의 최솟값을 출력해주면 된다.💡소요시간 : 10m
[백준 #1062]: 가르침(python)
\[백준해당 문제는 브루트 포스 방식으로 해결할 수 있다. 하지만 시간 초과를 해결하기위해 비트마스킹 기법을 사용해야한다. combinations을 사용하여 a,c,i,t,n을 제외한 문자들로 이루어진 모든 경우의 수를 만들고 비트마스킹 기법을 이용하여 포함관계에 있는
[백준] 2961번 도영이가 만든 맛있는 음식
누적 합, 누적 곱 개념을 이용해서 접근했는데 이 방법은 모든 재료를 다 사용하는 경우라면 해결이 되는데 일부 재료를 사용하는 경우라면 되게 까다로워져서 결국 포기했다.combinations을 이용해 나올 수 있는 모든 조합을 확인해 신맛에서 쓴맛을 뺀 절댓값을 구해
[BOJ] 16938 캠프 준비
16938 캠프 준비 문제 링크문제 풀이 코드 링크문제 풀이 방법이 2개... 비스마스킹 여부에 따라 풀이를 2개로 나누어 풀었다.첫 줄에 N, L, R, X를 받고, 두번째 줄에 N개의 문제(난이도)가 주어진다.N개의 문제들 중 문제를 선택하는데, 선택된 문제들의 합
[BaekJoon] 2234 성곽 (Java)
https://www.acmicpc.net/problem/2234위 그림과 같이 생긴 성곽이 있는데, 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타냅니다.성은 M x N개의 정사각형 칸으로 이루어접니다.성에는 최소 두 개의 방이
2961도영이가 만든 맛있는 음식
https://www.acmicpc.net/problem/2961첫번시도에서 통과 했는데 코드 정리하다보니 최적화를 더 할 수 있을거 같아서 두번째 시도에서 시간을 많이 단축하였다. 완전탐색에서 중복재료선택을 줄였다.재료가 3개면, 완전탐색을 통해 3개중 1개
[BOJ] 2098 외판원 순회
2098\. 외판원 순회 문제 링크문제 풀이 코드 링크하...도저히 설명없이는 풀 수 없었던 문제... 구글링을 열심히 했다. 시간 제한이 되게 빡빡해서, 생각조차 못한 부분을 수정해야했다.일반적인 외판원 순회(Traveling Salesman problem) 문제이다
[오늘의 알고리즘] 1/6 백준 14225, 1062
각 수의 인덱스를 비트로 표현해서 부분집합과 합을 구해서 없는 최솟값 구하기N자리 꽉 찬 집합의 부분집합을 구한다.각 부분집합의 원소를 인덱스로 가지는 값의 합(부분집합의 합)을 구해서 sums 배열에 마킹한다.1부터 부분집합의 합의 최댓값까지 순차 탐색하면서 sums
[BOJ] 7682 틱택토
2580 스도쿠에 이어서, 백트래킹 문제.같은 배열에 대해 공유해가며 값을 수정할 수 있다는 것에 대해 익숙해지기 위해 골랐다.문제 링크풀이 링크여러개의 테스트 케이스로 입력을 받는다.3x3짜리 틱택토 게임 보드가 한 줄로 들어온다. 각 칸은 O, X, .로 존재하는데
백준 2961 : 도영이가 만든 맛있는 음식
https://www.acmicpc.net/problem/2961단순히 재료를 넣는지 마는지에 따라 결과의 최솟값을 구하는 문제반복적이므로 재귀를 통해 해결했다\-> 하지만 이 문제는 밑의 비트마스킹 방법을 사용하는것이 더 효율적인 것 같다https:
[BaekJoon] 1062 가르침 (Java)
https://www.acmicpc.net/problem/17142바이러스는 활성 상태와 비활성 상태가 있고, 가장 처음에 모든 바이러스는 비활성 상태이며, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 이는 1초가 걸립니다.승원이