비트마스킹

문제 링크 문제 설명 현대모비스에서 전기차로 경사로 주행 테스트를 하려고 합니다. 경사로 테스트는 n×m 크기의 격자 형태의 공간에서 진행되며, 각 칸에 적힌 숫자는 높이를 나타냅니다. 전기차는 격자 내의 모든 칸에서 출발 가능하며, 상하좌우로 인접한 칸으로만 이동 가능하고 격자 밖을 벗어날 수는 없습니다. 전기차가 인접한 칸으로 이동하는 길의 경사는 이동하려는 칸의 높이에서 현재 칸의 높이를 뺀 값입니다. 예를 들어 높이가 5인 칸에서 7인 칸으로 이동하는 길의 경사는 2(= 7 - 5)이고, 높이가 6인 칸에서 높이가 1인 칸으로 이동하는 길의 경사는 -5(= 1 - 6)입니다. 경사 수열 d가 주어집니다. 경사 수열은 테스트에서 전기차가 이동할 길의 경사를 나타내며, d[i]는 전기차가 i+1번째로..

문제 링크 분류 비트마스킹, 다이나믹 프로그래밍, 비트필드를 이용한 다이나믹 프로그래밍, 외판원 순회 문제 제출 일자 2024년 1월 6일 14:18:11 문제 설명 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수..