본문 바로가기

브루트포스17

[백준] 10819번 차이를 최대로 JAVA (자바) 풀이 문제 10819번 (브루트포스, 백트래킹)  :  N개의 정수로 이루어진 배열 A    배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구해라 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|   [입력] :  첫째 줄에 N (3 ≤ N ≤ 8) :  둘째 줄에는 배열 A에 들어있는 정수 ( -100 ≤ 정수 ≤ 100 )   [출력] :  식의 최댓값을 출력    [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹  수열을 모두 바꿔가며 max 값을 찾기 때문에 브루트포스가 맞다  종료 조건) depth==N N개의 숫자를 모두 뽑았기 때문에 종료하고 sum 계산 후 result로 max값 뽑아내기  1. 계산은 i.. 2024. 6. 26.
[백준] 2589번 보물 JAVA (자바) 풀이 문제 2589(BFS)  :  보물섬 지도의 각 칸은 육지(L)나 바다(W)로 표시    이동은 상하좌우로 이웃한 육지로만 가능, 한 칸 이동하는데 한 시간이 걸린다    보물은 육지 두 곳에 나뉘어 묻혀있고 두 곳을 이동하는 최단거리를 구해라    같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다  예) 보물은 아래 표시된 두 곳에 묻혀 있고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간  [입력] :  첫째 줄에는 지도의 가로, 로 ( 가로, 세로의 크기는 각각 50이하 ) :  다음 줄부터 L과 W로 표시된 보물 지도 (빈칸없이)   [출력] :  보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력     [문제접근] 1. 출력 배열 사용하지 말고 큐에다 넣어버리기co.. 2024. 6. 21.
[백준] 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.
[백준] 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.
탐색 알고리즘 (브루트포스, DFS, BFS, 백트래킹) 탐색데이터 구조 내에서 가능한 경우의 수를 탐색해 최적의 결과를 찾는 방법선형 탐색 알고리즘 순차적 탐색이진 탐색비선형 탐색 알고리즘트리나 그래프 같이 복잡한 형태에 사용dfs / bfs  1. 브루트 포스완전 탐색모든 경우의 수 탐색단순하지만 경우의 수가 많아서 비효율적일 수 있다 2. DFS 깊이 우선 탐색그래프 또는 트리에서 모든 경로 탐색한 방향으로 깊숙이 노드 탐색 후 더이상 갈 곳이 없으면 다른 방향 탐색스택 / 재귀 함수 사용 3. 백트래킹DFS의 확장 개념해결 가능성 없는 경로일 경우 탐색 중지하고 되돌아가 다른 경로 탐색 4. BFS 너비 우선 탐색시작 노드에서 가까운 노드부터 탐색같은 깊이 층의 노드들 모두 탐색 후 층 내려가면서 탐색큐 함수 사용최단 경로 문제 알고리즘 선택 가이드 ▣.. 2024. 4. 30.
[백준] 1120번 문자열 JAVA (자바) 풀이 문제 1120 (문자열, 브루트포스) 길이가 N으로 같은 문자열 X와 Y X와 Y의 차이 = X [i] ≠ Y [i]인 i의 개수 (예, X = ”jimin”, Y = ”minji” 이면, 차이 = 4) 짧은 문자열 앞 혹은 뒤에 아무 알파벳 추가 연산을 반복해 문자열 길이를 같게 만든다 이때, 문자열 길이가 같으면서, 차이를 최소로 하는 프로그램을 작성해라 [입력] : 첫째 줄에 A, B 길이 ( 최대 50 / A 길이 ≤ B 길이 / 소문자 ) [출력] : 최소의 차이 출력 [참고] 규칙찾기 문자열 길이 차이 구하기 A문자열에 몇개의 알파벳을 더 붙여야 하는지 알기 위해서 문자열 길이 차이 = A 문자열 길이 만큼 다 순회하고 남은 개수 예를 들어 A = abc, B = eabcd 라면 처음엔 A의 .. 2024. 4. 16.

티스토리툴바