BOJ 9252번 LCS2 문제 자바(java) 풀이 백준 9252번 문제를 풀 수 있으면 백준 9251번 LCS를 풀 수 있기 때문에 9252번 문제를 기준으로 설명드리겠습니다!! 난이도: 골드5 BOJ 9252번 LCS2 문제정리 두 수열이 주어졌을때 모두의 부분 수열이 되는 수열 중 가장 긴 것(LCS)을 찾아라 문자는 대문자로만 이루어지며 최대 1000글자 긴 문자가 여러개 있다면 아무거나 출력하고, 최대 길이도 출력하여라 LCS 이 문제는 문제 이름이 그렇듯이 LCS(Longest Common Subsequence) 알고리즘을 이용해 풀 수 있습니다. subsequence는 보통 알고 있는 substring하고는 다릅니다. subsequence: 연속되지 않은 부분 문자열 substring: 연..

BOJ 5427번 불 문제 자바(java) 풀이 랭크 : 골드4 백준 5427번 불 문제 정리 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있고, 불이 번져서 출구를 향해 뛰고 있다. 매 초마다 불은 동서남북 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있다. 이동하는데 1초가 걸린다. 상근이는 벽이 있거나 불이 번졌으면 갈 수 없다. 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다!!!! 문자 #: 벽 .: 지나갈 수 있는 공간 @: 상근이의 미로에서의 초기위치(지나갈 수 있는 공간) *: 불이난 공간 불이 도달하기 전에 미로를 탈출할 수 없는 경우 'IMPOSSIBLE' 출력 탈출할 수 있는 경우 가장 빠른 탈출시간 출력 문제..

BOJ 6118번 숨바꼭질 자바(java) 풀이 랭크 : 실버1 백준 6118번 숨바꼭질 문제 정리 재서기는 헛간에 숨으려 한다. 헛간의 개수(N)는 최대 20,000개 이다. 수혀니는 1번 헛간 부터 찾는다. 모든 헛간은 최대 50,000개의 양방향 길(M)로 이루어져 있다. 재서기의 발냄새는 1번 헛간에서의 거리(지나야 하는 길의 최소 개수)가 멀어질 수록 감소한다. 재서기가 발냄새를 최대한 숨길 수 있는 헛간을 찾아라. 숨어야 하는 헛간 번호(여러개 있다면 가장 작은 번호), 헛간까지의 거리, 그 헛간과 같은 거리를 갖는 헛간의 개수 출력 문제 풀이 그래프 문제로 해석합니다. 그러면 모든 헛간은 이어져 있고 수혀니는 1번 헛간 부터 출발합니다. 재서기가 발냄새를 최대한 숨길 수 있는 헛간이란, 1번..

BOJ 2568번 전깃줄-2 문제 자바(java) 풀이 랭크 : 골드2 백준 2568번 전깃줄-2 문제 정리 교차하는 전깃줄을 없애서 전깃줄이 교차하지 않도록 하려고 한다. 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄 최소 개수 구하기 전깃줄의 개수는 최대 100,000개 이다. 문제 풀이 전깃줄의 상태를 왼쪽 기준 오름차순으로 나열하면 아래와 같습니다. A 전봇대: 1 2 3 4 6 7 9 10 B 전봇대: 8 2 9 1 4 6 7 10 어떻게 하면 제일 조금 자를 수 있을까 생각해보면 B 전봇대의 1,2,3번째 전깃줄을 자르면 3개로 제일 작게 자르는 경우가 됩니다. 왜나하면 왼쪽수는 이미 증가 상태이기 때문에 오른쪽도 오름차순 이면 전깃줄이 엉키지 않습니다. 즉 최장 증..

BOJ 6549번 히스토그램에서 가장 큰 직사각형 문제 자바(java) 풀이 랭크 : 골드1 백준 6549번 히스토그램에서 가장 큰 직사각형 문제 정리 히스토그램: 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형 각 직사각형을 같은 너비를 가지지만 높이가 다를 수 있다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 문제 풀이 우선 넓이를 어떻게 구해야 하는지 파악해야 합니다. 넓이는 구간에서 높이가 작은 직사각형에 depend 됩니다. 만약 1-3구간에서의 높이가 [3,1,2]라면 높이 1이 가장 작기 때문에 이 구간에서의 넓이는 1x3(구간의 길이)=3이 됩니다. 이 방식을 이용해서 1-1, 1-2, 1-3, ... 1-n 2-1, 2-2, 2-3, ... 2-n ... n..

BOJ 2565번 전깃줄 문제 자바(java) 풀이 랭크 : 실버1 백준 2565번 전깃줄 문제 정리 교차하는 전깃줄을 없애서 전깃줄이 교차하지 않도록 하려고 한다. 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄 최소 개수 구하기 전깃줄의 개수는 최대 100개 이다. 문제 풀이 전깃줄의 상태를 왼쪽 기준 오름차순으로 나열하면 아래와 같습니다. A 전봇대: 1 2 3 4 6 7 9 10 B 전봇대: 8 2 9 1 4 6 7 10 어떻게 하면 제일 조금 자를 수 있을까 생각해보면 B 전봇대의 1,2,3번째 전깃줄을 자르면 3개로 제일 작게 자르는 경우가 됩니다. 왜나하면 왼쪽수는 이미 증가 상태이기 때문에 오른쪽도 오름차순 이면 전깃줄이 엉키지 않습니다. 즉 최장 증가 수열(Lon..