dfs29 [백준] 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. [백준] 2529번 부등호 JAVA (자바) 풀이 문제 2529번 (백트래킹) : 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다 부등호 기호 앞 뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다 : 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있다 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다 [입력] : 첫 줄에 부등호 문자의 개수 정수 k : 그 다음 줄에는 k개의 부등호 기호 (k의 범위는 2 ≤ k ≤ 9) [출력] : k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력 (첫 자리가 0인 경우도 정수에 포함) [과정] 탐색하자 → 브루트.. 2024. 6. 25. [백준] 10971번 외판원 순회2 JAVA (자바) 풀이 문제 10971번 (백트래킹) : 1번 ~ N번 도시 한 도시에서 출발해 N개의 도시를 거쳐 원래의 도시로 돌아오는 순회 여행 경로 (한 번 갔던 도시로는 다시 갈 수 없다) : 이동 비용 W[i][j] = 도시 i에서 도시 j로 가기 위한 비용 (W[i][j] ≠ W[j][i]) W[i][i]는 항상 0 / 갈 수 없는 경우도 0 : 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오. [입력] : 첫째 줄에 도시의 수 N (2 ≤ N ≤ 10) : 다음 N개의 줄에는 비용 행렬 (각 행렬의 성분은 1,000,000 이하의 양의 정수) (갈 수 없는 경우는 0) [출력] : 순회에 필요한 최소 비용을 출력 [과정] 탐색하자 .. 2024. 6. 22. [백준] 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. [백준] 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. [백준] 15650번 N과 M(2) JAVA (자바) 풀이 문제 15650번 (백트래킹) : 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 골라서 수열 구하기 : 고른 수열은 오름차순 (예) N = 3, M = 2 인 경우 1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다 1, 2 / 1, 3 / 2, 3 이렇게 만든 수열을 한줄에 하나씩 출력한다 [입력] : 첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8) [출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X) 수열의 원소는 공백으로 구분해서 출력 : 수열은 사전 순으로 증가하는 순서로 출력 [과정] 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 문제 조건 .. 2024. 5. 3. 탐색 알고리즘 (브루트포스, DFS, BFS, 백트래킹) 탐색데이터 구조 내에서 가능한 경우의 수를 탐색해 최적의 결과를 찾는 방법선형 탐색 알고리즘 순차적 탐색이진 탐색비선형 탐색 알고리즘트리나 그래프 같이 복잡한 형태에 사용dfs / bfs 1. 브루트 포스완전 탐색모든 경우의 수 탐색단순하지만 경우의 수가 많아서 비효율적일 수 있다 2. DFS 깊이 우선 탐색그래프 또는 트리에서 모든 경로 탐색한 방향으로 깊숙이 노드 탐색 후 더이상 갈 곳이 없으면 다른 방향 탐색스택 / 재귀 함수 사용 3. 백트래킹DFS의 확장 개념해결 가능성 없는 경로일 경우 탐색 중지하고 되돌아가 다른 경로 탐색 4. BFS 너비 우선 탐색시작 노드에서 가까운 노드부터 탐색같은 깊이 층의 노드들 모두 탐색 후 층 내려가면서 탐색큐 함수 사용최단 경로 문제 알고리즘 선택 가이드 ▣.. 2024. 4. 30. [백준] 17484번 진우의 달 여행 JAVA (자바) 풀이 문제 17484 지구와 우주사이는 N X M 행렬 각 원소의 값 = 지날 때 소모되는 연료 양 연지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 연료의 최소값을 구해라 지구 → 달 경우 우주선 이동 가능 방향 우주선 이전에 움직인 방향으로 움직일 수 없다 (같은 방향으로 두번 연속 이동 불가) [입력] : 첫 번째 줄 지구와 달 사이 공간을 나타내는 행렬 크기 N, M ( 2≤ N, M ≤ 6 ) : N줄 동안 각 행렬의 원소 값 ( 행렬의 원소값은 100 이하의 자연수 ) 6 4 5 8 5 1 3 5 8 4 9 77 65 5 2 1 5 2 5 98 1 5 4 95 67 58 [출력] : 최소 연료의 값 29 [코드] import java.io.*; import java.util.*; class .. 2024. 1. 30. [백준] 10026번 적록색약 JAVA (자바) 풀이 문제 10026 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다 구역은 같은 색으로 이루어져 있다 같은 색상이 상하좌우로 인접해 있는 경우 같은 구역으로 취급 적록색약인 사람은 초록과 빨강은 같은 색으로 보여진다 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구해라 (예시) RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람 : 구역 총 4개 (빨강 2, 파랑 1, 초록 1) 적록색약인 사람은 : 구역 총 3개 볼 수 있다. (빨강 & 초록 2, 파랑 1) [입력] : 첫째 줄에 N (1 ≤ N ≤ 100) : 둘째 줄부터 N개 줄에는 그림 5 RRRBB GGBBB BBBRR BBRRR RRRRR [출력] : 적록.. 2024. 1. 22. 이전 1 2 3 다음
