4-A 질문 있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

4-A

해결된 질문

작성

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요 선생님 문제를 어떻게 접근해야 되는지 어떤 순서로 로직 작성해야되는지는 떠올랐기 했는데

문제에서 완탐 처럼 nC1, nC2...등등에서 써야 된다 하면
비트 마스킹에서 (1 << n) 요 부분 코드 22번째 줄 if(i & 1 << j) 요걸 사용한다 식으로 외워도 될가요?? 막상 비트마스킹 사용할려고 해도 어떻게 쓸지 떠올리가 않네요 ㅠㅠ

dfs,bfs, 스택 등등 공식처럼 금방 떠올라서 사용할 수 있는데 비트마스킹은 뭐랄까 다른 차원에 개념인거처럼 이걸 언제 쓰고 어떻게 응용할지 감이 안잡히네요

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 창완님 ㅎㅎ

문제에서 완탐 처럼 nC1, nC2...등등에서 써야 된다 하면
비트 마스킹에서 (1 << n) 요 부분 코드 22번째 줄 if(i & 1 << j) 요걸 사용한다

-> nC1, nC2...구할 때 보통 저렇게 코드를 구축합니다.

따라서 저거 통째로 외우시는것도 괜찮습니다만 if (i & (1 << j))는 i의 j번째 비트가 켜져 있는지 확인하는 방식이라는 등의 의미는 다 알고 계셔야 합니다.

비트마스킹은 뭐랄까 다른 차원에 개념인거처럼 이걸 언제 쓰고 어떻게 응용할지 감이 안잡히네요

-> 음... 이렇게 생각하시면 됩니다.

조합을 구한다? 또는 조합을 nC1, nC2... 너무 많이 구해야 함 -> 아 재귀함수로 만들기 귀찮네 -> 비트마스킹은 어떨까...? -> 헉 이거 n이 30이하네? 해볼까?

이렇게 드가시면 됩니다.

감사합니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. 안창완님 질문해 주셔서 감사합니다.

비트마스킹은 특히 nCk 또는 모든 부분 집합을 찾고자 할 때 유용한 기술입니다. 비트 연산을 사용하면 많은 경우의 수를 빠르게 처리할 수 있기 때문에 컴퓨터 과학 문제에서 강력한 도구로 활용됩니다. 비트마스크에서는 각 비트를 사용하여 해당 요소의 포함 여부를 나타내는 점이 특징입니다.

비트마스킹의 기본 이해

비트마스크 생성: (1 << n)은 n번째 비트만 켜진 숫자를 의미합니다.
부분집합 생성: 모든 부분집합을 생성하는 방법은 단순히 0부터 (1 << n) - 1까지 모든 숫자에 대해 비트마스크를 확인하는 것입니다.
부분집합의 포함 확인: 특정 비트가 켜져 있는지 확인하는 방법은 if (i & (1 << j))와 같이 합니다. 여기서 i는 현재 비트마스크이고 j는 확인하고자 하는 비트의 위치입니다.

비트마스킹 활용 상황

경우의 수 탐색: n개의 요소에 대해 전체 부분집합을 탐색하기에 유용합니다.
조합 문제: 조합을 계산하기 위해 비트 연산을 사용하여 부분집합을 생성할 수 있습니다.
중복 없는 집합 관리: 특정 조건을 만족하는 부분집합을 구하거나 확인할 때도 사용됩니다.

비트마스킹을 외울 때 중요한 것은 이러한 일반적인 패턴을 머리에 두고 여러 문제를 해결하면서 체득하는 것입니다. 알고리즘 자체보다는 해당 알고리즘이 어떤 문제에서 잘 동작하는지를 파악하는 것이 중요합니다.

관련하여 이미 좋은 논의가 이루어진 질문이 있어서 참고 URL을 드리겠습니다. 해당 게시물에서는 비트마스킹을 바탕으로 완전 탐색을 쉽게 구현하는 방법에 대해 다루고 있습니다.

비트마스킹 사용에 관한 질문입니다. - 비트마스킹을 어떻게 활용할 수 있는지, 특히 완전탐색을 할 때 유용한 이유를 설명하고 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변