반례 궁금합니다.

작성한 질문수 14

1

안녕하세요 ㅎㅎ

p.s. 비트마스킹 챕터에 있는 문제라 비트마스킹을 써봤는데, 굳이 이런 문제에 비트마스킹을 쓸 필요가 없었을까요? 앞으로 코테를 풀 때 메모리가 부족할 만큼 수의 범위가 크면 비트마스킹만 쓰면 될까요? 이 문제도 노드가 최대 1000개에 엣지가 1000000개 까지 가능하니 비트마스킹을 써야겠다고 생각습니다.

>> 흠... 조금 잘못 이해하신 거 같은데요.

문제의 지문을 보시면

The first line will contain an integer N with the number of nodes in the graph. The number of nodes will be between 1 and 1,000. The identifier of each node will be an integer from 1 to N. 

이라고 되어있습니다. 즉, 정점이 1000개까지 가능한 것이죠.

자 그러면

    for (int i = 1; i <= node; ++i)
    {        if ((v[idx] & (1 << i)))

이 코드에서 1 << i가 가질 수 있는 최대값은 무엇일까요?

1 << 1000이 됩니다.

즉,

2^1000 이라는 값이 되며 이 값은 너무나도 큰 수가 됩니다.

이 때문에 틀린 것이죠.

비트마스킹은 이러한 정수조건이 있기 떄문에 쓸 때는 n이 30 ~ 31이하일 때 쓰는 것을 기억해주세요 ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

안녕하세요 Maruche 님, 인프런 AI 인턴이에요.
주어진 링크는 백준 온라인 저지의 문제로 이해하겠습니다.

해당 문제의 반례는 직접 문제 페이지를 확인해야 더 정확히 파악할 수 있을 것 같습니다. 주어진 링크를 통해 문제 페이지로 이동하여 반례나 다른 유용한 정보를 확인하시는 것을 권장드립니다. 문제의 특징과 제한조건에 따라 어떤 방법을 사용해야 하는지 결정할 수 있을 것입니다.

비트마스킹은 메모리를 절약할 수 있는 방법 중 하나이지만, 모든 문제에 비트마스킹을 적용하기는 어렵습니다. 문제의 특성과 어떤 연산을 수행해야 하는지에 따라 적절한 방법을 선택하는 것이 중요합니다. 각 문제마다 어떤 방법이 더 효율적인지 고려하고, 필요한 경우 비트마스킹을 사용하시면 됩니다.

문제 해결에 대한 도움이 필요하시면, 질문 게시판이나 관련 커뮤니티에서 도움을 받을 수 있을 것입니다. 잘 모르는 부분이 있으면 추가적인 질문을 주저하지 마세요. 좋은 결과 있기를 바랍니다. 감사합니다!