📌 04 - 부분집합 구하기(DFS) 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 문제이다. 첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래의 출력예제와 같은 순서로 출력해야 한다. 단, 공집합은 출력하지 않는다. 입력예제 3 출력예제 1 2 3 1 2 1 3 1 2 3 2 3 부분집합의 개수는 2^N 이지만 공집합은 출력하지 않으므로 -1을 해준다. N이 3이면 출력해야하는 부분집합의 개수는 7개가 된다. 재귀함수를 이용해 부분집합을 찾아갈 때 다음과 같이 그림을 그리면서 이해를 하면 도움이 된다. 📝 소스 코드 function solution(n) { let answer = []; let ch = Array.from({ length: n + 1 }, () => 0..

📌 03 - 이진트리 순회(깊이우선탐색) 이진트리 순회를 연습해보는 문제이다. 처음 나온 개념이기에 먼저 개념 정리를 할 필요가 있다. 이진트리에 대해서 먼저 알아보자❗ 나무를 뒤집어 놓은 모양과 같으며 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 다음 그림과 같다. 이진트리를 순회하는 방법에는 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)의 3가지가 있는데, 이는 부모 노드를 기준으로 하고 있다. 전위순회(preorder)는 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순서로 탐색한다. 위 사진의 순회 결과는 1 2 4 5 3 6 7이다. 중위순회(inorder)는 왼쪽 자식..

📌 02 - 재귀함수를 이용한 이진수 출력 10진수 N이 입력되면 2진수로 변환하여 출력하는 문제이다. 단, 재귀함수를 이용해서 출력해야 한다. 이진수를 구하는 과정 1단계: 변환하려는 수를 2로 나눈 후 몫과 나머지 기록 2단계: 1단계에서 계산한 몫을 2로 나눈 후 몫과 나머지 기록, ...몫이 0이 될 때까지 반복 기록한 나머지 값을 아래에서 위로 읽으면 2진법으로 변환 완료 👍 풀이 방법 이진수를 구하는 과정을 보면 기록한 나머지 값을 아래에서 위로 읽어야(LIFO 구조) 2진법으로 변환할 수 있다는 것을 알 수 있다. 이는 재귀함수를 사용하여 문제 해결이 가능하다는 것이다. (참고) 재귀함수 알고리즘 몫(L)이 0이 될 때까지 계속하여 DFS() 함수를 호출하는데 인자는 2로 나눈 몫(정수)을 ..

📌 01 - 재귀함수 자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 문제이다. 👍 풀이 방법 스택 프레임(Stack Frame)에 대한 내용을 알고 있으면 재귀함수를 이해하는데 있어서 도움이 된다. 해당 내용은 다음 스택 프레임(Stack Frame)은 무엇인가? 라는 글에 따로 정리하였다. solution 함수 내부에서 DFS(n)를 호출하면 해당 함수의 매개 변수, 반환 주소값. 지역 변수 등의 스택 프레임이 스택에 저장된다. L이 0이 될 때까지 계속해서 DFS(L - 1) 함수를 호출하면서 해당 함수의 스택 프레임이 추가로 스택에 저장된다. L이 0과 같으면 return하고 스택에 저장된 함수를 차례대로 호출하여 console.log를 실행하고 종료한다. 함수의 호출이 종료되면..

📌 스택 프레임(Stack Frame) 메모리 스택(Stack) 영역은 함수의 호출과 관계되는 지역변수와 매개변수, 반환 주소 값이 저장되는 영역이다. 스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다. 함수가 호출되면 스택에는 함수의 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소 값, 함수에서 선언된 지역변수 등이 저장된다. 그래서 스택 프레임이 뭔데❓❓ 이렇게 스택 영역에 차례대로 저장되는 함수의 호출 정보를 스택 프레임이라고 한다. 이러한 스택 프레임 덕분에 함수의 호출이 모두 끝난뒤에 해당 함수가 호출되기 이전 상태로 되돌아갈 수 있다. 스택 프레임(Stack Frame) 동작 방식 ex) 재귀함수 function solution(n) { function DFS(L) { i..

📌 12 - 마구간 정하기(결정 알고리즘) N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, ..., xN의 좌표를 가지며, 마구간간에 좌표과 중복되는 일은 없습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력해보자! 입력설명 첫 줄에 자연수 N과 C가 공백을 사이에 두고 주어진다. 둘째 줄에 마구간의 좌표가 차례로 주어진다. 출력설명 첫 줄에 가장 가까운 두 말의 최대 거리를 출력한다. 입력예제 5 3 1 2 8 4 9 출력예제 3 👍 풀이 방법 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 구하는 문제..

📌 11 - 뮤직 비디오(결정 알고리즘) DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 즉 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한, 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. M개의 DVD에 모든 동영상을 녹화하기로 했다. 이 때 DVD의 크기를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다. 위 문제를 정리해보면 M개의 같은 크기를 가지고 있는 DVD에 음악을 담아야 하는데, 그 크기가 가장 최소가 되는 값을 찾는 문제이다. 특정한 상황에서 최적의 값을 구해야 하므로 이분 탐..

📌 10 - 이분 검색 임의의 N개의 숫자가 입력으로 주어진다. N개의 수를 오름차순으로 정렬한 다음 N개의 수중 한 개의 수인 target이 주어지면 이분 검색으로 target이 정렬된 상태에서 몇 번째에 있는지 구하는 문제이다. 단, 중복값은 존재하지 않는다. 이분 검색 알고리즘이란❓ 정렬된 배열에서 특정한 값의 위치를 찾는 알고리즘이다. 이분 검색 알고리즘의 시간 복잡도는 O(logN)으로 순차 검색의 시간 복잡도 O(N)에 비하면 상대적으로 빠른 검색 알고리즘에 속한다. 다음 풀이 방법을 보면 그 이유를 알 수 있을 것이다. 풀이 방법 배열을 정렬한다. 이분 검색 알고리즘에서 가장 중요한 부분이다. 배열의 처음(start)과 끝(end)의 인덱스를 더한 후 2로 나누어 배열의 중간 인덱스(mid)..