[프로그래머스] 12942 최적의 행렬 곱셈 - JAVA
·
알고리즘/문제풀이
[프로그래머스] 12942 최적의 행렬 곱셈 - JAVA문제https://school.programmers.co.kr/learn/courses/30/lessons/12942문제 분석조건여러 개의 행렬을 순서대로 곱할 때, 곱셈 순서(괄호를 치는 순서)에 따라 총 곱셈 연산 횟수가 달라진다. 주어진 행렬들의 곱셈에 필요한 최소 연산 횟수를 구하는 문제풀이방법DP를 이용하여 문제를 풀었다.`dp[i][j]`는 i번째 행렬부터 j번째 행렬까지 곱하는 데 필요한 최소 곱셈 연산 횟수를 의미한다. 행렬이 1개(`i == j`)일 경우 곱셈이 필요 없으므로 0으로 초기화 한다.`i`부터 `j`까지의 행렬 곱은, 중간의 한 지점 `k`를 기준으로 (`i ~ k`)까지의 곱과 (`k+1 ~ j`)까지의 곱, 이 두 결..
[프로그래머스] 62050 지형 이동 - JAVA
·
알고리즘/문제풀이
[프로그래머스] 62050 지형 이동 - JAVA문제https://school.programmers.co.kr/learn/courses/30/lessons/62050 문제 분석조건`N x N` 크기의 땅의 각 칸에는 높이 정보가 있다. 상하좌우로 인접한 칸으로 이동할 때, 두 칸의 높이 차이가 `height` 이하라면 비용이 들지 않는다. 하지만 높이 차이가 `height`를 초과하면, 그 차이만큼의 비용을 내고 사다리를 놓아야만 이동할 수 있다.이때, 모든 땅을 서로 오고 갈 수 있도록 연결하는 데 필요한 사다리 비용의 최솟값총합을 구하는 문제풀이방법그래프의 모든 정점을 최소 비용으로 연결하는 최소 신장 트리(MST)를 이용해 문제를 해결하였다.`Ladder` 클래스: 다음으로 이동할 칸의 정보(`po..
[백준/BOJ] 2473 세 용액 - JAVA
·
알고리즘/문제풀이
[백준/BOJ] 2473 세 용액 - JAVA문제https://www.acmicpc.net/problem/2473문제 분석조건-1,000,000,000 이상, 1,000,000,000 이하의 특성값을 갖는 N개의 용액이 있다. 이 중 3개의 다른 용액을 선택하여 각 용액의 특성값을 더했을 때 0과 가장 가까운 3개 용액을 구하는 문제이다.풀이방법우선 입력 받은 N개의 용액을 정렬한 뒤, 가장 낮은 특성값을 가진 용액을 고정시킨 뒤 탐색을 하는 방식으로 구현하였다.코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Stri..
[백준/BOJ] 21610 마법사 상어와 비바라기 - JAVA
·
알고리즘/문제풀이
[백준/BOJ] 21610 마법사 상어와 비바라기 - JAVA문제https://www.acmicpc.net/problem/21610 문제 분석조건N × N 격자에서 비구름을 M번 이동시킨다. 한 번의 이동 명령은 다음 단계로 이루어진다.모든 구름이 특정 방향으로 특정 칸만큼 이동한다. 격자는 경계가 연결되어 있다.구름이 있는 칸에 비가 내려 물의 양이 1 증가한다.물복사 마법이 시전된다. 비가 내렸던 칸은 대각선 방향에 물이 있는 칸의 수만큼 물의 양이 추가로 증가한다.이전에 구름이 있던 칸을 제외하고, 물의 양이 2 이상인 모든 칸에 새로운 구름이 생기고, 해당 칸의 물은 2만큼 줄어든다.M번의 이동이 모두 끝난 후, 격자에 남아있는 물의 총 양을 구하는 문제이다.풀이방법단계별로 단순 순차적으로 구현하..
[프로그래머스] 84021 퍼즐 조각 채우기 - JAVA
·
알고리즘/문제풀이
[프로그래머스] 84021 퍼즐 조각 채우기 - JAVA문제https://school.programmers.co.kr/learn/courses/30/lessons/84021 문제 분석조건`game_board`에 있는 빈 공간(0)에 `table`에 있는 퍼즐 조각(1)을 아래 조건들에 맞춰 채워 넣는 문제이다. 목표는 최대한 많은 칸을 채우는 것이다.1. 퍼즐은 빈 공간에 딱 맞는 곳에만 넣을 수 있다.(1개의 퍼즐을 넣은 뒤 인접한 곳에 빈 칸이 있으면 안된다.)2. 퍼즐은 회전은 가능하나 뒤집을 수는 없다.3. 한번 넣은 퍼즐은 다시 사용할 수 없다.풀이방법빈 공간의 모양과 해당 빈 공간이 채워졌는지를 정보로 가진 `EmptyArea` 클래스를 정의하여 이용했다. `Block` 클래스는 도형의 크기와..
[백준/BOJ] 1202 보석 도둑- JAVA
·
알고리즘/문제풀이
[백준/BOJ] 1202 보석 도둑- JAVA문제https://www.acmicpc.net/problem/1202 문제 분석조건N개의 보석이 각각의 무게와 가격을 가지고 있고, K개의 가방이 각각의 최대 허용 무게를 가지고 있다. 각 가방에는 최대 한 개의 보석만 넣을 수 있을 때, 훔칠 수 있는 보석의 최대 가격을 구하는 문제이다.풀이방법가장 작은 가방부터 넣을 수 있는 보석 중 가장 가치가 큰 보석을 넣는 그리디 방식으로 해결했다.가장 먼저 보석은 무게가 가벼운 순으로, 가방은 담을 수 있는 용량이 작은 순으로 정렬한다.그다음, 용량이 가장 작은 가방부터 순서대로 확인하며 현재 가방에 담을 수 있는 무게의 보석들을 모두 찾아낸다.이렇게 찾아낸 보석들은 정답이 될 수 있는 후보군이므로, 이 보석들의 가..