본문 바로가기

PS

 (53)
[백준 / 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] 4195 친구네트워크 (Java) 문제 출처 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 민혁이는 소셜 네트워크에서 친구 만드는걸 좋아한다. 어떤 사이트의 친구관계가 주어졌을때, 해당 친구관계에 포함되어있는 친구의 수를 출력하는 프로그램을 만드는 문제다. 풀이 친구관계가 최대 10만까지 갈수있으므로, 매 쿼리마다 모든 노드를 탐색하면, O(N^2)의 시간복잡도가나와 TLE를 받게된다. 문제를 풀기위해 유니온파인드를 사용해야했다. 문제의 노드정보가 문자열로 주어..

티스토리툴바