그래프와 그의 탐색과정으로 깊이 우선탐색과 너비우선탐색에 관해 전 포스트에 알아봤습니다.
여기에 링크를 걸어놨으니 한번 보시고 오셔도 좋습니다.(자바스크립트로 DFS와 BFS까지 구현해놨습니다.)
오늘은 그에따른 programmers 문제를 풀어보고 제가 풀었던 방법에 대하여 설명을 해보려합니다.
문제는 이렇게 4문제이고 제가 오기전에 일단 한번 풀어보고 포스트를 작성중입니다. 저기 한문제는 ... 뭐가 잘못되었는지 모르겠어요.. 나중에 댓글로 누군가 알려주세요..
- 타겟넘버
https://programmers.co.kr/learn/courses/30/lessons/43165
자세한내용은 위링크 가보시면 되지만 혹시나 궁금하신분들을 위하여
n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예
numbers = [1, 1, 1, 1, 1]
target = 3
return =5
로써 각각 한번씩 되는지 확인해야되는 문제였습니다.
function solution(numbers, target) {
var answer = 0;
var sum = 0;
var idx = 0;
answer = plusMinus(idx,numbers,target,answer,sum);
return answer;
}
function plusMinus(i,numbers,target,answer,sum){
if(numbers.length === i && sum===target){
return answer+1;
}else if(numbers.length === i){
return answer;
} else{
sum += numbers[i];
answer = plusMinus(i+1,numbers,target,answer,sum);
sum -= 2*numbers[i];
answer = plusMinus(i+1,numbers,target,answer,sum);
return answer;
}
}저는 위의 재귀함수를 이용한 위의 코드로 풀었습니다.
plusMinus라는 함수를 이용하여 현재의 idx(위치), 숫자배열, target숫자, 가능한 개수, 이전까지의 합을 함수에 넣어서 각각 더하고 빼서 다시 함수에 넣는 방법을 선택했습니다.(여기서 함수안에 넣고 숫자배열과 target숫자는 전역변수로 쓰는게 어떨까라는 생각은 들지만..)
재귀함수는 생각하기는 어렵지만 막상쓴다면 콜백도 되서 깊이탐색에 아주좋은 방법입니다. 모든경로를 탐색해야되는 방법이라 깊이 탐색으로 이용하고싶어 재귀를 이용하여 풀어봤습니다.
한곳의 노드를 방문하고 연결된 모든 노드를 방문하고 방문되지 않은 곳은 새로운 네트워크다 생각하고 방문되지 않은곳을 시작으로 새로운 방문을 시작하는 방법을 생각했습니다.
(코드를 올리는것은 가독성이 떨어져서 사진으로 대체하겠습니다.)
제일 처음 컴퓨터의 숫자만큼의 배열을 만들어서 방문체크를 합니다.
아무것도 안들어있다면 방문하지 않은것이고 방문하면 true를 집어넣는것이죠. 같은 idx에 있는 computers는 체크의 대상이 되는것이죠.
다음 i라는 노드에 방문하면 방문체크부터 합니다. 이미 방문했던 노드이면 바로 return해버리고, 방문하지 않은 노드라면 방문하고 그와 연결된 노드를 방문하기위해 방문함수로 들어가게 됩니다.
모든 방문이 끝났다면 4번째 줄의 for문에 의하여 방문체크가 됩니다. 방문하지 않은 노드가 있다면 그것은 연결되지 않은 네트워크로 추가가 되는 것입니다.
이렇게 하여 문제를 완료하게 되었습니다.
-
단어변환
https://programmers.co.kr/learn/courses/30/lessons/43163
단어변환은 단어의 변화의 최소숫자를 탐색하는 것으로 너비탐색을 이용하는 것이 적절하다 판단하여 적용해봤습니다.
que라는 배열을 만들어 로그를 입력하고 이동회수까지 적용하려 코드를 작성했습니다.
중간에 push되는 부분은 object로 되는 곳인데 한 화면에 들어가지 않아 한줄로 작성했습니다.
실행해본 결과는 위처럼 아주 잘 나오는거 같았습니다. 중복되는 것도 없고, 어떠한 word가 나오기 위해서 로그도 판별할수 있도록 prevWords까지 넣어서 나중에 순서도 정할수 있도록 하려고 정하였지만.. 결과는..
처참하네요.. 흑 이유는 모르겠지만 일단 넘어가도록 하고 4번문제에 집중했습니다.(이것저것 많이해봤지만 모르겠습니다 ㅠㅠ 누가 댓글로라도 알려주세요...) -
여행경로
https://programmers.co.kr/learn/courses/30/lessons/43164
마지막 여행경로 문제입니다.
인천공항에서 출발하여 모든 티켓을 다쓰며 경우한 node를 return하는게 문제였습니다. 그래서 저는 최소경로가 아닌 모든 경로를 다 거쳐야되기때문에 당연히 재귀함수를 이용한 깊이탐색을 이용해야겠다고 생각하여 코드를 작성해 나갔습니다.
두개의 경로라고 하더라도 알파벳 순서로 정렬되어야 하고, 제일 첫번째는 인천공항 고정이기 때문에 도착지로 정렬부터하고 시작했습니다.
이후 어떠한 티켓을 이용햇는지 ticketNum(ticketIdx)를 함수에 넣어서 출발지와 도착지를 모두 알수 있도록하였습니다.그리고, answer에는 현재까지의 여행지를 계속적으로 push를 해줘서 마지막에는 return 할수 있도록 했습니다. 그리고 어떠한 티켓을 이용했는지도 알기위해서 used배열도 같이 넣어주고 여행을 했다면 티켓을 used[ticketNum]에 true를 넣고 마무리했습니다.
마지막은 결국에 ICN부터 시작이고 티켓을 다 사용해야되기때문에 answer의 길이는 ticket의 길이보다 ICN으로 1만큼 증가해야되는걸로 체크를 했습니다.
여기서 중요한점은 배열을 넣을때는 항상 concat으로 넣어줘야 한다는 점입니다. 다른언어는 모르겠지만 자바스크립트에서는 C언어처럼 배열이 포인터처럼 들어가서 그냥 넣어준다면 return을 안하더라도 원래배열도 바꿔버리더라고요 조심하시면서 하시면 될것같습니다.(저는 이거때문에 1시간넘게 고생했어요..)
긴글이고 발표를 위한 글이긴하지만 다 적고나니 뿌듯하네요 ㅎㅎ
블로그 정기적으로 쓰시는분들 대단하다는걸 느끼네요.
마무리하며 부족한점이나 좋았다는 건 댓글 기능있는지 모르겠는데 댓글있으면 남겨주세요~
[5/9]
3번째 단어변환 완료했습니다.
어떤것이 예외인지는 모르겠으나 바로 숫자 리턴을 시켜주었더니 완료가 되었습니다.
예외를 모르지만 예외가 될수 있는 모든것을 사전차단하여 마무리하였습니다.
