5-S 질문있습니다!
233
작성한 질문수 2
안녕하세요 큰돌 강사님 코드에 대해 질문있습니다
공유 코드입니다
http://boj.kr/6afa87cbba6042c59e5314d9cd919887
문자형 백터에 연산자를 모두 넣고 연산자 인덱스를 백트레킹하여 순열을 구한 뒤 백터에 대입해서 풀었습니다.
해설에 있는 코드와 실행시간 차이가 꽤 많이 나는데 두 코드가 어떤 부분에서 효율성의 차이가 나는지 궁금하여 질문 남깁니다.
답변 1
0
안녕하세요 jin님 ㅎㅎ
이 코드는 백트래킹이라고 볼 수가 없습니다.
왜냐하면 휴리스틱으로 어떤 부분의 경우의 수를 제외한다는게 없는것 같아서 그렇습니다.
사실 이 문제는 백트래킹으로 풀 수 없는문제고 제 코드 또한 백트래킹으로 풀지 않았습니다.
if(plus) go(index + 1, cur + a[index + 1], plus - 1, minus, mul, div);
if(minus) go(index + 1, cur - a[index + 1], plus, minus - 1, mul, div);
if(mul) go(index + 1, cur * a[index + 1], plus, minus, mul - 1, div);
if(div) go(index + 1, cur / a[index + 1], plus, minus, mul, div - 1);앞의 코드처럼 모든 경우의 수를 탐색하죠? 완탐입니다. :)
자 그러면 jin님의 코드를 볼까요?
for (int i = 0; i < N-1; i++) { // operate
if (visited[i])continue;
visited[i] = 1;
_index.push_back(i);
dfs();제 생각에는 앞의 코드는 0, 1, 2 / 0, 1, 3 모든 경우의 수를 탐색해 나가기 위해 구축하신 거 같은데 저부분의 비효율성이 큽니다. 계속해서 0부터 n - 1까지 탐색을 하고 있습니다. continue를 하고 있지만 저 부분은 O(N - 1)의 코드입니다.
제 생각에는 jin님이 담아놓은 v를 기반으로
구축을 한다고 했을 때 v안에 + - *가 있다고 가정하면 총 6가지 순열의 수가 나오죠?
그렇다면 이런식으로 할게 아니라 차라리
```
do
while next_permutation
을 기반으로 하는게 나아보입니다.
또한
if (_index.size() == N - 1) {
int result = arr[0];이런식으로 기저사례에서만 체크할 수 있게 한 부분은 잘하셨습니다.
감사합니다.
0
음.. 아뇨 next_permutation은 O(N)이 아닙니다. next_Permutation을 걸면 전체적으로 nPr의 시간복잡도를 가지구요.
그리구 jin님의 코드 같은 경우 + + 와 + +를 구분하는 코드입니다. 1번 + 2번 + 이렇게 놔서 1, 2인지 2 1인지 구분하는데 그부분도 사실 불필요한 코드이기 때문에 해당 부분 고려하시면 더 좋은 코드가 될 거 같아요.
코딩 살구 클럽 컴파일 에러
0
4
1
추천 문제
0
7
1
코딩살구클럽 승인
0
9
1
코살구 1주차 1940번 문제 조건과 프라이빗 테스트 불일치 문의
0
21
2
문제를 고민하는 시간 관련
0
26
2
코딩살구클럽
0
38
2
코딩살구클럽 문의
0
37
2
코딩살구클럽 승인
0
35
2
DP 경우의 수 설명이 이해가 되지 않습니다.
0
33
2
3-F 채점 관련 질문
0
31
1
BFS, DFS 활용이 되는 상황에서의 방향성
0
33
2
코딩살구클럽 승인
0
45
2
코딩살구클럽승인
0
39
3
코딩살구클럽 승인
0
54
2
3-D 관련 질문
0
35
2
코살구 회원가입 문의
0
45
2
코살구 로그인 문제
0
65
2
3-A 문제 풀이 관련 질문
0
56
3
2-O 질문 있습니다
0
38
2
2-T 문제에 관한 질문
0
40
2
코딩 살구 클럽 접속 및 사용방법 문의
0
63
2
안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~
0
67
2
코딩살구클럽 로그인문제
0
85
3
코딩 살구 클럽 로그인 문제
0
86
2