[BOJ] - 달이 차오른다, 가자. / 1194번 (Java)

[BOJ] - 달이 차오른다, 가자. / 1194번 (Java) [BOJ] - 달이 차오른다, 가자. / 1194번 (Java) 1. 문제 접근 문제의 궁극적인 목표는 '0'(출발지)에서 '가장 가까운 1'(도착지)로 갈 때, 이동 횟수의 최솟값을 구하는 것이다. 단, 몇가지 제약 사항이 존재한다. 벽으로는 절대 이동할 수 없다. 빈칸은 언제나 이동할 수 있다. 총 6개의 열쇠('a', 'b', 'c', 'd', 'e', 'f')가 존재하고, 각 열쇠는 6개의 문( 'A', 'B', 'C', 'D', 'E', 'F' )를 열 수 있다. 즉, 열쇠를 얻고, 문을 여는 것에 대한 탐색을 어떻게 할 것인지가 관건이다. 탐색을 진행하며 만나는 중요한 지점은 2가지다. 4방 탐색을 진행한 결과 문을 만난다. 4방..

• format_list_bulleted 알고리즘
• · 2024. 3. 27.
• textsms

[BOJ] - 녹색 옷 입은 애가 젤다지? / 4485번 (Java)

[BOJ] - 녹색 옷 입은 애가 젤다지? / 4485번 (Java) [BOJ] - 녹색 옷 입은 애가 젤다지? / 4485번 (Java) 1. 문제 접근 [0, 0]에서 출발하여, [N-1, N-1]까지 이동하며 "최소 비용"을 구하면 된다. 해당 문제는 최소비용을 구하는 문제로, 다익스트라 알고리즘을 사용해도 되지만, 2차원 배열에서 다익스트라 알고리즘을 사용하는 걸 선호하지 않아 BFS로 접근했다. 중요한 점은 "이동하기 위해서는(`Queue`에 넣기 위해서는) 비용이 갱신 되어야한다"는 것이다. 다른 BFS들과 달리 방문 배열(`isVisited[]`)를 사용하지 않고, 현재 비용 + 다음 위치 비용이 이전의 비용보다 작을 경우 `Queue`에 삽입한다. // 비용 검증(갱신 할 필요가 있는가) ..

• format_list_bulleted 알고리즘
• · 2024. 3. 27.
• textsms

[BOJ] - 평범한 배낭 / 12865번 (Java)

[BOJ] - 평범한 배낭 / 12865번 (Java) [BOJ] - 평범한 배낭 / 12865번 (Java) 1. 문제 접근 DP를 적용하는 0/1 Knapsack 문제의 대표 문제 유형이다. 물품에는 2개의 요소가 있다 (`부피`, `가치`) 둘 중 부피를 기준으로 2차원 동적 테이블을 생성한다. 동적 테이블의 정의는 다음과 같다. dpTable[item][volume]: 부피 volume을 만족하는 item을 포함하는 최대 가치 0번 물품부터 N-1번 물품까지 탐색하며, 각 물품을 포함하며 얻을 수 있는 최대 가치를 구하면 된다. 2가지 경우가 존재한다. 물품을 넣을 수 없는 경우 물품을 넣을 수 있는 경우 먼저 물품을 넣을 수 없는 경우는 현재 물품의 부피가 고려 중인 부피보다 큰 경우이다. 따라..

• format_list_bulleted 알고리즘
• · 2024. 3. 27.
• textsms

[BOJ] - RGB거리 / 1149번 (Java)

[BOJ] - RGB거리 / 1149번 (Java) [BOJ] - RGB거리 / 1149번 (Java) 1. 문제 접근 N개의 집에 대해 인접한 집이 서로 다른 색으로 칠해지도록 하는 경우의 수 중, 최소 비용을 구하면 된다. 1번 집의 경우는 3가지 색 모두 사용하여 칠할 수 있다. 2번 집의 경우 1번 집의 색이 아닌 2개의 색 중 하나를 골라 칠할 수 있다. 이후 집들도 모두 동일하다. 따라서, 각 집에 대해 특정 색으로 칠했을 때의 비용을 누적해가면서 최적해를 찾으면 되는 DP문제다. 2차원 DP 동적 테이블이 필요하다. 테이블의 크기는 3행(R, G, B) N열이 된다. // 0행: R // 1행: G // 2행: B dp = new int[3][N]; 첫 집의 경우는 모든 색 칠할 수 있으므로..

• format_list_bulleted 알고리즘
• · 2024. 2. 28.
• textsms

[BOJ] - 1로 만들기 / 1463번 (Java)

[BOJ] - 1로 만들기 / 1463번 (Java) [BOJ] - 1로 만들기 / 1463번 (Java) 1. 문제 접근 N이 주어졌을 때, 1로 만들기 위한 연산의 최소 횟수를 구하면 된다. 연산을 1. 3으로 나누기, 2. 2로 나누기, 3. 1빼기 총 3가지가 존재한다. 해당 문제는 DP로 풀 수 있지만, 나의 경우에는 BFS를 통해 풀었다. N을 시작점으로, 도달할 수 있는 번호를 `Queue`에 넣으면서 진행했다. 나누기 연산의 경우, 나누어 떨어질 경우만 고려했고, 공통적으로 기존의 거리(`dist`)와 비교하여 짧은 경우에 한하여 `Queue`에 삽입했다. int currNum = q.poll(); if (currNum == GOAL) break; if (currNum % 3 == 0 &&..

• format_list_bulleted 알고리즘
• · 2024. 2. 28.
• textsms

[BOJ] - 최단경로 / 1753번 (Java)

[BOJ] - 최단경로 / 1753번 (Java) [BOJ] - 최단경로 / 1753번 (Java) 1. 문제 접근 시작 정점에서 모든 정점까지의 최단거리를 구하면 되는 문제다. 간선의 가중치를 의미하는 w값이 10이하의 "자연수"이므로, 음의 가중치를 갖지 않는다. 따라서, 다익스트라(Dijkstra)알고리즘을 사용하여 구현하면 된다. 현재 위치한 노드에서 방문할 수 있는 노드를 선별하는 것이 핵심이다. Node adNode = adList[currNodeNum]; while (adNode != null) { // 방문한 노드는 PASS, 도달하는 비용이 업데이트 되지 않으면 PASS if (!isVisited[adNode.nodeNum] && currCost + adNode.weight < dist[..

• format_list_bulleted 알고리즘
• · 2024. 2. 28.
• textsms