알고리즘 문제풀이/BOJ
-
BOJ 16987번 계란으로 계란치기 문제 자바(java) 풀이 랭크 : 실버3 백준 16987번 계란으로 계란치기 문제 정리 계란으로 계란을 치는 경우 다음과 같은 점들을 고려한다. 1.1 계란에는 내구도와 무게가 정해져 있다. 1.2 계란으로 서로를 치면 계란의 내구도는 상대 계란의 무게 만큼 깎이게 된다. 1.3 내구도가 0이 되는 순간 계란이 깨진다. 계란을 왼쪽 부터 차례로 들어 한 번씩만 다른 계란을 쳐서 최대한 많은 계란을 깨려고 한다. 계란을 치는 과정은 다음과 같다. 3.1 가장 왼쪽 계란을 든다. 3.2 손에 든 계란으로 깨지지 않은 계란중 하나를 친다. 만약 손에 든 계란이 깨졌거나 깨지지 않은 계란이 없다면 아무일도 하지 않는다. 3.3 최근에 든 계란의 바로 오른쪽 계란을 들고 반..
[DFS] 백준 16987번 계란으로 계란치기 자바(java) 풀이BOJ 16987번 계란으로 계란치기 문제 자바(java) 풀이 랭크 : 실버3 백준 16987번 계란으로 계란치기 문제 정리 계란으로 계란을 치는 경우 다음과 같은 점들을 고려한다. 1.1 계란에는 내구도와 무게가 정해져 있다. 1.2 계란으로 서로를 치면 계란의 내구도는 상대 계란의 무게 만큼 깎이게 된다. 1.3 내구도가 0이 되는 순간 계란이 깨진다. 계란을 왼쪽 부터 차례로 들어 한 번씩만 다른 계란을 쳐서 최대한 많은 계란을 깨려고 한다. 계란을 치는 과정은 다음과 같다. 3.1 가장 왼쪽 계란을 든다. 3.2 손에 든 계란으로 깨지지 않은 계란중 하나를 친다. 만약 손에 든 계란이 깨졌거나 깨지지 않은 계란이 없다면 아무일도 하지 않는다. 3.3 최근에 든 계란의 바로 오른쪽 계란을 들고 반..
2020.04.01 -
BOJ 2580번 스도쿠 자바(java) 풀이 백트래킹의 대표적인 문제중 하나라고 할 수 있습니다. 백트래킹 문제에 익숙하지 않다면 N-Queen 문제와 이 문제를 꼭 풀어보시기 바랍니다. 난이도: 골드4 BOJ 2580번 스도쿠 문제 정리 9x9 판으로 이루어진 판에 1~9 까지의 숫자들이 써있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1~9까지의 숫자가 한 번씩만 나타난다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1~9 까지의 숫자가 한 번씩만 나타난다. 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오. 스도쿠 판을 채우는 방법이 여럿인 경우 그 중 하나만을 출력한다. 문제 풀이 n-queen 문제와 유사한 방식으로 백트래킹을 이용하여 문제..
[백트래킹] 백준 2580번 스도쿠 자바(java) 풀이BOJ 2580번 스도쿠 자바(java) 풀이 백트래킹의 대표적인 문제중 하나라고 할 수 있습니다. 백트래킹 문제에 익숙하지 않다면 N-Queen 문제와 이 문제를 꼭 풀어보시기 바랍니다. 난이도: 골드4 BOJ 2580번 스도쿠 문제 정리 9x9 판으로 이루어진 판에 1~9 까지의 숫자들이 써있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1~9까지의 숫자가 한 번씩만 나타난다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1~9 까지의 숫자가 한 번씩만 나타난다. 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오. 스도쿠 판을 채우는 방법이 여럿인 경우 그 중 하나만을 출력한다. 문제 풀이 n-queen 문제와 유사한 방식으로 백트래킹을 이용하여 문제..
2020.03.31 -
BOJ 18110번 solved.ac 문제 자바(java) 풀이 랭크 : 실버4 백준 18110번 solved.ac 문제 정리 난이도 의견은 문제를 푼 사람들이 생각한 난이도를 의미하는 정수 하나로 주어진다. 아직 아무 의견이 없다면 문제의 난이도는 0으로 결정한다. 의견이 하나 이상 있다면, 문제의 난이도는 모든 사람의 난이도 의견의 30%로 절사평균으로 결정한다. 절사평균: 극단적인 값들이 평균 값을 왜곡하는 것을 방지하기 위해 가장 큰 값들과 가장 작은 값들을 제외하고 평균을 구하는 것! 30% 절사 평균: 위에서 15%, 아래에서 15%를 제외하고 평균을 계산한다. 제외 되는 사람 수는 반올림 해서 결정한다.(25명인 경우 0.15를 곱하면 3.75가 나오는데 반올림하여 4명 절삭) 계산된 평균도..
[정렬, 반올림] 백준 18110번 solved.ac 자바(java) 풀이BOJ 18110번 solved.ac 문제 자바(java) 풀이 랭크 : 실버4 백준 18110번 solved.ac 문제 정리 난이도 의견은 문제를 푼 사람들이 생각한 난이도를 의미하는 정수 하나로 주어진다. 아직 아무 의견이 없다면 문제의 난이도는 0으로 결정한다. 의견이 하나 이상 있다면, 문제의 난이도는 모든 사람의 난이도 의견의 30%로 절사평균으로 결정한다. 절사평균: 극단적인 값들이 평균 값을 왜곡하는 것을 방지하기 위해 가장 큰 값들과 가장 작은 값들을 제외하고 평균을 구하는 것! 30% 절사 평균: 위에서 15%, 아래에서 15%를 제외하고 평균을 계산한다. 제외 되는 사람 수는 반올림 해서 결정한다.(25명인 경우 0.15를 곱하면 3.75가 나오는데 반올림하여 4명 절삭) 계산된 평균도..
2020.03.30 -
BOJ 9252번 LCS2 문제 자바(java) 풀이 백준 9252번 문제를 풀 수 있으면 백준 9251번 LCS를 풀 수 있기 때문에 9252번 문제를 기준으로 설명드리겠습니다!! 난이도: 골드5 BOJ 9252번 LCS2 문제정리 두 수열이 주어졌을때 모두의 부분 수열이 되는 수열 중 가장 긴 것(LCS)을 찾아라 문자는 대문자로만 이루어지며 최대 1000글자 긴 문자가 여러개 있다면 아무거나 출력하고, 최대 길이도 출력하여라 LCS 이 문제는 문제 이름이 그렇듯이 LCS(Longest Common Subsequence) 알고리즘을 이용해 풀 수 있습니다. subsequence는 보통 알고 있는 substring하고는 다릅니다. subsequence: 연속되지 않은 부분 문자열 substring: 연..
[LCS, DP] 백준 9251번 LCS, 9252번 LCS2 문제 자바(java) 풀이BOJ 9252번 LCS2 문제 자바(java) 풀이 백준 9252번 문제를 풀 수 있으면 백준 9251번 LCS를 풀 수 있기 때문에 9252번 문제를 기준으로 설명드리겠습니다!! 난이도: 골드5 BOJ 9252번 LCS2 문제정리 두 수열이 주어졌을때 모두의 부분 수열이 되는 수열 중 가장 긴 것(LCS)을 찾아라 문자는 대문자로만 이루어지며 최대 1000글자 긴 문자가 여러개 있다면 아무거나 출력하고, 최대 길이도 출력하여라 LCS 이 문제는 문제 이름이 그렇듯이 LCS(Longest Common Subsequence) 알고리즘을 이용해 풀 수 있습니다. subsequence는 보통 알고 있는 substring하고는 다릅니다. subsequence: 연속되지 않은 부분 문자열 substring: 연..
2020.03.29 -
BOJ 5427번 불 문제 자바(java) 풀이 랭크 : 골드4 백준 5427번 불 문제 정리 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있고, 불이 번져서 출구를 향해 뛰고 있다. 매 초마다 불은 동서남북 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있다. 이동하는데 1초가 걸린다. 상근이는 벽이 있거나 불이 번졌으면 갈 수 없다. 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다!!!! 문자 #: 벽 .: 지나갈 수 있는 공간 @: 상근이의 미로에서의 초기위치(지나갈 수 있는 공간) *: 불이난 공간 불이 도달하기 전에 미로를 탈출할 수 없는 경우 'IMPOSSIBLE' 출력 탈출할 수 있는 경우 가장 빠른 탈출시간 출력 문제..
[BFS] 백준 5427, 4179번 불(Fire) 문제 자바(java) 풀이BOJ 5427번 불 문제 자바(java) 풀이 랭크 : 골드4 백준 5427번 불 문제 정리 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있고, 불이 번져서 출구를 향해 뛰고 있다. 매 초마다 불은 동서남북 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있다. 이동하는데 1초가 걸린다. 상근이는 벽이 있거나 불이 번졌으면 갈 수 없다. 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다!!!! 문자 #: 벽 .: 지나갈 수 있는 공간 @: 상근이의 미로에서의 초기위치(지나갈 수 있는 공간) *: 불이난 공간 불이 도달하기 전에 미로를 탈출할 수 없는 경우 'IMPOSSIBLE' 출력 탈출할 수 있는 경우 가장 빠른 탈출시간 출력 문제..
2020.03.28 -
BOJ 6118번 숨바꼭질 자바(java) 풀이 랭크 : 실버1 백준 6118번 숨바꼭질 문제 정리 재서기는 헛간에 숨으려 한다. 헛간의 개수(N)는 최대 20,000개 이다. 수혀니는 1번 헛간 부터 찾는다. 모든 헛간은 최대 50,000개의 양방향 길(M)로 이루어져 있다. 재서기의 발냄새는 1번 헛간에서의 거리(지나야 하는 길의 최소 개수)가 멀어질 수록 감소한다. 재서기가 발냄새를 최대한 숨길 수 있는 헛간을 찾아라. 숨어야 하는 헛간 번호(여러개 있다면 가장 작은 번호), 헛간까지의 거리, 그 헛간과 같은 거리를 갖는 헛간의 개수 출력 문제 풀이 그래프 문제로 해석합니다. 그러면 모든 헛간은 이어져 있고 수혀니는 1번 헛간 부터 출발합니다. 재서기가 발냄새를 최대한 숨길 수 있는 헛간이란, 1번..
[다익스트라] 백준 6118번 숨바꼭질 자바(java) 풀이BOJ 6118번 숨바꼭질 자바(java) 풀이 랭크 : 실버1 백준 6118번 숨바꼭질 문제 정리 재서기는 헛간에 숨으려 한다. 헛간의 개수(N)는 최대 20,000개 이다. 수혀니는 1번 헛간 부터 찾는다. 모든 헛간은 최대 50,000개의 양방향 길(M)로 이루어져 있다. 재서기의 발냄새는 1번 헛간에서의 거리(지나야 하는 길의 최소 개수)가 멀어질 수록 감소한다. 재서기가 발냄새를 최대한 숨길 수 있는 헛간을 찾아라. 숨어야 하는 헛간 번호(여러개 있다면 가장 작은 번호), 헛간까지의 거리, 그 헛간과 같은 거리를 갖는 헛간의 개수 출력 문제 풀이 그래프 문제로 해석합니다. 그러면 모든 헛간은 이어져 있고 수혀니는 1번 헛간 부터 출발합니다. 재서기가 발냄새를 최대한 숨길 수 있는 헛간이란, 1번..
2020.03.27