코딩테스트, 초급, Subsets

유료강의: / @코드없는프로그래밍
챕터리스트: • 코딩테스트 BackTracking
code: colab.research...
주어진 배열의 모든 subset들을 구하라
예제: [a,b,c]
정답 : [ [], [a], [b], [c], [ab], [ac], [bc], [abc]]

[@김기찬-v9f]

지식 공유 해주셔서 감사합니다 설명을 참 잘하세요

[@코드없는프로그래밍]

감사합니다. 채널 및 플레이리스트에 더 많은 내용있습니다.

[@eezz_]

재귀 문제는 너무 어렵네요.. 많이 배워서 감사드리고, 두 가지 질문이 있습니다. 1번 질문은 BackTrace를 구현하는 방식이 Recursion이라고는 알겠는데,,, 그냥 "재귀 함수로 작성한다"와 무슨 특별한 차이가 있는지 개념이 잘 잡히지 않습니다. ( Leetcode Example에 따른 답변 순서는 아래 JAVA 코드로 첨부했습니다. 그런데 "???" 주석 친 부분처럼.. 애매한 부분이 있다보니 문제가 있는지 궁금합니다.) 2번 질문은 재귀함수를 이용하면 메모리 Stack Overflow가 발생할 수 있으니, 자료구조 Stack을 사용하여 Heap Memory 이용 방식으로 바꾸는 것 같은데.. 정확한 장,단점이 무엇인가요? 메모리 부족으로 할당 실패가 발생하면 예외 처리가 가능하다는 장점 하나 라고 추측하는데 더 있을까요..? ---------------------- class Solution { List mList; int[] mNums; private void BT(int a_nIndex, LinkedList a_pIntList) { if (a_nIndex == -1) { mList.add(a_pIntList); return; } BT(a_nIndex - 1, a_pIntList); LinkedList cloneList = (LinkedList) a_pIntList.clone(); cloneList.addFirst(mNums[a_nIndex]); BT(a_nIndex - 1, cloneList); } public List subsets(int[] nums) { mNums = nums; mList = new LinkedList(); mList.add(new LinkedList()); //??? for (int i = 0; i < nums.length; i++) { LinkedList pIntList = new LinkedList(); pIntList.add(mNums[i]); BT(i - 1, pIntList); } return mList; } }

[@코드없는프로그래밍]

안녕하세요. 어떤 문제들은 recursive approach가 더 쉽고, 어떤 문제들은 iterative methods들이 더 쉽습니다. 1. Backtracking같은 경우는 각 단계에서 새로운 decision space가 생성이되고(candidates라고도 말합니다) 그 space를 탐색하는 원리로 작동이 됩니다. 그중에 candidates들이 reject이 되면 그 path는 탐색을 그만두는 것이구요. 이러한 접근방법은 recursion으로 표현하는것이 직관적이기 때문에 recursion을 사용하는 것 뿐입니다. 2. Recursion은 매번 함수를 호출하고 stack frame을 쌓아가야 하기 때문에 그 동작이 느릴수밖에 없습니다. 또한 stack frame limit은 프로세스가 가져갈수있는 전체 메모리에 비해서 작기때문에 overflow가 날 가능성이 높습니다. iterative한 방법을 사용하게 되면 많은 양의 memory확보가 가능한점, 그리고 data들이 붙어있기때문에 프로그램의 동작 속도가 더 빠릅니다. overflow에 대해서 더 안정적이기도 합니다. 하지만 코딩테스트에서 recursion이 생각하기 편하면 그냥 recursion으로 풀면됩니다. 지금 풀고있는 backtracking이 그런 경우겠죠. 인터뷰어가 recursion으로 코딩을 하게되면, recursion - iteration 을 자유자재로 할 수있는지를 보기 위해 물어보는 경우가 있습니다. 인터뷰가 아닌 실제업무에서는 iteration을 주로 사용하면됩니다. 가끔, recursive function call을 하는 경우가 있는데 두가지 조건 (1. recursion으로 쓸때 함수가 훨씬 간단해지는 경우 , 2. recursion depth가 어떠한경우에도 깊지 않다 라는것이 확실시 될 경우) 이 두가지가 모두 해당이 되는 경우에만 recursion 을 사용하게 됩니다.

[@eezz_]

@@코드없는프로그래밍 자세한 답변 감사드립니다.

[@eezz_]

복습 하니 더 보기 쉽게 작성할 수 있었네요..( 수정 ) BT_() 시간 복잡도 정리 중 영상 다시 확인하니 다르게 작성하고 있어서, 재 첨부합니다. ㅜ; class Solution { List mRet; int[] mNums; -> 0ms private void BT(int a_nIndex, ArrayList pList) { if (a_nIndex == mNums.length) { mRet.add(new ArrayList(pList)); // O(n) return; } BT(a_nIndex + 1, pList); pList.add(mNums[a_nIndex]); BT(a_nIndex + 1, pList); pList.remove(pList.size() - 1); } -> 1ms private void BT____(int a_nIndex, ArrayList pList) { mRet.add(new ArrayList(pList)); for (int i = a_nIndex; i < mNums.length; i++) { pList.add(mNums[i]); BT____(i + 1, pList); pList.remove(pList.size() - 1); } } public List subsets(int[] nums) { mNums = nums; mRet = new ArrayList(); BT(0, new ArrayList()); //BT____(0, new ArrayList()); return mRet; } }

[@loganj6203]

지금 저의 머리로는 BT이 이해가 잘 되질 않네요. 왜 이걸 이렇게 해야되지 이런 의문도 좀 드네요. 혹시 쉽게 참고할만한 자료가 있을까요? 아니면 그냥 풀다보면 익숙해지려나요.

[@코드없는프로그래밍]

Implementation 에대해 어려운 영상이긴합니다. 아마 챕터 다른 영상들을 보시면 이해가 되실겁니다. 감사합니다

[@user-em3yh4xf1p]

영상 잘 봤습니다!! 파이썬으로 코드를 짰는데, 질문이 있습니다. 1. 아래코드 10번째 줄에서 letters + [c]를 해서 BT함수를 재귀적으로 돌리면 Accepted가 뜨는데, 처음에 letters.append(c)로 짰더니 NoneType에 append를 할 수 없다고 에러가 뜨네요. 무슨 차이인가요? -------------------------------------------------- class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: dab = [] def BT(index, letters): if index == len(nums): dab.append(letters) return c = nums[index] BT(index + 1, letters + [c]) BT(index + 1, letters) BT(0, []) return dab ------------------------------------------------------------- 2. 위에 letters.append(c)로 해서 에러가 떠서 아래와 같이 letters에 append(c)를 한뒤 letters를 넘기고 빠져나올 때 letters.pop을 해줬습니다 종료조건인 if index == len(nums)에 잘 들어와서 dab에 letters가 append되는 것 까지 확인했는데, 최종 출력값에는 빈 배열인 [ [ ], [ ], [ ], [ ], [ ], [ ], [ ] ] 이런식으로 출력이 되네요. 왜 if안에서는 dab에 append가 되었는데, if를 빠져나오면서 dab이 초기화되는 것인가요? class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: dab = [] def BT(index, letters): if index == len(nums): dab.append(letters) return c = nums[index] letters.append(c) BT(index + 1, letters) letters.pop() BT(index + 1, letters) BT(0, []) return dab

[@코드없는프로그래밍]

첫번째 문제는 append도 되야합니다. 영상 아래 colab link를 확인하시면 append 활용하여 implementation된 것 확인할수있습니다. 두번째는 파이썬에서 list는 ref로 동작하기때문에 최종 리스트에 deep copy를 해주어야 합니다. 역시나 영상아래 implementation에서 확인가능합니다.

[@user-em3yh4xf1p]

@@코드없는프로그래밍 아 ref로 동작하기때문에 copy를 해줘야 되는군요. 감사합니다 코드를 봤는데 from typing import List를 하신 이유와 BT함수를 이름지을때 앞에 _언더바를 붙인 이유도 궁금합니다

[@코드없는프로그래밍]

Type list는 제가 C++ 백그라운드를 가지고 있기때문에 타입체킹이 더 편해서 사용하였습니다. 언더바 같은경우는 private member function처럼 읽으라고 사용하였습니다. 물론 파이썬에는 그런기능은 없지만 그냥 코딩스타일일뿐입니다

[@user-em3yh4xf1p]

@@코드없는프로그래밍 아 감사합니다!! 좋은 하루되세요!