🔎 문제
🧩 구현과정 및 코드
개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.
사용할 데이터 구조와 풀이 방향성
적용할 알고리즘 혹은 메서드
수영
구현
- [1,1,1,1,1]로 노트에 적었을 때 모두 양수, 1개 음수, 2개 음수,,, n개 음수 모든 경우의 수를 구해야 한다는 생각이 들었다. → DFS, 스택으로 접근
- DFS를 재귀로 푸는 방법이 가독성이 좋았다.
코드
function solution(numbers, target) { let answer = 0; dfs(0, 0); // 재귀함수를 이용한 DFS function dfs(index, sum) { if(index === numbers.length) { if(sum === target) { answer++; } return; } dfs(index + 1, sum + numbers[index]); dfs(index + 1, sum - numbers[index]); } return answer; }
정은
구현
- dfs 용 중첩함수를 만듦
- 매개변수 : 배열, 결과값
- [결과값+0번째 인덱스 값]과 [0번째를 없앤 배열]로 dfs 함수 재귀호출
- b가 끝나면 [결과값-0번째 인덱스 값]과 [0번째를 없앤 배열]로 dfs 함수 재귀호출
- (마지막 turn) 빈 배열이 되면 결과 값을 target과 비교, 같으면 answer++
- 제일 시작은 초기 배열 numbers와 초기 결과값 0으로 시작
코드
function solution(numbers, target) { var answer = 0; function dfs(arr,result) { if (arr.length <= 0) { if (result === target) { answer++; } return; } dfs(arr.slice(1),result+arr[0]); dfs(arr.slice(1),result-arr[0]); } dfs(numbers,0); return answer; }
종혁
구현
numbers배열의 모든 수를 다 계산해봐야 답이 나올 것 같다는 생각이 들었고,numbers의 또한 길이가 최대 20이어서 모든 경우의 수를 다 따져보기로 함
dfs를 통해numbers[count]가 [-1,1]을 한번씩 가진 경우를 구하고, 결과값을 acc에 저장하여dfs(count+1,acc+numbers[count])로 다음 원소를 살펴보고, 모든 배열을 다 돌았을 때(count가length와 같아졌을 때)acc === target인지 체크- [-1,1]이라는 배열을 사용하지 않아도
acc-numbers[count]acc+numbers[count]처럼acc에서 현재 원소를-하는 경우/+하는 경우로 나눠서도 가능
코드
function solution(numbers, target) { //음이 아닌 정수 n개 //입력값이 매우 작음 - numbers.length가 최대 20 //각 수가 +를 가지냐 or -를 가져야되냐 let result = 0 function dfs(count,acc){ if(count >= numbers.length){ if(acc === target){ result ++ } return} dfs(count+1,acc+numbers[count]) dfs(count+1,acc-numbers[count]) // 1+1+1+1+1 // - 리턴 후 1+1+1+1-1 .... 이런식 } dfs(0,0) return result }
재웅
구현
- 모든 경우의 수를 계산해야 하니 백트래킹이라고 볼 수 있지만, 가지치기를 어떻게 해야할지는 감이 잡히지 않았음.
- 재귀를 통해 어렵지 않게 구현할 수 있지만, 자바스크립트에서는 재귀 성능이 좋지 않기 때문에 스택으로 구현해보았음.
- 2번 테스트케이스가 100ms까지 소요되었는데, 연산량이 그리 많지 않아 재귀보다 나은지는 잘 모르겠음.
코드
function solution(numbers, target) { let count = 0 const stack = [[numbers[0],0],[-numbers[0], 0]] while(stack.length>0){ let [currentValue,currentIdx] = stack.pop() const nextIdx = currentIdx+1 if(currentIdx===numbers.length-1 && currentValue===target){ count++ }else if(currentIdx<numbers.length-1){ stack.push([currentValue+numbers[nextIdx],currentIdx+1]) stack.push([currentValue-numbers[nextIdx],currentIdx+1]) } } return count }
✏️ 후기
문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.
수영
- 재귀 문제를 더 풀어봐야겠다.
정은
- 배열 대신에 인덱스를 넘겨주는 방식도 존재했다.
- bfs는 어떻게 구현하는지 궁금해서, 한번 풀어보고 싶다.
종혁
- 각 원소들이 카드 두개 중 하나를 선택하는 모든 경우를 구하는데, 그 카드의 값이 -1 또는 1 인 경우라고 생각하니 쉽게 풀렸던것같다
재웅
- 스택으로 구현해봤는데, 연산량이 그리 많지 않아 재귀보다 나은지 잘 모르겠다.