인프런 커뮤니티 질문&답변
작성한 질문수
3-O 이중for문의 j처리에 대해 질문드립니다.
해결된 질문
작성
·
25
·
수정됨
0
안녕하세요 큰돌님 go함수의 이중for문에서 의문이 있어 질문드립니다.
int i=here로 세로축(가로선범위)에는 제약을 걸었고, main함수에서 go(1, 0)으로 함수를 시작하는 것을 확인했습니다.
하지만 가로축(세로선범위)는 int j=1로 시작합니다.
그리고 visited는 오직 가로선을 놓을 수 있는지 없는지만 판단하죠.
visited[i][j] = 1;
go(i, cnt + 1);
visited[i][j] = 0;
이 line에 의해서 j=1 상황은 빠져나온 후 (here, j=1) 일때를 지나서 (here, j=2)일때 go함수가 실행된다면 다시 이중for문으로 들어와 j=1일때 go를 실행할 것입니다.
그렇다면 j에 의해서는 조합의 경우의 수가 아니라 순열의 경우의 수만큼 go함수 호출이 발생할 것입니다.
그래서 j에도 1부터 탐색하는게 아니라 현재위치부터 탐색하도록 만들어야하는 것이 아닐까요??
논리적으로 정답은 똑같아서 정답처리 되었지만 시간 상 더 오래걸릴 수 있지않을까 라는 생각이 들었습니다.
제가 잘못생각하고 있는것인지 궁금하여 질문드립니다.
답변 2
0
안녕하세요 광인님 ㅎㅎ
for(int i = here; i <= h; i++){
for(int j = 1; j < n; j++){좋은 말씀이신데요 ㅎㅎ
지금 보면 매개변수는 here밖에 안받고 있으며 만약 j도 현재위치가 되려면 함수자체를 변경해야 하는데 어떻게 변경되어야 한다고 말씀하시는 건가요?
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다.
김광인님의 질문을 해결하기 위해 유사한 질문과 답변들을 찾아보았습니다. 이와 비슷한 질문에서 강사님께서 답변을 주신 사례들이 있습니다. 다음 내용을 참고해 주세요.
설명 및 유사 질문 안내
이중 for 문의 시작 인덱스에 대한 질문: 김광인님께서 제기하신 문제는 go 함수 내에서 가로선을 놓을 수 있는 위치를 순회할 때, j의 시작 위치를 현재 위치로 제한함으로써 불필요한 순회를 줄이고자 하는 내용입니다. 이와 관련해서 다음 URL에서 유사한 논점을 찾아볼 수 있습니다:
3-O go 함수 질문 드립니다.: 이 질문에서는 이중 for 문의 시작점에 대한 이해가 다뤄졌습니다. 한 가지 명확히 하고 싶은 점은,
here부터 탐색을 시작함으로써 이전에 이미 체크된 부분을 중복해서 확인하지 않기 위함이라는 것입니다.3-O 15684 사다리조작 질문입니다.: 여기서는 가로선 설정 시
j범위에 대한 고민과 의문을 해결하는 답변들이 있습니다.n를 포함하지 않음으로써 발생할 수 있는 반례와 그 영향에 대해 설명합니다.
이 문제에서 첨언하자면, 순서나 조합의 가능성을 최대한 줄여서 효율적으로 알고리즘을 구현하는 것이 중요합니다. 각 호출에서 시작 인덱스를 제한하는 것이 최적화의 한 방법이라는 점에서 김광인님의 접근이 유효할 수 있습니다. 이와 같은 최적화의 가치는 특히 문제의 범위가 커질수록 더 중요합니다.
이 정보를 바탕으로, 개선할 필요성을 느끼신 부분에 대해 실험적으로 코드를 바꿔보고 실행 시간을 비교해 보는 것도 좋은 방법일 것입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.