본문 바로가기

알고리즘

 (100)
백준 2515 전시장 (java) https://www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1
백준 2632 피자 판매 https://www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 ( 3≤m, n� www.acmicpc.net 구현하는 문제! A피자에서 나올 수 있는 모든 경우의 합을 저장하고 B피자에서 나올 수 있는 모든 경우의 합을 저장 한 후 각각의 합을 비교해가면 된다. import java.io.*; import java.lang.reflect.Array; import java.util.*; public class Main { static BufferedReader br = new Buffe..
백준 16933 벽 부수고 이동하기 3 https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net -1을 까먹었다가 계속 틀린 문제 ㅠㅠㅠㅠㅠ import java.io.*; import java.util.*; class Move implements Comparable { int r, c, k, dist; boolean day; Move(int a, int b, int cc, int d, boolean day) { r = a; c = b; k = cc; di..
백준 4991 로봇 청소기 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net bfs와 dfs를 결합한 문제... 처음에 Input 때문에 아주 고생했다. 로봇청소기가 있는 위치는 소문자 o 이다. 벽은 소문자 x이다. 처음에 이걸 안했다가 아주 애먹었다. 가장 가까운 방법만 골라서 가는 그리디 알고리즘은 얼핏 생각하면 최적일 것 같지만 최적이 아닐 수 있다. 증명이 안된다. 그러므로 사용할 수 없다. 이 문제의 Input의 크기가 몹시 작기 때문에 모든 경우의 수를 무작정 계산하는..
백준 1507 궁금한 민호 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 플로이드 워셜을 응용한 문제다. 어렵지않다! 대신 문제 설명이 좀 이상하다. 분명 최소 거리쌍을 주었다고 했는데... -1이 나오는 케이스는 '현재 주어진 거리쌍이 최소 거리쌍이 아닌 경우'다. 문제가 좀 이상하지 않은가 싶긴한데... 암튼 그렇다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import jav..
백준 9370 미확인 도착지 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 다익스트라 문제인데 변형이 있다. 다익스트라 알고리즘은 분명 한 점(시작점)에서 다른 모든 점까지의 최단 거리를 구할 수 있는 알고리즘이다. 하지만 그 최단 거리의 경로 자체는 유일하지 않을 수도 있다. 그걸 잘 지적한 문제라고 생각한다. import java.awt.image.AreaAveragingScaleFilter; import java.io.*; import java.util.*; ..
백준18809 Gaaaaaaarden https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 구현 문제가 그렇듯 시간과의 싸움이었다... 보통의 bfs 구현문제가 방문 체크만 요구한다면 이 문제는 구현방법에 따라 2~3가지의 방문체크를 요구한다. 여러 배열을 쓰는 게 머리 아파서 flag 값을 나눠서 풀었다. 힘들다! import java.io.*; import java.util.*; class Pair { int r, c; Pa..
백준 1053 팰린드롬 공장 https://www.acmicpc.net/problem/1053 1053번: 팰린드롬 공장 팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다. 모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다. � www.acmicpc.net 다이나믹 프로그래밍 문제다. 즉, 점화식을 세워야 한다. dp[i][j] = i 부터 j까지의 문자열을 팰린드롬으로 만들 수 있는 최소 연산 횟수. dp[i][j] = min(dp[i+1][j] , dp[i][j-1], if(s[i] == s[j]) dp[i+1][j-1] else dp[i+1][j-2]+1) 문제는 4번 연산이다. 두 문자를 교환하는 연산을 최대 한 번 사용할 수 있는데... 언제 ..
백준 1958 LCS 3 https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다) www.acmicpc.net 삼중배열을 이용한 LCS 문제 요구하는 알고리즘이 선명한 문제는 상대적으로 쉬운 것 같다. import java.io.*; public class Main { static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static BufferedReader br = new BufferedReader(new InputStreamReader(System.i..
백준 14444, 13275 가장 긴 팰린드롬 부분 문자열 https://www.acmicpc.net/problem/14444 14444번: 가장 긴 팰린드롬 부분 문자열 알파벳 소문자로만 이루어진 문자열 S가 주어졌을 때, S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net https://www.acmicpc.net/problem/13275 13275번: 가장 긴 팰린드롬 부분 문자열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있으며 길이는 1보다 크거나 같고, 100,000보다 작거나 같다. www.acmicpc.net 두 개가 같은 문제다. 자바로 풀면 시간초과뜬다. 마나허 알고리즘을 사용하는 '전형적인' 문제다. /* 가장 긴 팰린드롬 부분 문자열 */ #..

티스토리툴바