강의 듣기 전, 혼자 풀어볼 때 코드를 이렇게 짰는데 이것도 맞는 풀이일까요 ...? import java.util.*; import java.io.*; /* N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. ex. 6 1 3 5 6 7 10 -> YES */ public class P01_합이같은부분집합_DFS_아마존인터뷰 { static int total; static int[] arr; static String answer; static int index; static int sum; static int N; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); arr = new int[N]; StringTokenizer st = new StringTokenizer(br.readLine()); total = 0; for (int i=0; i<N; i++) { arr[i] = Integer.parseInt(st.nextToken()); total += arr[i]; } index = 0; sum = 0; answer = "NO"; DFS(index); System.out.println(answer); } public static void DFS(int index) { if (sum*2 > total || index==N) { return; } else { sum += arr[index]; if (sum*2 == total) { answer = "YES"; return; } DFS(index+1); sum -= arr[index]; DFS(index+1); } } } 채점 사이트에서 통과하기는 하는데 이 풀이가 맞아서 통과한건지 아님 운좋게(?) 테스트 케이스 5개가 다 맞아서 통과한건지 뭔가 풀이에 대한 확신이 없어서요 .. !
안녕하세요 큰돌님. 강의 너무나도 잘 보며 공부하고 있습니다! 2-p 연구소 조합을 재귀로 작성해 보았습니다. for문으로 조합을 구하는것과 별로 다른것이 없는거 같은데 재귀로 구하니 백준 2번째 테케가 틀리게 나옵니다! 시간되실때 봐주시면 정말 감사드리겠습니다! http://boj.kr/7ee04a6b382f416abe6647adff8912c6
강사님 안녕하세요, 5-E (1931 - 회의실 배정) 문제를 저는 회의 start 시간 기준 오름차순 sort + stack 이용하여 풀어보았는데요. 제 생각에는 맞을 것 같은데 왜 틀리게 나오는지 모르겠어서요... http://boj.kr/17216518de8a498bb29034d7e4d52877 어떤 부분이 틀렸는지 봐주실 수 있을까요..
선생님 풀이에서 궁금한 부분이 있어 질문을 남기게 되었습니다. dp[1][2][0] = 1; 문제에서 (1,2)까지 가로 파이프가 있다고했습니다. 코드에서는 y,x 순으로 배열을 작성하였으므로 dp[2][1][0]=1을 초기값으로 하는것이 맞다고 생각되는데 그렇게 하면 정답이 맞지 않습니다. 저 부분에 대한 선생님 설명을 듣고싶습니다. 추가 ) x,y 순으로 배열을 작성하여 코드를 작성하였는데요, 이때에는 정답이 틀리고 이 코드에서 dp[2][1][0]=1로 초기값 설정하였을때 정답이 나오는것 같습니다. https://www.acmicpc.net/source/57275157
강사님 안녕하세요, 5-B 문제풀의 강의 5:28 부근에서 설명을 해주실 때, stk.top () 이 폭발 문자열 첫번째 문자열과 같은 경우 를 예를 들며 stk.top () 이 문자 "C" 가 검출되었을때 조건문이하가 실행되는 것으로 말씀해주셨는데요 if(stk.size() >= T.size() && stk.top () == T[T.size() - 1]) 조건문 에서 stk.top () 의 문자가 폭발 문자열의 마지막 문자로 검출되었을때 if 조건문 참이 되어서 실행이 되는 것으로 이해했고 그게 맞는 것 같은데 해당 부분 설명하시는 부분에 수정이 필요할 것 같습니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 설명 하실떄 사용하는 파이썬 프로그램 명은 어떤건 가요? 저는 파이참을 사용중인데 하나씩 재생하는데? 조금 불편함이있어 노씨님 프로그램으로 사용해보고 싶어 문의 드립니다.
function solution(n, m) { let answer = []; let tmp = Array.from({ len function DFS(L, s) { if (L === m) { answer.push(tmp.slice( } else { for (let i = s; i <= n tmp[L] = i; console.log(tmp); DFS(L + 1, s + tmp[L]); } } } DFS(0, 1); return answer; } console.log(solution(4, 2)); 강사님 저는 강의 보기전에 i + 1이 아닌 s + tmp[L]로 하니까 정답이 나오더라구요, 이렇게 해도 문제가 없 는 코드인가요?
안녕하세요 강사님! 강의 너무 잘 듣고 있습니다! 다름이 아니라 채점프로그램을 실행하면 위와 같은 오류가 발생하는데 원인을 모르겠습니다.. 파이썬도 ORG에서 최신버전으로 PATH와 설정 체크까지 해서 설치하였고 해당 폴더에 AA.py로 만들고 프로그램을 실행시켜도 위와 같은 오류가 발생합니다..ㅠㅠ 해결방법이 있을까요? k번째 큰 수 문제 코드입니다! import sys sys.stdin=open("input.txt", "rt") n, k = map(int,input().split()) a = list(map(int,input().split())) res=set() # set()=> 같은 값을 여러번 넣어도 한번만 들어감. for i in range(n): for j in range(i+1,n): for m in range(j+1, n): res.add(a[i]+a[j]+a[m]) res=list(res) res.sort(reverse=True) # 내림차순 print(res[k-1])
def LCA(root, p, q): if root == None: return None left = LCA(root.left, p, q) right = LCA(root.right, p, q) if root == p or root == 1: return root elif left and right: return root return left or right https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/ 이 문제 질문드립니다. 맨 밑에 코드가 이해가 안가서 질문드려요 root가 q 이거나 p 이면 root를 반환하는 것 까지 이해했습니다. elif left and right: return root return left or right 저 부분이 잘 이해가 안됩니다 elif left and right 의 의미가 left 랑 right 둘다 존재하면 root를 반환하라는 의미인가요? 그게 아니면 left 아니면 right 중 둘 중 하나 존재하는 것을 리턴하라는 의미구요 저는 자바로 하고있는데 저부분이 이해가 안가서 질문드립니다..!
function solution(k, nums, m) { const isMulti = (n, m) => { if (!(n % m)) return 1; return 0; }; let ans = 0; function DFS(L, sp, sum) { if (L === k) { console.log(L, tmp, sp, sum); if (isMulti(sum, m)) ans++; } else { for (let i = sp; i < nums.length; i++) { DFS(L + 1, i + 1, sum + nums[i]); } } } DFS(0, 0, 0); return ans; } 해당 문제 시간복잡도가 궁금하여 질문드립니다. 해당 문제를 선생님과 똑같이 풀이했는데요, DFS 내부 for문의 i시작점이 동적으로 변하다보니 시간복잡도를 어떻게 잡아야 할지 몰라 헷갈려 질문드려요. 만일 for문의 i의 시작점이 고정적으로 0이라면 O(N^K)가 될 것 같은데, 이처럼 i가 유동적으로 변하는 것으로 기존 빅오 표기에 영향이 갈만큼 차이가 발생하게 되나요? 시간내어 확인해주셔서 감사합니다.
안녕하세요 큰돌님 알고리즘 강의를 보며 많은 도움을 받고있습니다! 해당 강의 보면서 조건들을 잘 맞추고 출력형식도 잘 했다고 생각했는데 제출하면 오답이네요ㅠㅜ 틀린 내용을 잘 못찾겠어서 질문드립니다! 시간되실때 한번 봐주실 수 있으신가요? http://boj.kr/ac9ebe891d7c4734a5f01e78a1e2d13d
function solution(coins, m) { coins.sort((a, b) => b - a); let ans = 0; function DFS(L, sum) { if (sum > m) { return; } if (sum === m) { ans = L; return "end"; } else { for (let i = 0; i < coins.length; i++) { if (DFS(L + 1, sum + coins[i]) === "end") return "end"; } } } DFS(0, 0); return ans; } 동전 교환 문제에서 강사님께서 가르쳐주신 코드도 실습해 본 후, 제 나름대로 작성해본 코드입니다. 제 얕은 생각으로는 위 코드처럼 가장 먼저 동전 종류를 내림차순으로 정렬한 후, DFS를 가지쳐 내려나간다면, 가장 큰 단위부터 적용해나가므로 맨 처음 종료조건에 도달해 ans에 대입되는 값이 무조건 최소동전 개수가 되지 않을까 생각해서 이렇게 작성했습니다. 이 풀이가 틀린지 궁금하고, 만일 맞다면 시간복잡도 상 효율이 극단적으로 떨어지는 최악의 경우가 존재할 지 또한 궁금합니다. 귀한 시간 내어 읽어주셔서 감사합니다.
