본문 바로가기

분류 전체보기153

[백준] 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.
[백준] 1504번: 특정한 최단 경로 (Java) 1. 문제설명방향성 없는 그래프에서 1번 정점에서부터 N번 정점으로 최단 거리로 이동하려 한다. 한 번 이동했던 정점 또는 간선을 다시 이동할 수 있다. 주어진 두 정점을 반드시 거치면서 최단 경로를 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식`Node` 객체를 사용하여 정점과 거리 정보를 저장한다.인접리스트 형식(`List[] list`)으로 간선 정보를 저장한다. (양방향으로)다익스트라 알고리즘을 사용한다.우선순위 큐를 사용하여 가장 짧은 경로를 먼저 처리하고, 현재 경로에서 더 짧은 경로를 찾으면 경로 정보를 갱신하는 방식으로 구현한다.두 가지 경로를 구한다.1 → v1 → v2 → N1 → v2 → v1 → N총 3번의 다익스트라 메서드 호출을 통해 두 가지 경로의 최.. 2024. 9. 10.
[백준] 1238번: 파티 (Java) 1. 문제설명N개의 마을에 각각 한 명의 학생이 있다. 이 마을 사이에는 M개의 단방향 도로들이 있고 i번째 길을 지나는데 T(i)의 시간을 소비한다. 각각의 학생들을 최단 시간에 파티(X)에 오고 가기를 원한다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생을 구하는 문제이다.모든 학생은 집에서 X에 갈 수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식인접리스트 형식으로 그래프 정보를 입력받는다.정방향 그래프: X 마을에서 각 마을로 가는 경로를 구할 때 사용역방향 그래프: 각 마을에서 X 마을로 가는 경로를 구할 때 사용다익스트라 알고리즘을 두 번 실행한다.첫 번째: 정방향 그래프를 사용하여 X에서 각 마을로 .. 2024. 9. 10.
반응형