다이나믹 프로그래밍 검색 결과

해당 글 2건

[백준 1102] 발전소

문제 : https://www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다. 발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다 www.acmicpc.net 비트 마스크를 이용하는 DP 문제. 처음에는 현재 방문 중인 발전소의 노드 번호가 필요한 줄 알고 삽질했다. 코드를 작성하다보니 ..
PS/백준 문제풀이 2019. 8. 6. 18:16

[백준 2098] 외판원 순회

알고리즘을 배우다보면 피할 수 없이 만나는 tsp문제이다. 이 문제의 입력인 N의 크기가 최대 16으로 극히 작은 문제이기 때문에 dp를 이용하여 문제를 풀 수 있다. 하지만 dp 사용에 있어서 tsp(currentCity, visited) 를 나타낼 때 visited를 배열(벡터)를 사용하기가 어려워진다. 메모이제이션을 해야하는데 visited 를 통째로 메모하기도 어렵고 공간 복잡도도 굉장할 것이다. 그래서 N이 작기때문에!!!!! 할 수 있는 방법으로 비트마스크를 사용한다. 0번째 도시를 이미 갔다. == 0번째 비트가 1 0번째 도시를 아직 안갔다. == 0번째 비트가 0 이런식으로 0번째부터 n-1번째 도시까지 총 n개의 도시를 비트로 체크할 수 있다. 여기서 메모이제이션을 위한 배열은 다음과 ..
PS/백준 문제풀이 2019. 8. 6. 17:04