인프런 커뮤니티 질문&답변
작성한 질문수
tsp함수에서 (visited | (1 << i))
해결된 질문
작성
·
65
·
수정됨
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요. 강의잘 듣고 있습니다. 다름이 아니라 코드 중에 잘 이해가 가지 않는 부분이 있어서 질문드립니다.
ret = min(ret, tsmp(i, visited | (1 << i)) + dist[here][i]);에서 visited | (1 << i)는 i를 기준으로 탐색하지 않는 곳을 확인 하기 위해서 필요한 코드인가요?
ex) tsp(0, 1)이고 i = 1일때, ret = min(최대, tsp(1, 1 | (1 << 1), + dist[0][1])이 됩니다
여기서 tsp(1, 1 | (1 << 1)은 0, 1번째를 탐색했고 다시 1번째를 기준으로 2, 3을 탐색하는 것일까요?0, 1을 탐색하는 이유는 1 | (1 << 1) -> 0001 | 0010 -> 0011이고 이는 0번째와 1번째를 확인했음을 의미하는 거 맞을까요?
그리고 2번을 기준으로 나머지 탐색을 하지 않은 도시(3, 4)를 탐색하는 것이구요.
위의 내용이 맞다면, 해당 코드에 대한 이해는 했는데 솔직히 말하면 제가 visited | (1 << i)라는 코드를 떠올리지는 못할 것 같습니다... 어떻게 하면 떠올릴 수 있을까요? 아직은 문제풀이를 많이 하지 않았으니까 그냥 외우면 되는 걸까요? ㅠㅠ
답변 2
0
안녕하세요 라영님 ㅎㅎ
대략적으로 잘 이해하셨습니다ㅎㅎ
i를 기준으로 탐색하지 않는 곳을 확인 하기 위해서 필요한 코드인가요?
-> 저 코드 하나만으로는 탐색하지 않는 곳이 아니라 그저 방문기록을 위한 코드라고 보시면 되는데
if(visited & (1 << i)) continue;제 코드를 보시면 이 코드가 위에 있기 때문에 결과적으로 탐색하지 않은 곳을 탐색한다라는 의미가 됩니다.
자세히 설명을 드리면요.
visited | (1 << i)는 도시 방문 여부를 기록하는 데 사용됩니다. visited는 각 비트가 특정 도시의 방문 여부를 나타내는 비트 마스크입니다. 즉, 숫자의 각 비트가 특정 도시에 대응되며, 비트가 1이면 그 도시는 방문한 것이고, 0이면 방문하지 않은 것입니다.
1 << i는 숫자 1을 i번째 비트로 왼쪽으로 이동시킵니다. 예를 들어, i = 1이면 1 << 1은 0010이 됩니다. 이 값은 i번째 도시에 해당하는 비트를 1로 설정하는 것을 의미합니다.
visited = 0001 (도시 0만 방문함)이고 i = 1일 때:
visited | (1 << 1) 0001 | 0010 = 0011
이제 도시 0과 1이 방문된 상태가 됩니다.
0, 1을 탐색하는 이유는 1 | (1 << 1) -> 0001 | 0010 -> 0011이고 이는 0번째와 1번째를 확인했음을 의미하는 거 맞을까요?
-> 네 맞습니다.
그리고 2번을 기준으로 나머지 탐색을 하지 않은 도시(3, 4)를 탐색하는 것이구요.
-> 네 맞습니다.
visited | (1 << i)라는 코드를 떠올리지는 못할 것 같습니다... 어떻게 하면 떠올릴 수 있을까요? 아직은 문제풀이를 많이 하지 않았으니까 그냥 외우면 되는 걸까요? ㅠㅠ
-> 네 일단은 외워주세요. ㅎㅎ 외우다는 것도 저는 하나의 공부방법이라고 생각합니다. 저또한 이해가 안되고 그럴 때 코드 자체를 외웠구요 ㅎㅎ 그렇게 익숙해지는 순간이 오고 -> 잘 떠올리실 거에요 ㅎㅎ
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다. 김라영님께서 질문하신 Traveling Salesman Problem(TSP) 알고리즘에서의 visited | (1 << i) 부분에 대한 이해를 돕기 위해 설명을 준비했습니다.
visited | (1 << i)의 의미: 이 표현식은 특정 정점i를 방문했음을 표시하기 위해 비트마스크를 사용한 것입니다.visited는 현재까지 방문한 정점들의 집합을 비트로 표시한 변수입니다.1 << i는i번째 비트를 1로 설정하게 합니다. 따라서visited | (1 << i)는 현재 방문한 정점들에i를 추가로 방문했음을 나타내는 새로운 비트마스크를 생성하는 것입니다. 예를 들어,visited가0001이고i가 1이라면1 << 1은0010이 되며, 이를 OR 연산하면visited는0011이 되어, 0번과 1번 정점을 방문했음을 나타냅니다.탐색 로직: TSP에서의 목표는 모든 정점을 한번씩 방문하고 시작점으로 돌아오는 최소 경로를 찾는 것입니다.
visited | (1 << i)는 특정 정점을 ‘방문한’ 상태를 기록하는 기능을 하며, 방문하지 않은 정점들을 탐색하기 위한 정보를 제공합니다.접근 방법 익히기: 이러한 비트마스크를 활용한 방법은 처음에는 객체나 배열같이 직관적이지 않을 수 있지만, 익숙해지면 매우 효율적이고 강력한 기법입니다. 문제 풀이 과정을 통해 비슷한 패턴을 반복적으로 접하다 보면 자연스럽게 이해하게 될 것입니다. 또한, 비트마스크에 익숙해지기 위해 직접 작은 문제를 만들어 연습하거나 다양한 문제 해결을 시도해 보는 것도 추천드립니다.
직접적인 유사 질문 사례:
관련 질문들을 통해 해당 비트마스크 사용법에 대한 추가적인 설명과 예제를 확인하실 수 있습니다:
- 7-A 한줄로 디버깅 하고 싶은데 혹시 이 부분 나눌 수 있을까요?
- dp테이블과 tsp의 의미
김라영님께서 이 질문과 연관된 다른 예제나 설명을 통해 더 많은 인사이트를 얻으셨으면 좋겠습니다. 문제를 자주 접하고, 비트 연산 패턴을 직접 구현해보면서 익숙해지는 것을 추천드립니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.