BOJ 2667 단지번호붙이기
2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 이 문제는 한칸의 위, 아래, 좌 , 우 에 1 표시가 되어있다면 (집이 있다면) 집이 연결되었다고 표현하고, 이렇게 연결된 집들을 '단지'라고 일컫는다. 따라서 과 같이 생긴 그래프가 있을때 와 같이 단지가 형성 되는 것이다. ..
단순히 DFS와 BFS를 구현하는 문제이다. 근데 이 문제의 핵심은 " 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고," 이다. 이를 간단히 하기 위해서는 인접행렬로 그래프를 구현하면 된다 . 인접행렬로 그래프를 구현하고, 간선을 탐색할 경우 당연히 인덱스 차례대로 방문하기 때문에 "정점번호가 작은 것을 먼저 방문하고"가 자연스럽게 충족된다. 반면에 인접리스트로 구현할 경우, 간선 노드들이 정렬이 되어있지 않으므로 정렬을 해주어야 한다. 나는 인접 리스트 버전과 인접 행렬버전 모두를 구현했다. 먼저 인접행렬버전을 보자. 인접행렬은 당연히 (n+1)*(n+1) 의 크기로 구현을 해주고, BFS를 위해 큐도 구현해주어야 한다. 또한 visited 배열 (방문을 표시하는 배열..
BOJ 12865 평범한 배낭
이 문제는 완전 전형적인 Knapsack 문제이다! 배낭의 무게가 w로 한정적일때, 가치가 모두 다른 보석들을 얼마만큼 넣어야 최적해인지 찾아야한다. 그렇다면 아래 그림을 통해 knapsack 문제를 더 살펴보자! 1) 현재 보석의 무게 > 배낭의 무게 이 경우는 해당 보석을 넣을 수 없으므로, 이전에 구해놓은 최적해 (이전 보석-현 배낭무게의 최적해)를 똑같이 복사한다. 2) 현재 보석의 무게 w) max(vali+p[i-1][w-wi] , p[i-1][w] else i는 현재 보석, w는 현재 배낭의 무게 wi는 현재 보석의 무게, vali 는 현재 보석의 가치이다. 구현에서 더 추가되는 부분은, p 라는 2차원 배열이다. 2차원 배열을 선언하는 이유는 "해당 무게의 최적해" 들을 보석의 개수 별로 ..
다이나믹 프로그래밍 입문과도 같은 문제이다 아마 dp처음 풀면 그리디로 풀려고 할텐데 그러면 무조건 오답이다! 왜냐하면 그리디로는 모든 조건들이 최소인 경우를 계산할 수 없기 때문이다. 일단, 문제에서 주어지는 RGB 거리 정보를 저장할 배열 dp와, 문제를 풀 배열 solve를 생성했다. 그리고 해당 문제의 점화식은 solve[i][j] = dp[i][j] + get_min(solve[i-1][j-1],solve[i-1][j-2]) 이다. 점화식은 잘 보면 이해가 쉽게 갈 것이다. dp[i][j]는 solve[i][j] 자리의 기본 값이고, get_min ~ 을 통해서 같은 색깔 sovle[i-1][j] 를 빼고 두 색깔중에 가장 작은 값을 solve에 더해주는 것이다. 이런식으로 이전의 solve도 ..