백트래킹

📖 문제  16637번: 괄호 추가하기첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가www.acmicpc.net 💡  풀이 방식• DFS + 백트래킹1. 이전 연산 결과 순차적으로 계산2. 이전 연산 결과 오른쪽의 2개의 값을 괄호로 처리해 계산하고, 이전 연산 결과와 합침 DFS 통해 맨 뒤에서부터 괄호를 묶을 수 있는 경우 묶으면서 연속적으로 계산연산자 인덱스 기준 접근 - 숫자 리스트와 연산자 리스트를 따로 두어야 한다.  🔺 코드12345678910111213141516171819202122232425262728293031323334353..

🔺 문제 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 🧩 해결 아이디어 • 문자열 + 스택 + 재귀 - 필요 자료구조 (여는 괄호 위치, 닫는 괄호 위치) 저장 객체 괄호 위치 객체 저장 리스트 괄호 제거해서 나오는 식 저장할 TreeSet 괄호 지울지 말지 판단용 boolean 배열 - 여는 괄호인 경우, 스택에 시작 위치 인덱스를 넣는다. - 닫는 괄호인 경우, (스택의 여는 괄호 인덱스, 현재 인덱스)를 넣는다. - 재귀를 통해 괄호를 표시할지 말지 각 쌍들을 조합하여..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🧩 해결 아이디어 • 백트래킹 (조합) . 필요 자료구조 ┕ 격자 저장할 2차원 int형 배열 ┕ 중복 방지용 boolean형 배열 ┕ 조합 숫자들 저장용 int형 리스트 (열 저장) . 시간 복잡도 : O(N! * N) - 2차원 배열에 값을 입력받는다. - 1부터 N행까지 돌며 어떤 열을 색칠할지 N개의 값을 뽑아 조합을 생성한다. - 해당 조합에 있는 숫자들 중 최솟값을 구하고, 이 최솟값을 현재 최댓값과 비교해 갱신한다. 💥 유의사항 각 행과 열에 1개의 색칠된 칸만 오게 한다고 하였으므..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🧩 해결 아이디어 • 백트래킹 (순열) - 가능한 모든 순열 거꾸로 탐색 (큰 수부터 거꾸로 백트래킹 진행) - 시간 복잡도 : O(N! *N) 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 import java.util.*; import java.io.*; public class Main { static..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🧩 해결 아이디어 • 백트래킹 (순열) - 방문 배열 : 중복 방지용 - 앞에서부터 원소 선택하고, 선택하지 않은 원소들 중 가장 앞에 있는 원소들 선택 - N개 모두 뽑았을 때, 해당 순열 출력 - 시간 복잡도 : O(N! * N) 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 im..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🧩 해결 아이디어 • 백트래킹 1. N개 중 M개를 뽑는 가능한 모든 조합을 만든다. 2. 해당 조합에 대해 XOR 연산을 수행하고, 이 중 최댓값을 구한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 import java.util.*; import java.io.*; ..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🧩 해결 아이디어 • 백트래킹 (조합) - 마지막으로 뽑힌 숫자와 지금까지 뽑은 갯수를 값으로 가져가서 뽑을 수 있는 원소 후보들을 탐색한다. - 시간 복잡도: O(M) 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import java.util.*; import java.io.*; public class Main ..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import java.util.*; import java.io.*; public class Main { static int K, N; static int[] arr, result; static StringBuilder sb = new StringBuilder(); public static void ma..

🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import java.util.*; class Solution { static String begin, target; static String[] words; static boolean[] visited; static int answer = 0; public int solut..