본문 바로가기

algorithm

 (54)
[백준 / 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를 받게된다. 문제를 풀기위해 유니온파인드를 사용해야했다. 문제의 노드정보가 문자열로 주어..
[백준 / BOJ] 1949 우수 마을 (Java) 문제 출처 : https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net N개의 마을로 이루어진 나라가 있다. 나라는 1부터 N까지의 번호로 표시되며, 트리구조 , 양방향 간선 으로 이루어져있다. 각 마을에는 C명의 주민이 살고있다. (C
[백준 / BOJ] 16918 봄버맨 (Java) 문제 출처 : https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net R*C그리드가 있다. 0 초 - 봄버맨은 초기에 폭탄을 하나 설치한다. 1 초 - 봄버맨은 초반 1초에는 아무것도 하지않는다. 2 초 - 봄버맨이 폭탄이 없는곳에 폭탄을 설치하고 3초전에 설치한 폭탄을 터트린다. 3 초 - 봄버맨이 폭탄이 없는곳에 폭탄을 설치하고 3초전에 설치한 폭탄을 터트린다. 4 초 - 봄버맨이 폭탄이 없는곳에 폭탄을 설치하고 3초전에 설치한 폭탄을 터트린다. . . . 위 과정..
[백준 / BOJ] 7579 앱 (Java) 문제 출처 : https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 스마트폰 백그라운드에 켜져있는 N개의 애플리케이션중 몇개의 애플리케이션을 종료해서 M만큼의 메모리를 확보하고싶다. 각 애플리케이션을 종료할때얻는 메모리양과 종료할때 필요한 비용이 주어질때, M만큼의 메모리를 확보하기위해 필요한 최소 비용을 구하는 문제다. 풀이 knapsack 문제였다. 개인적으로 dp배열을 생각하는게 어려웠다. 2차원 배열을 이용해 푸는것은 맞는것 같은데, M이 10,00..
[백준 / BOJ] 9881 Ski Course Design (Java) 문제 출처 : https://www.acmicpc.net/problem/9881 9881번: Ski Course Design Farmer John has N hills on his farm (1

티스토리툴바