dfs34 [백준] 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 (DFS, BFS) 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다구역은 같은 색으로 이루어져 있다같은 색상이 상하좌우로 인접해 있는 경우 같은 구역으로 취급적록색약인 사람은 초록과 빨강은 같은 색으로 보여진다 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구해라 (예시) RRRBBGGBBBBBBRRBBRRRRRRRR 적록색약이 아닌 사람 : 구역 총 4개 (빨강 2, 파랑 1, 초록 1) 적록색약인 사람은 : 구역 총 3개 볼 수 있다. (빨강 & 초록 2, 파랑 1) [입력] : 첫째 줄에 N (1 ≤ N ≤ 100) : 둘째 줄부터 N개 줄에는 그림5RRRBBGGBBBBBBRRBBRRRRRRRR [출력] :.. 2024. 1. 22. [백준] 2468번 안전 영역 JAVA (자바) 풀이 문제 2468 (dfs, 백트래킹)지역의 높이 정보를 파악지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정각 지역의 높이 정보 = N크기의 2차원 배열 형태배열의 각 원소 = 높이 침수 정도를 어떤 높이로 설정해야 안전한 영역이 최대가 되는지 계산해라 예) N=5 → 5 x 5 배열 6826232346673327253689527 높이가 4 이하인 지점 물에 잠겼다 = 회색6826232346673327253689527 → 안전한 영역 = 물에 잠기지 않는 지점 상, 하, 좌, 우로 인접하며 그 크기가 최대인 영역→ 안전한 영역 = 5개 높이가 6이하인 지점이 잠긴다면 안전.. 2024. 1. 22. [백준] 2210번 숫자판 점프 JAVA (자바) 풀이 문제 2210번 : 5 x 5의 숫자판 존재 각 칸에는 0~9까지의 숫자가 들어갈 수 있다 : 처음 칸에서 5번 더 이동 가능 (상하좌우로만) 모두 이동한 칸은 처음 칸을 포함해서 총 6칸 중복으로 이동 가능 (즉 갔던 자리 다시 갈 수 있다는 뜻) : 나올 수 있는 6칸의 숫자를 붙여서 6자리의 경우의 수를 구하여라 [입력] : 다섯 개의 줄에 다섯 개의 정수로 숫자판 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 [출력] : 경우의 수 출력 15 [문제접근] 모든 경로를 하나하나 다 파악해줘야 하기 때문에 DFS 선택! 다른 문제와 달리 방문기록을 표시하는 객체가 없다 → 해당 문제는 중복을 허용하기 때문이다 → 즉, 같은 자리를 다시 찾아갈 수 있다 다만 .. 2024. 1. 21. [백준] 1182번 부분수열의 합 JAVA (자바) 풀이 문제 1182번 : N개의 정수로 이루어진 수열 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하기 [입력] : 첫 줄에 정수 개수 N, 정수 S (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 수열이 공백으로 구분[출력] : 합이 S가 되는 부분수열 개수 출력 [과정] - [공통] 공집합일 경우를 생각해야 하므로 S = 0 이라면 -1 하고 시작한다 - 재귀적 백트래킹반복문을 쓰지 않아서 좀 더 직관적으로 코드를 간결하게 볼 수 있다dfs(next,sum); dfs(next,sum+arr[start]); 예) [3, 7, 2] / S=9 backtrack(0, 0) ├.. 2023. 11. 27. [백준] 15649번 N과 M(1) JAVA (자바) 풀이 문제 15649번 (백트래킹) : 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 골라서 수열을 모두 구하는 프로그램 (예) N = 3, M = 1 인 경우 1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다 1 / 2 / 3 이렇게 만든 수열을 한줄에 하나씩 출력한다 [입력] : 첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8)[출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X) 수열의 원소는 공백으로 구분해서 출력 : 수열은 사전 순으로 증가하는 순서로 출력 [과정] 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 문제 조건) 숫자 중복금지 → 완전 탐색이 아닌.. 2023. 11. 13. [프로그래머스] Lv.3 다단계 칫솔 판매 JAVA 풀이 문제 Lv.3 다단계 칫솔 판매 : 하위 직원이 칫솔 판매하면 10프로는 상사한테 넘긴다 (계속 반복하면서 center까지도 수익금 10% 전달) : 단 더이상 10%로 나눠지지 않는다면 되는 단계까지만 한다 - [enroll] : 모든 판매원의 이름을 담고 있는 배열 - [referral] : enroll배열과 연결된 직속 상사 "-" 표시가 있다면 제일 높은 상사 - [seller] : 판매한 직원 - [amount] : 판매한 칫솔 개수 (seller와 연결지어 보면 된다) 예시) enroll referral income john - 360 mary - 958 edward mary 108 sam edward 0 emily mary 450 jaimie mary 18 tod jaimie 180 youn.. 2023. 11. 2. 이전 1 2 3 4 다음
