탐색4 [백준] 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. 탐색 알고리즘2 (이분탐색, DP) 탐색 DP(Dynamic Programming, 동적 계획법) 겹치는 결과를 별도의 메모리 영역에 저장해서 한번만 계산하고 재사용하도록 한다 DP 공식 f(n) = f(n-1) + f(n-2) 탑다운 (Top-Down) 보텀업 (Bottom-Up)작은 크기로 문제를 나눠서 해결작은 것부터 해결해서 점차 빌드업메모제이션 (memoization)타뷸레이션 (tabulation)일부만 계산해도 답이 나올 때모두 계산해야 답이 나올 재귀반복문시간 복잡도 O(n)시간 복잡도 O(n) DP의 조건최적 부분 구조(Optimal Substructure)큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.중복되는 부분 문제(Overlapping Subproblem)부분 문제가 중.. 2024. 6. 3. [백준] 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. 탐색 알고리즘 (브루트포스, DFS, BFS, 백트래킹) 탐색데이터 구조 내에서 가능한 경우의 수를 탐색해 최적의 결과를 찾는 방법선형 탐색 알고리즘 순차적 탐색이진 탐색비선형 탐색 알고리즘트리나 그래프 같이 복잡한 형태에 사용dfs / bfs 1. 브루트 포스완전 탐색모든 경우의 수 탐색단순하지만 경우의 수가 많아서 비효율적일 수 있다 2. DFS 깊이 우선 탐색그래프 또는 트리에서 모든 경로 탐색한 방향으로 깊숙이 노드 탐색 후 더이상 갈 곳이 없으면 다른 방향 탐색스택 / 재귀 함수 사용 3. 백트래킹DFS의 확장 개념해결 가능성 없는 경로일 경우 탐색 중지하고 되돌아가 다른 경로 탐색 4. BFS 너비 우선 탐색시작 노드에서 가까운 노드부터 탐색같은 깊이 층의 노드들 모두 탐색 후 층 내려가면서 탐색큐 함수 사용최단 경로 문제 알고리즘 선택 가이드 ▣.. 2024. 4. 30. 이전 1 다음
