본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )

 (260)
[백준 / 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로 푸는 문제였다. 로봇은 시작지점과 키가있는 위치에서 무한히 복제할수있다. 즉, 키..
[백준 / BOJ] 1030 프렉탈 평면 (Java) 문제 출처 : https://www.acmicpc.net/problem/1030 1030번: 프렉탈 평면 첫째 줄에 7개의 정수 s, N, K, R1, R2, C1, C2가 주어진다. www.acmicpc.net 7개의 정수 s, N, K, R1, R2, C1, C2 가 주어진다. 1*1그리드는 매 초마다 N*N그리드로 나뉘어지며 이때, 나뉜 정사각형이 흰색이라면, 가운데 K*K칸이 검은색으로 변한다. s초가 지났을때, R1,C1에서 R2,C2그리드를 출력하는 문제다. 풀이 수학?과 분할정복으로 푸는 문제였다. 문제를 풀기위해 우선, N*N 그리드가 매초마다 K*K조각으로 나누어질때, s초가 지난후 위치하는 좌표를 구해야한다. 예를들어, 1*1그리드가 매 초마다 3*3의 조각으로 나뉠때, 2초가 지난후 ..
[백준 / BOJ] 1099 알 수 없는 문장 (Java) 문제 출처 : https://www.acmicpc.net/problem/1099 1099번: 알 수 없는 문장 첫째 줄에 문장이 주어진다. 문장의 길이는 최대 50이다. 둘째 줄에 단어의 개수 N이 주어지며, N은 50보다 작거나 같은 자연수이다. 셋째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최 www.acmicpc.net 몇개의 단어로 이루어진, 길이가 최대 50인 문장이 있다. 이 문장은 특이하게, 문장을 이루는 단어의 알파벳이 섞여있어도 된다. 예를들어, neotowheret 는 one two three there 중 3개의 단어를 사용해서 만들수있다. neo - > one tow -> two heret -> three heret -> there 단어를 해석할때, 각 단어의 바뀐 알..
[백준/BOJ] 9625 BABBA (Java) 문제 출처 : https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 버튼이 하나만 있는 기계가 있다. 버튼을 누르면 화면에있는 A가 B로 바뀌고 B는 AB로 바뀐다. 버튼을 K번 눌렀을때, 화면에 표시되어있는 A와 B의 갯수를 출력하는 문제다. 풀이 다이나믹 프로그래밍 문제다. 버튼을 K번 눌렀을때 A와 B의 갯수를 생각해보자. 1. A는 K-1번째 버튼을 눌렀을때, B의 갯수만큼 생성된다. 2. B는 K-1번째 버튼을 눌렀을때, A와 B의 갯수만큼 생..
[백준 / BOJ] 4195 친구네트워크 (Java) 문제 출처 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 민혁이는 소셜 네트워크에서 친구 만드는걸 좋아한다. 어떤 사이트의 친구관계가 주어졌을때, 해당 친구관계에 포함되어있는 친구의 수를 출력하는 프로그램을 만드는 문제다. 풀이 친구관계가 최대 10만까지 갈수있으므로, 매 쿼리마다 모든 노드를 탐색하면, O(N^2)의 시간복잡도가나와 TLE를 받게된다. 문제를 풀기위해 유니온파인드를 사용해야했다. 문제의 노드정보가 문자열로 주어..

티스토리툴바