본문 바로가기

algorithm

 (54)
[백준 / BOJ] 16967 배열 복원하기 문제 출처 : https://www.acmicpc.net/problem/16967 16967번: 배열 복원하기 크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐 www.acmicpc.net 크기가 H*W인 배열A를 아래로 X 오른쪽으로 Y만큼 이동한 배열을 배열 A와 겹쳤을때 나온 배열을 배열 B라고 하자. (배열이 겹쳐지면 같은 위치의 수가 합쳐진다.) 배열의 크기 H, W 이동범위 X, Y, 배열 B가 주어질때 배열 A를 구하는 문제다. 풀이 수학? 구현? 문제다. 배열B가 주어졌을때, 원래 배열의 (i,j)의 값은 다음과 같..
[백준 / BOJ] 11049 행렬 곱셈 순서 문제 출처 : https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net N개의 행렬이 주어진다. 행렬 A의 크기를 N*M, 행렬 B의 크기를 M*K라고 할때, 각 행렬을 곱할때 필요한 곱셈 연산 수는 N*M*K이다. 모든 행렬을 곱하는데 필요한 최소 연산횟수를 구하는 문제다. 풀이 다이나믹 프로그래밍으로 풀리는 문제다. 처음엔 그리디로 생각했지만, 현재 최적값이 나중에도 최적이라는 보장이없기때문에 그리디로는 풀기 힘들어보인다. 이 문제처럼 ..
[백준 / BOJ] 1854 K번째 최단경로 찾기 문제 출처 : https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net n개의 도시, m개의 길, k가 주어진다. 김 조교가 1번째 도시에서 출발한다 했을때, 1번부터 n번도시까지 k번째 최단경로를 구하는 문제다. 풀이 다익스트라로 푸는 문제다. k가 100으로 크지않아서, n번째 도시에 k번째 도착하는 모든 경로를 찾아서 구해주면된다. 로직 1. 1번도시에서 다익스트라를 시작한다. 2. 최단경로..
[백준 / BOJ] 5719 거의 최단 경로 (Java) 문제 출처 : https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net N개의 장소와 M개의 도로가 주어진다. (각 도로는 가중치를 갖고있다.) 시작도시 S에서 도착도시 D로 가는 최단경로를 포함하지않는 경로중 가장 빠른 경로를 출력하는 문제다. 풀이 쉬운 문제이해와 그렇지 않은 최적화 과정.. 다익스트라로 푸는 문제였다. 문제가 특이한게, 플래티넘 난이도 임에도 푸는 방법이 굉장히 직관적으로 보인다. 최적화와 경로 추적이..
[백준 / BOJ] 1414 불우이웃돕기 Prim (Java) 문제 출처 : https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net N개의 컴퓨터가 있고, 각 컴퓨터를 연결하는 랜선이 N*N개 주어진다. 다솜이는 자신의 컴퓨터를 최소한의 랜선을 사용해서 연결하고 나머지 랜선을 기부할려고한다. 이때, 다솜이가 기부할수있는 최대 랜선 길이를 구하는 문제다. 풀이 MST문제다. 다솜이가 컴퓨터를 연결하는 과정에서, 연결 순서, 방법등 아무것도 고려하지않고 "최소한의 랜선길이"만 유지하면 되므로 MST로 풀리는 문..
[백준 / BOJ] 1033 칵테일 (Java) 문제 출처 : https://www.acmicpc.net/problem/1033 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 제조하기위한 재료의 갯수 N과 각 재료의 비율이 주어졌을때, 칵테일을 만들기위해 필요한 재료의 질량을 출력하는 문제다. 풀이 유클리드 호제법을 응용해서 푸는 수학 문제였다. 문제에서 두가지 재료의 비율이 주어진다. 이 비율을 갖고 각 재료의 질량을 구하는 공식을 만들어보면, 재료를 각각 a,b 비율을 p,q라 했을때, ..
[백준 / BOJ] 16916 부분 문자열 (Java) 문제 출처 : https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 문자열 S, 문자열 P가 주어진다. 문자열 P가 문자열 S에 속하는지 확인하는 문제다. 풀이 KMP알고리즘을 이용해 푸는 문제다. 문자열의 길이가 최대 100만까지 증가하기때문에, KMP알고리즘을 이용해 풀어야한다. (suffix배열을 만들지 못하는 문자열에서 여전히 시간초과가 나올것이라 생각했는데, 다행히? 그런 테스트케이스는 없는것 같다.) 로직 1. 문자열 P가 S에 포함되는지 확인해야하기 때문에, 문자..
[백준 / BOJ] 1944 복제 로봇 (Java) 문제 출처 : https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 특정한 위치에서 무한히 복제할수있는 로봇이 있다. 로봇은 미로의 출발점 'S'에서 시작해 모든 키'K'를 찾는것이 목표이다. 로봇은 'S'혹은'K'위에서 무한히 복제할수있다. 미로가 주어졌을때, 로봇이 모든 키를 찾기위해 움직여야하는 최솟값을 구하는 문제다. 풀이 MST로 푸는 문제였다. 로봇은 시작지점과 키가있는 위치에서 무한히 복제할수있다. 즉, 키..

티스토리툴바