본문 바로가기

전체 글156

[백준] 1941번: 소문난 칠공주 (Java) 1. 문제설명총 25명의 여학생들이 5x5의 정사각형 격자 형태로 자리가 배치되어 있다. S(이다솜파)와 Y(임도연파)를 값으로 갖는 5*5 행렬이 주어졌을 때 아래 규칙을 만족하는 모든 경우의 수를 구한다.7명의 학생들로 구성되어야 하고, 7명의 자리는 서로 가로나 세로로 인접해야 한다.7명의 학생 중 S 학생이 적어도 4명 이상은 반드시 포함되어야 한다.시간 제한: 2초메모리 제한: 256MB 2. 접근 방식25자리 중 7자리를 선택하는데, ‘S’ 학생이 4명 이상 포함되도록 한다. (조합, 백트래킹)BFS를 사용해 해당 7개의 자리가 모두 상하좌우로 연결되어 있는지 확인한다.선택된 7명의 자리가 서로 인접한디 BFS로 확인한다. 인접할 경우 count 증가시킨다. 3. 틀린 이유2차원 배열로 백트래.. 2024. 9. 13.
[백준] 14888번: 연산자 끼워넣기 (Java) 1. 문제설명N개의 수로 이루어진 수열에서, 수와 수 사이에 연산자를 하나씩 넣어 수식을 만들 수 있다. 식의 계산은 연산자 우선순위를 무시하고 앞에서부터 진행한다. 나눗셈의 경우 몫만 취하며, 음수를 나눌 때는 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼다.N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구한다. (주어진 수의 순서를 바꿀 수 없고, 어떤 식이더라도 -10억보다 크거나 같고, 10억보다 작거나 같은 INT 범위의 결과가 나오는 입력만 주어진다.)시간 제한: 2초메모리 제한: 512MB 2. 접근 방식수와 연산자를 배열에 저장한다.모든 경우의 식을 계산해야 한다. ⇒ 완전탐색, 백트래킹메서드에서 “다음 계산할 수의 인덱스(`numI.. 2024. 9. 13.
[백준] 16987번: 계란으로 계란치기 (Java) 1. 문제설명계란은 내구도와 무게에 대한 정보가 주어지고, 왼쪽부터 차례로 들어 한 번씩만 다른 계란 쳐 최대한 많은 계란을 깨는 문제이다. 계란의 내구도는 상대 계란으 무게만큼 깎이게 되고, 내구도가 0 이하가 되면 깨진다.계란을 치는 과정:가장 왼쪽 계란을 든다.들고 있는 계란으로 다른 계란 중 하나를 친다. 만약 손에 든 계란이 깨졌거나 다른 모든 계란이 깨진 경우 넘어간다.최근에 든 계란의 오른쪽 계란을 들고 2번 과정을 반복한다. 가장 오른쪽 계란을 들게 되면 종료한다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식참고: https://buly.kr/4bgWSet계란의 내구도와 무게를 각각 다른 배열에 저장한다.백트래킹을 사용하여 계란을 깨뜨리는 모든 경우의 수를 구한다.마지막 계란을 .. 2024. 9. 13.
[백준] 1927번: N번째 큰 수 (Java) 1. 문제설명NxN의 표에 int 범위의 수가 채워져 있다. 채워진 모든 수는 자신의 한 칸 위에 있는 수보다 크다. 이러한 표가 주어졌을 때 N번째 큰 수를 찾는 문제이다.시간 제한: 1초메모리 제한: 12MB (Java 11: 384 MB) 2. 접근 방식우선순위 큐를 사용하여 내림차순으로 표의 모든 값을 저장한다.N-1번 큐의 맨 앞의 값을 제거하고, N번째의 값을 출력한다. 3. 최종 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputS.. 2024. 9. 11.
[백준] 11279번: 최대 힙 (Java) 1. 문제설명최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 구하는 문제이다.x가 자연수이면 배열에 x를 넣는다.x가 0이면 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.시간 제한: 1초 (Java 11: 2초)메모리 제한: 256MB 2. 접근 방식우선순위 큐를 사용하여 최대 힙을 구현한다.최대 힙이기 때문에 우선순위 큐는 내림차순 정렬되도록 설정한다. (참고)연산x가 자연수 ⇒ 값 추가x가 0 ⇒ 가장 큰 값 출력 & 제거 ⇒ 큐의 맨 첫 번째 값 출력 & 제거만약 큐가 비어있으면 0을 출력 3. 최종 코드import java.io.*;import java.util.*;public class Main { public s.. 2024. 9. 11.
[백준] 1927번: 최소 힙 (Java) 1. 문제설명최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 구하는 문제이다.x가 자연수이면 배열에 x를 넣는다.x가 0이면 배열에 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작한다.시간 제한: 1초 (Java 11: 2초)메모리 제한: 128MB 2. 접근 방식우선순위 큐를 사용하여 최소 힙을 구현한다.연산x가 자연수 ⇒ 값 추가x가 0 ⇒ 가장 작은 값 출력 & 제거 ⇒ 큐의 맨 첫 번째 값 출력 & 제거만약 큐가 비어있으면 0을 출력 3. 최종 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Pr.. 2024. 9. 11.
반응형