깊이우선탐색3 [백준] 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. 탐색 알고리즘 (브루트포스, DFS, BFS, 백트래킹) 탐색데이터 구조 내에서 가능한 경우의 수를 탐색해 최적의 결과를 찾는 방법선형 탐색 알고리즘 순차적 탐색이진 탐색비선형 탐색 알고리즘트리나 그래프 같이 복잡한 형태에 사용dfs / bfs 1. 브루트 포스완전 탐색모든 경우의 수 탐색단순하지만 경우의 수가 많아서 비효율적일 수 있다 2. DFS 깊이 우선 탐색그래프 또는 트리에서 모든 경로 탐색한 방향으로 깊숙이 노드 탐색 후 더이상 갈 곳이 없으면 다른 방향 탐색스택 / 재귀 함수 사용 3. 백트래킹DFS의 확장 개념해결 가능성 없는 경로일 경우 탐색 중지하고 되돌아가 다른 경로 탐색 4. BFS 너비 우선 탐색시작 노드에서 가까운 노드부터 탐색같은 깊이 층의 노드들 모두 탐색 후 층 내려가면서 탐색큐 함수 사용최단 경로 문제 알고리즘 선택 가이드 ▣.. 2024. 4. 30. 이전 1 다음
