본문 바로가기

Java125

[백준] 2670번 연속부분최대곱 JAVA (자바) 풀이 문제 2670번 (DP, 브루트포스) :  N개의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아 곱 출력   → 최대값 = 1.638 [입력] :  첫째 줄 양의 실수들의 개수 N ( N  ≤ 10000 자연수) :  다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다 ( 소수점 첫째자리까지 /  0.0 ≤ 수 ≤ 9.9 )  [출력] :  최댓값을 소수점 이하 넷째 자리에서 반올림해서 출력[설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다 탑다운 (Top-Down) 보텀업 (Bottom-Up)작은 크기로.. 2024. 6. 14.
[백준] 14916번 거스름돈 JAVA (자바) 풀이 문제 14916번 (DP) :  거스름돈 = 2원, 5원  :  거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램  :  예) 거스름돈이 15원이면 5원짜리 3개, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개   [입력] :  첫째 줄에 거스름돈 액수 n (1 ≤ n ≤ 100,000)   [출력] :  거스름돈 동전의 최소 개수를 출력 (거슬러 줄 수 없으면 -1 출력)[설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다 탑다운 (Top-Down) 보텀업 (Bottom-Up)작은 크기로 문제를 나.. 2024. 6. 11.
[백준] 16953번 A → B JAVA (자바) 풀이 문제 16953번 (bfs):  정수 A를 B로 바꾸고 필요한 연산의 최솟값을 구해라 :  가능한 연산X 2수의 가장 오른쪽에 1 추가  [입력] :  첫째 줄에 A, B (1 ≤ A )   [출력] :  연산의 최솟값에 1을 더한 값을 출력 (만들 수 없는 경우 -1 출력)   [과정]  1. int 말고 long 사용뒷자리에 1을 추가하게 될 경우 숫자가 너무 커질 수 있다 2 - 1. count = 0라면while문 초입에서 ++하고 시작2 - 2. count = 1라면 while문 끝에서 ++하기 3. if문 조건계산한 숫자(p)가 b보다 클 경우, 작을 경우, 같을 경우 딱 세 가지이다if(p==b)랑 if(p>b) 만해주고 나머지는 p 4. void가 아닌 int 사용void를 사용하려면 re.. 2024. 6. 9.
[백준] 2178번 미로 탐색 JAVA (자바) 풀이 문제 2178(BFS)  : N×M크기 미로 101111101010101011111011: 1 = 이동할 수 있는 칸  0 = 이동할 수 없는 칸 : (1, 1) ~ (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구해라  서로 인접한 칸으로만 이동할 수 있고 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다  [입력] :  첫째 줄에 두 정수 N, M (2 ≤ N, M ≤ 100) :  다음 N개의 줄에는 M개의 정수로 미로   [출력] :  첫째 줄에 지나야 하는 최소의 칸 수를 출력     [문제접근] 좌표 사용 시 int[] 나 Point 사용→ int[] 배열을 사용Queue q = new LinkedList();q.add(new int[] {x,y});→ Point 사용import.. 2024. 6. 4.
선형 자료구조 (배열, 스택, 큐) 자료구조 (Data Structure) 란- 개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법으로 선형과 비선형으로 구분할 수 있다 선형 자료구조 (Linear Data Structure) - 데이터 요소가 순차적으로 나열되어 있으며 첫번째부터 마지막 요소까지 백트래킹 없이 순회할 수 있다 1. 배열(Arrays) 1-1) Array- 가장 기본적인 배열로 ‘고정된 크기’를 가지며 동일한 데이터 타입만 저장할 수 있습니다.int[] arr = new int[5];for (int i = 0; i 메서드설명clone()배열 복사length배열 길이sort()배열 정렬fill()배열의 모든 요소를 특정 값으로 설정binarySearch()이진 검색을 수행하여 배열에서 지정된 값의 인덱스를 반환equ.. 2024. 6. 4.
[백준] 10974번 모든 순열 JAVA (자바) 풀이 문제 10974번 (백트래킹)  :  1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성   [입력] :  첫째 줄에 N(1 ≤ N ≤ 8)  [출력] :   첫째 줄부터 N개의 줄에 걸쳐서 모든 순열을 사전순으로 출력   [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹   문제 조건 1) 숫자 중복금지  문제 조건 2) 수열 원소 오름차순   종료 조건) 배열이 M만큼 채워지면 출력하고 boolean false  N과 M(1) 문제와 비슷하다 방문기록을 체크해가며 숫자를 추가한다   [코드]import java.io.*;import java.util.*;public class Main{ static int N,arr[]; static boolea.. 2024. 5. 27.
[SWEA] 13038. 교환학생 D3 JAVA (자바) 풀이 문제 13038번 (브루트포스) 교환학생들을 위한 수업은 특정 요일에만 진행된다 ( a1 ~ a7 )  수업 미진행 = 0 / 수업 진행 = 1일요일 = a1 / 월요일 = a2 / 토요일 = a7수업이 어떠한 요일에도 열리지 않는 경우는 없다. 교환학생으로 n일 동안 수업을 들으려고 한다. 최소 일수를 출력하라  [입력]: 첫 번째 줄에 테스트 케이스의 수 : 각 테스트케이스의 첫 번째 줄에는 첫 번째 줄에 정수 n (1≤ n ≤105)   그 다음 줄에는  7개의 정수 a1, a2, …, a7  [출력] : "#테스트케이스 정답" 출력    [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있어서 다시 되돌아 간다 → 백트래킹  ※ 과정 ※  시작 요일을 바꿔가며 가장 최소일 수인 min 값을 .. 2024. 5. 12.
[SWEA] 1491. 원재의 벽 꾸미기 D3 JAVA (자바) 풀이 문제 1491번 (브루트포스) 1 X 1타일 N개를 이용해 R X C 크기의 직사각형 인테리어 만들기원재의 방은 정사각형 형태이기 때문에 만드는 직사각형 인테리어를 최대한 정사각형에 가깝게 만들면서 최대한 많은 타일을 사용해라가중치 A, B를 가지고 나름의 식 = A X lR – Cl + B X (N - R X C)위의 값을 최소화하라 [입력] 첫 번째 줄에 테스트 케이스의 수 T 각 테스트 케이스의 첫 번째 줄에는 세 정수 N, A, B(1 ≤ N, A, B ≤ 105) [출력] 각 테스트 케이스마다 ‘#x'를 출력하고, 답을 출력한다.    [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹  ※ 최적의 조건 ※  A X |R – C| + B X (N - R X C) A, B, .. 2024. 5. 12.
[SWEA] 1206. [S/W 문제해결 기본] 1일차 - View D3 JAVA (자바) 풀이 문제 1206번 (브루트포스) 왼쪽과 오른쪽으로 창문을 열었을 때, 양쪽 모두 거리 2 이상의 공간이 확보될 때 조망권이 확보된다조망권이 확보된 세대의 수를 반환해라 [EX]  연두색으로 색칠된 6세대는 2칸 이상의 공백이 존재하므로 조망권 확보A와 B는 왼쪽 조망은 2칸 이상 확보, 오른쪽 조망은 한 칸만 확보C의 경우는 오른쪽 조망은 2칸이 확보, 왼쪽 조망이 한 칸 확보 [제약 사항] 가로 길이는 항상 1000이하맨 왼쪽과 맨 오른쪽 두 칸 공백각 빌딩의 높이는 최대 255   [입력]: 10개의 테스트케이스: 각 테스트케이스의 첫 번째 줄에는 건물의 개수 N (4 ≤ N ≤ 1000)  그 다음 줄에는 N개의 건물의 높이 (0 ≤ 각 건물의 높이 ≤ 255)  (맨 왼쪽, 오른쪽 두 칸에 있는 건.. 2024. 5. 12.
[SWEA] 3307. 최장 증가 부분 수열 D3 JAVA (자바) 풀이 문제 3307. 최장 증가 부분 수열 (DP) 수열 : { A1, A2, ... , AN }최장 증가 부분 수열 : { B1, B2, ... , BK }  (0≤K≤N, B1 AB1 ≤ AB2 ≤ ... ≤ ABK인 최대 K로 구성된 수열이다.예를 들어, 수열이 { 1, 3, 2, 5, 4, 7 } 이라면, 최장 부분 증가 수열의 길이는 4가 된다.[입력]: 첫 번째 줄 테스트 케이스의 수 T: 각 테스트 케이스의 첫째 줄에 수열의 길이 N(1≤N≤1,000)  둘째 줄에는 수열의 원소 N개 ( 1 ≤ N  ≤ 2³¹-1 자연수)[출력] ‘#T’ 최대 증가 부분 수열의 길이 출력   [과정] 초기 방식) 시작점을 하나씩 고정하면서 다음 노드로 순차적으로 돌면서 수가 더 크면 길이를 count 하는 방식으.. 2024. 5. 7.

티스토리툴바