본문 바로가기

Java123

[백준] 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.
[백준] 6603번 로또 JAVA (자바) 풀이 문제 6603번 (백트래킹)  :  {1, 2, ..., 49}에서 6개 택  :  k개(k>6) 골라 집합 S 만들어 6개의 조합 만들기   [입력] :  각 줄의 첫 번째 수는 k (6     (입력 마지막 줄 = 0)  [출력] :  각 테스트 케이스마다 경우의 수 출력 (사전 순 / 중복 금지)  :  각 테스트 케이스 사이에는 빈 줄 출력   [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹  문제 조건 1) 숫자 중복금지  문제 조건 2) 수열 원소 오름차순   종료 조건) 배열이 M만큼 채워지면 출력하고 boolean false  N과 M(2) 문제 응용버전이다  마찬가지로 boolean이 필요없다 현재 숫자보다 무조건 다음 인덱스의 숫자가 커져야 하기 때문에  굳이 .. 2024. 5. 4.
[백준] 15652번 N과 M(4) JAVA (자바) 풀이 문제 15652번 (백트래킹)  :  1부터 N까지 자연수 중에서 M개를 고른 수열 (중복선택 가능)  :  고른 수열은 비내림차순비내림차순 : A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK    (예) N = 3, M = 2 인 경우    1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다    1, 1 / 1, 2 / 1, 3 / 2, 2 / 2, 3 이렇게 만든 수열을 한줄에 하나씩 출력한다   [입력] :  첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8) [출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X)   수열의 원소는 공백으로 구분해서 출력  : 수열은 사전 순으로 증가하는 순서로 출력   [과정]  탐색하자 → 브루트포스 / dfs →.. 2024. 5. 4.

티스토리툴바