알고리즘 - Baekjoon

[백준] 1926번 : 그림 Silver1(실버1) - JAVA[자바]

[Silver I] 그림 - 1926 문제 링크 성능 요약 메모리: 44896 KB, 시간: 448 ms 분류 너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색 문제 설명 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다. 입력 첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공..

[백준] 3986번 : 좋은 단어 Silber4(실버4) - JAVA[자바]

[Silver IV] 좋은 단어 - 3986 문제 링크 성능 요약 메모리: 24996 KB, 시간: 548 ms 분류 자료 구조, 스택 제출 일자 2023년 10월 25일 11:20:33 문제 설명 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다. 평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서..

[백준] 2512번 : 예산 Silver2(실버2) - JAVA[자바]

[Silver II] 예산 - 2512 문제 링크 성능 요약 메모리: 30104 KB, 시간: 412 ms 분류 이분 탐색, 매개 변수 탐색 제출 일자 2023년 10월 25일 10:40:22 문제 설명 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배..

[백준] 16987번 : 계란으로 계란치기 Gold5(골드5) - JAVA[자바]

[Gold V] 계란으로 계란치기 - 16987 문제 링크 성능 요약 메모리: 18356 KB, 시간: 280 ms 분류 백트래킹, 브루트포스 알고리즘 제출 일자 2023년 10월 24일 14:31:26 문제 설명 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱걸이를 5회 하는 기적의 운동 루틴을 통해 뇌와 근육을 동시에 단련한다. 근육을 단련할 때 식단이 정말로 중요하다는 것을 아는 인범이는 탄수화물이 많은 밥이나 빵 따위의 아침 식사를 대신해 단백질이 많은 계란찜을 해먹는다. 계란찜을 먹기 위해서는 계란을 깨야 하는데, 인범이는 힘이 너무 넘치는 나머지..

[백준] 10971번 : 외판원 순회2 Silver2(실버2) - JAVA[자바]

[Silver II] 외판원 순회 2 - 10971 문제 링크 성능 요약 메모리: 19624 KB, 시간: 524 ms 분류 백트래킹, 브루트포스 알고리즘, 외판원 순회 문제 제출 일자 2023년 10월 24일 11:32:56 문제 설명 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순..

[백준] 15666번 : N과 M(12) Silver2(실버2) - JAVA[자바]

[Silver II] N과 M (12) - 15666 문제 링크 성능 요약 메모리: 19900 KB, 시간: 268 ms 분류 백트래킹 제출 일자 2023년 10월 24일 11:02:20 문제 설명 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 ..

[백준] 15665번 : N과 M(11) Silver2(실버2) - JAVA[자바]

[Silver II] N과 M (11) - 15665 문제 링크 성능 요약 메모리: 90956 KB, 시간: 580 ms 분류 백트래킹 제출 일자 2023년 10월 24일 10:58:41 문제 설명 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은..

[백준] 15664번 :N과 M(10) Silver2(실버2) - JAVA[자바]

[Silver II] N과 M (10) - 15664 문제 링크 성능 요약 메모리: 18376 KB, 시간: 224 ms 분류 백트래킹 제출 일자 2023년 10월 24일 10:53:50 문제 설명 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열..