동적 프로그래밍(Dynamic Programming) : 큰 문제를 작은 문제들로 나누어 해결한 후, 그 결과를 저장하여 중복 계산을 줄이는 최적화 기법• 중복 계산 감소 : 이미 계산한 결과를 저장하고, 필요할 때마다 재활용하여 중복된 계산을 피함• 점화식 : 주어진 문제의 해를 작은 문제의 해를 통해 표현하는 식• 최적 부분 구조 : 큰 문제의 최적해가 작은 문제들의 최적해를 통해 구할 수 있어야 함 완전 탐색은 다 탐색하므로 높은 시간 복잡도를 가지므로 ‘체계적’, ‘효율적’으로 탐색하기 위해서 2가지 조건이 있어야 함Overlapping Subproblems (중복 하위 문제) : 중복 계산해야하는 하위 문제가 존재Optimal Substructure (최적 부분 구조) : 하위 문제에서 구한 ..
완전탐색(Exhaustive Search)재귀를 활용한 의사결정 트리 탐색정답이 될 가능성이 있는 모든 후보(candidates)를 탬색하여 정답을 찾는 알고리즘 패러다임의사결정 트리(possibility tree) 사용의사결정 트리 : 문제를 해결하는 모든 경우의 수를 트리 형태로 나타낸 것, DFS 방식으로 탐색하면 가능한 모든 경우를 빠짐없이 확인 가능 1️⃣ 완전탐색(재귀), DFS의사결정 트리를 DFS 방식 으로 순회하는 과정이라고 할 수 있음각 단계에서 가능한 선택지를 탐색하며 하나의 경로를 끝까지 탐색한 수 원래 상태로 되돌아 가는 방식1. 모든 가능한 경우를 표현2. DFS 방식으로 탐색3. 모든 Leaf 노드까지 도달 2️⃣ Backtracking(백트래킹)완전탐색으로 순회하면서 이전 ..
🔗 길 찾기 게임import java.util.*;class Solution { private static class Node{ int x; int y; int num; Node left; Node right; Node(int x, int y, int num){ this.x=x; this.y=y; this.num=num; } } private static Node makeTree(int [][] nodeinfo){ Node[] nodes=new Node[nodeinfo.length]; for(int i=0;i{ if(..
🔗 신규 아이디 추천class Solution { public String solution(String new_id) { // 3~15자 이하 // 알파벳 소문자, 숫자, -, _, . 가능 // 7 단계 아이디 규칙 검사, 맞지 않는 경우 새로운 아이디 추천 // new_id : 신규 유저가 입력한 아이디 // 1. 대문자 -> 소문자 new_id=new_id.toLowerCase(); // 2. 가능한 문자 제외 삭제 new_id = new_id.replaceAll("[^0-9a-z._-]", ""); // 3. .연속을 . 하나로 new_id = new_id.r..
🔗 다단계 칫솔 판매import java.util.Map;import java.util.HashMap;class Solution { public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) { // 민호 : root node // 이익의 10%를 부모에게 주고 나머지는 자신이 가짐, 부모는 또 부모에게 10% 줌 // 10% 계산시 원단위 절사, 1원 미만인 경우 분배하지 않고 자신이 가짐 // enroll : 각 판매원의 이름을 담은 배열, 민호의 이름은 없음 // referral : i 번째에 있는 이름은 배열 enroll..
:link: 예상 대진표class Solution{ public int solution(int n, int a, int b) { // n : 참가자 수 // a : 참가자 번호 // b : 경쟁자 번호 // 참가자는 경쟁자와 몇 번째 라운드에서 만나는지 return // a, b 의 참가자 번호가 같아 지면 만나는 것 int answer = 0; for(; a!=b;answer++){ a=(a+1)/2; b=(b+1)/2; } return answer; }}
