비전공자 출신으로서 대기업 준비 과정을 공유합니다. 기본문제 : www.acmicpc.net/problem/15649 코드 : github.com/ChangguHan/codingt... 00:15 개념 00:36 기본 문제 10:45 라이브 코딩 19:40 백트래킹 Tip #백트래킹 #코딩테스트 #알고리즘 #비전공자 #개발자
안녕하세요 강의 잘 봤습니다. 백트래킹 자바로 해당 문제 풀고 있는데요. 마지막에 rs.pop() 해주는 부분을 값 담아두는 배열 number[depth] = 0; 이런식으로 처리를 해줬는데, 이부분 굳이 안쓰고 chk[i] = False 쪽만 해줘도 되지 않나요? 오히려 속도는 rs.pop() 부분을 안해주는게 더 빠른거 같아서요.
써멀님 안녕하세요! number[depth]=0; 이 어떤 맥락에서 들어갔는지 잘 모르겠지만, 제 코드스타일을 꼭 따라할 필요는 없고, 자기만의 방법을 찾는게 중요합니다 말씀하신것처럼 제 코드에서 chk[i] = False 만하고, rs.pop()하지 않는다면? 돌려보시면 알겠지만 풀리지 않을껍니다. rs에는 현재 백트래킹 단계에서 가지고 있는 숫자가 담겨있어야해요
@@developer_jango 답변 정말 감사합니다 ! 제가 java 로 아래처럼 짰는데, 메인메서드랑 재귀메서드가 아래와 같습니다. 저 상황에서는 배열의 끝값을 pop() 처리 안해주고 그냥 bool 배열만 false 처리 해줬거든요. 혹시 돌고있는 for문의 인덱스가 달라서 굳이 pop 처리를 안해줘도 되는걸까요 ? 괜찮이시다면 답변 부탁드리겠습니다 ! public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); // 1부터 n 까지의 자연수 중에서 m = Integer.parseInt(st.nextToken()); // '중복없이' m개 고르는 문제 number = new int[m + 1]; visited = new boolean[n + 1]; recursive(0); } public static void recursive(int depth) { if (depth == m) { for (int i = 0; i < m; i++) { System.out.print(number[i] + " "); } System.out.println(); return; } for (int i = 0; i < n; i++) { //(자연수 0+1 부터 (n-1)+1 까지) if (!visited[i]) { number[depth] = i + 1; visited[i] = true; // 중복없이 m개를 골라야하니까. recursive(depth + 1); visited[i] = false; // rs.pop() 같은 처리 필요 없나? } } }
잘 보고 있습니다~ㅎㅎ
백트래킹 비디오들 보면서 돌다가 이강의가 가장 이해하기 좋네요. 너무 감사합니다~~
이번영상도 너무너무 유익합니다! 재능나눔 감사드려요
백트래킹 강의 중 가장 이해 잘 됐습니다
감사합니당
와 진짜 감격스럽네요 설명을 너무 잘해주셔서 저 같은 비전공자도 이해가 쏙쏙되네요
감사합니다 너무 이해 잘되게 설명해주시네요..!
잘 봤습니다! 어려운 부분이라서 여러개 찾아듣는데 이해시켜주셔서 감사합니다
감사합니다!! 히파님 홧팅!
와.. 지금까지 순열 알고리즘 코드를 이해하지 못했었는데, 영상보고 이해하고갑니다! 자세하게 설명해주셔서 감사드립니다!!
이해가 잘 되네요! 백트랙킹은 응용하면 어려워지던데 기초부터해서 풀어야겠어요.
안녕하세요! 좋은 강의 갑사합니다! 한가지 질문이 있는데, recur(num+1)이 호출되면 그 아래 코드는 실행이 안되는거 아닌가요?? 이해가 잘 안되네요 ㅠㅠ
백트래킹은 여태까지 여러 강의 봤지만 장고님이 제일 설명 잘 함.
코딩테스트 준비중인데 개념적인게 부족해서 유튜브 찾다가 강의중에 제일 잘 설명해주시는것같아서 보고있습니다 ㅠㅠ 나중에 책도 써주세요 ㅠㅠ
멋진 영상 잘 봤습니다. 감사합니다 :)
지금까지 본 재귀함수 관련 강의 중 가장 이해가 잘됩니다. 너무 깔끔하게 정리 잘해주셔서 눈물이 날 것만 같은... 감사합니다!
극찬 감덩ㅠ, 저도 눈물이 날것만 같은...
감사합니다!
저두 감사합니당 ㅎㅎ
장고님... 백트래킹 이해가 안되서 대부분 백트래킹 문제를 permutation으로 풀다가... 한계에 부딛혔습니다. 장고님 덕에 오늘 그 한계를 깼습니다...!
잘봤습니다
중복이 안된다고 했는데 [1,2]와 [2,1]은 다른 걸로 보는 건가요?
코데 준비중에 올려주신 강의들 잘 보고 있습니다 ㅎㅎ 질문이 있는데요. 시간복잡도가 대충 2억이 넘지 않아야 한다는건 해당 백준문제의 조건인건가요?
프로그래머스 등에서는 문제 설명에서 시간 제한 같은게 안나와 있고 코드를 돌려봐야 알 수 있는데 문제 풀이 설계과정에서 어떻게 접근하면 좋을지 팁 올려주시면 정말 감사하겠습니다..!! 영상 정말 도움 많이되고 있습니다. 올려주셔서 감사합니다
프로그래머스는 보통 1~2초라고 보시고 문제 푸시면 돼요!
안녕하세요 강의 잘 봤습니다. 백트래킹 자바로 해당 문제 풀고 있는데요.
마지막에 rs.pop() 해주는 부분을 값 담아두는 배열 number[depth] = 0; 이런식으로 처리를 해줬는데,
이부분 굳이 안쓰고 chk[i] = False 쪽만 해줘도 되지 않나요?
오히려 속도는 rs.pop() 부분을 안해주는게 더 빠른거 같아서요.
써멀님 안녕하세요!
number[depth]=0; 이 어떤 맥락에서 들어갔는지 잘 모르겠지만,
제 코드스타일을 꼭 따라할 필요는 없고,
자기만의 방법을 찾는게 중요합니다
말씀하신것처럼 제 코드에서
chk[i] = False 만하고,
rs.pop()하지 않는다면?
돌려보시면 알겠지만 풀리지 않을껍니다.
rs에는 현재 백트래킹 단계에서 가지고 있는 숫자가 담겨있어야해요
@@developer_jango 답변 정말 감사합니다 ! 제가 java 로 아래처럼 짰는데, 메인메서드랑 재귀메서드가 아래와 같습니다.
저 상황에서는 배열의 끝값을 pop() 처리 안해주고 그냥 bool 배열만 false 처리 해줬거든요.
혹시 돌고있는 for문의 인덱스가 달라서 굳이 pop 처리를 안해줘도 되는걸까요 ? 괜찮이시다면 답변 부탁드리겠습니다 !
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 1부터 n 까지의 자연수 중에서
m = Integer.parseInt(st.nextToken()); // '중복없이' m개 고르는 문제
number = new int[m + 1];
visited = new boolean[n + 1];
recursive(0);
}
public static void recursive(int depth) {
if (depth == m) {
for (int i = 0; i < m; i++) {
System.out.print(number[i] + " ");
}
System.out.println();
return;
}
for (int i = 0; i < n; i++) { //(자연수 0+1 부터 (n-1)+1 까지)
if (!visited[i]) {
number[depth] = i + 1;
visited[i] = true; // 중복없이 m개를 골라야하니까.
recursive(depth + 1);
visited[i] = false;
// rs.pop() 같은 처리 필요 없나?
}
}
}
백트레킹.. 하.. 백트레킹이 구현된 재귀함수가 이해가 안됩니다.. 어떻게 돌아가는지 종이에 for문 하나하나 써봐도 도통 이해가 되질않습니다.. 어떻게 해야하나요? 대~~~충은 이렇게 돌아가게꺼니 막연하게는 알겠는데, 직접 구현하라고하면 못할거 같습니다... 어떻게 이걸 이해 해야할까요?
백트래킹이 처음에 이해하기가 어렵죠 ㅠ
이해는 트리구조를 그려보면서 따라가보면 좀 도움이 될것같고, 구현하는것은 기본구조는 외워주셔야돼요
백트래킹관련 문제중 접근방법이 대해 조언을 얻고싶습니다. 혹시 메일이나 메신저로 문제 공유드려도 괜찮을까요
잘봤습니다
어이쿠,, 하루에 세개나!!!
원장님 너무 열심히하시는거 아닌가요?
@@developer_jango 설명을 잘 해주셔서 내용이 잘 들어옵니다. 그래서 3개나 본 것 같습니다 ㅋㅋ 양질의 강의라 댓글이랑 좋아요는 하는게 양심에 맞는 것 같아서 ㅋㅋㅋㅋㅋ
@원장 감사합니다 ㅎㅎㅎ
우리 같이 열심히해서 좋은결과 만들어봐요!!