방금 배운 비트마스킹 을 활용하여 백준 문제를 풀어보자! 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 문제 설명 예제 1번은 식재료 1, 3, 5를 골랐을 때이고, 2번은 식재로 2, 3, 4를 골랐을 때이다. 둘 다 최소 영양성분 100, 70, 90, 10 이상을 만족하지만 총 가격은 1번이 270, 2번이 180으로 2번을 골랐을 때가 가격이 더 저렴하므로 더 나은 선택이 된다. 구현 아이디어 각 재료의 선택 여부를 0과 1로 나타내면 6자리 이진수로 모든 경우의 수를 나타낼 수 있다. ex) 111..

비트마스킹을 알고리즘 문제를 풀 때 어떻게 활용하는지 알아보기 전에 비트연산자를 먼저 알아보자. 비트연산자 연산자 기능 & AND 연산 | OR 연산 ^ XOR 연산 ~ 모든 비트를 반전 비트 열을 오른쪽으로 이동 & 연산자 true & true = true이고, 나머지는 모두 false를 반환한다 연산 결과 0 & 0 0 1 & 0 0 0 & 1 0 1 & 1 1 ex) 1001 & 1000 = 1000 | 연산자 하나라도 true라면, true를 반환한다. 연산 결과 0 & 0 0 1 & 0 1 0 & 1 1 1 & 1 1 ex) 1001 & 1000 = 1001 ^ 연산자 두 비트가 서로 다를 경우(true ^ true, false ^ false)에 true를 반환한다. 연산 결과 0 & 0 1 1..

4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 문제 설명 예제 아래 사진은 시간별 지훈이(왹깅)와 불(🔥)의 위치를 나타낸 그림이다. 이 때 주의할 것은 지훈이와 불이 '동시에' 움직인다는 것이다. 지훈이가 움직인 다음 불이 붙거나, 불이 붙은 다음 지훈이가 움직이는 것이 아니다. t=2일 때 미로의 가장자리에 도착하였고, 한 칸을 더 움직여 t=3일 때 지훈이는 미로를 탈출할 수 있다. 구현 아이디어 처음에는 지훈이가 움직일 수 있는 경로가 여러 개라고 생각해서 DFS로 완전탐색을 해야 한..

문제 설명 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제에서 중요한 부분들을 하이라이트로 표시해보았다. 이제 예제를 통해 문제를 좀 더 확실히 이해해보자. M=3인데 치킨집(2)의 개수가 3개이므로 폐업을 시킬 필요가 없다. (1,3) ~ (2,3) 사이 치킨 거리 = 1 (3,2) ~ (3,3) 사이 치킨 거리 = 1 (3,3) ~ (4,3) 사이 치킨 거리 = 1 (2,3) ~ (2,5) 사이 치킨 거리 = 2 이므로, 도시 전체의 치킨 거리는 5이다. 구현 아이디어 치킨집 중 ..

완전탐색이란? 완전탐색은 모든 경우의 수를 탐색하는 알고리즘이다. 무식하게 한다는 의미로 브루트포스(Brute Force) 알고리즘이라고도 부른다. 직관적이기 때문에 이해하기 쉬우며 문제의 정확한 결과를 얻어낼 수 있는 가장 확실하며 기초적인 방법이다. 모든 경우의 수를 탐색하는 것은 저번 포스트의 순열이나 조합을 사용하거나, 단순 구현을 하면 된다. 하지만 시간 초과가 날 수 있으므로, 보통은 최대 범위가 1억 미만일 때까지만 한다. 완전탐색으로 문제 푸는 방법 완전탐색을 활용할 때 가장 간단한 방법은 반복문(for, while)을 활용하는 것이다. 만약 반복문만 사용하는 것이 너무 복잡하거나 특정 행위를 반복하며 매개변수만 변경하면 될 것 같은 경우에는 재귀함수를 사용할 수 있다. ex. 조합/순열 ..

누적합이란? 요소들의 누적된 합. 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어 활용하는 것을 의미한다. 앞에서부터 더하는 prefix sum, 뒤에서부터 더하는 suffix sum이 있는데, 코딩테스트에는 prefix sum이 자주 나온다. 누적합을 만들 때, 0번째 index는 비워두고 1번째 index부터 사용하는 것이 편하다 인덱스 0 1 2 3 4 원소 0 1 10 11 100 누적합 0 1 11 22 122 누적합을 C++로 간단하게 구현할 수 있다. #include using namespace std; int a[100004], b, c, psum[100004], n, m; int main() { cin >> n >> m; for (int i = 1; i..