Java/알고리즘 (47) 썸네일형 리스트형 [자바 알고리즘 인터뷰] 12장 그래프 (9) 코스 일정 https://leetcode.com/problems/course-schedule/description/ - 0을 완료하기 위해선느 1을 끝내야 한다는 것을 [0,1] 쌍으로 표현하는 n개의 코스가 있다.- 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라 풀이 1) DFS로 순환 구조 판별 - 이 문제는 그래프가 순환(Cyclie) 구조인지를 판별하는 문제로 바꿀 수 있다. - 순환 구조라면 계속 뱅글뱅글 맴돌게 될 것이고, 해당 코스는 처리할 수 없기 때문이다. - 따라서 순환 판별 알고리즘을 구현하면 이 문제를 풀이할 수 있다. Map> finishtoTakeMap = new HashMap();//완료하기 위해 처리해야 하는 일정을 finish->take 형태의.. [자바 알고리즘 인터뷰] 12장 그래프 (8) 여행 경로 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이 1) 일정 그래프 반복 DFS 2024.05.17 - [Java/알고리즘] - [자바 알고리즘 인터뷰] 12장 그래프 (7) 일정 재구성 [자바 알고리즘 인터뷰] 12장 그래프 (7) 일정 재구성https://leetcode.com/problems/reconstruct-itinerary/description/ - [from,to]로 구성된 항공권 목록을 이용해 JEK에서 출발하는 여.. [자바 알고리즘 인터뷰] 12장 그래프 (7) 일정 재구성 https://leetcode.com/problems/reconstruct-itinerary/description/ - [from,to]로 구성된 항공권 목록을 이용해 JEK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘순(Lexical Order)로 방문한다. 풀이 1) 일정 그래프 재귀 DFS - 여행 일정을 그래프로 구성해 DFS를 진행하면 징행된 경로를 정답으로 처리할 수 있다. - 주의할 점은 중복된 일정일 경우 어휘순으로 방문한다는 점이다, - 입력값인 여행 일정은 끝까지 이어질 것이므로 from->to 형태의 그래프로 구성해 끝까지 탐색하면 된다. //여행 일정을 from->to 형태의 그래프로 구성for(List ticket : tickets) { .. [자바 알고리즘 인터뷰] 12장 그래프 (6) 부분집합 https://leetcode.com/problems/subsets/description/ - 모든 부분집합을 리턴하라 풀이 1) 트리의 모든 DFS 결과 - 트리를 구성하고 트리를 DFS하는 문제로 풀이할 수 있다.- 자기 자신보다 큰 값이 자식 노드인 트리형태가 된다. - path에 지금까지 탐색한 경로를 저장하며 인덱스를 증가시키면서 DFS한다. - 별도의 종료 조건없이 모든 탐색의 경로가 부분집합이 되므로 탐색할 때 마다 매번 결과를 추가하면 된다. public void dfs(List> results, int nums[], int index, Deque path){ //모든 탐색 경로를 매번 결과에 추가 results.add(new ArrayList(path)); /.. [자바 알고리즘 인터뷰] 12장 그래프 (5) 조합의 합 https://leetcode.com/problems/combination-sum/description/ - 숫자 집합 candidates를 조합하여 합이 target이 되는 엘리먼트들을 나열하라. 각 숫자는 중복으로 나열 가능하다. 풀이 1) DFS로 중복 조합 그래프 탐색 - 합 target을 만들 수 있는 모든 번호 조합을 찾는 문제인데, 앞서 순열 문제와 유사하게 DFS로 풀이할 수 있다. - 입력값의 중복 조합 그래프를 풀이하는 문제로 도식화할 수 있다. - 모든 중복 조합에서 찾아야 하기 때문에 항상 부모의 값부터 시작하는 그래프로 구성할 수 있다. - 조합은 각각의 노드가 자기 자신보다 더 큰 숫자의 나열로 정리할 수 있다. public void dfs(List> resul.. [자바 알고리즘 인터뷰] 12장 그래프 (4) 조합 https://leetcode.com/problems/combinations/description/ - 전체 수 n을 입력받아 k개의 조합(Combination)을 리턴하라 풀이 1) DFS로 k개 조합 생성 - 조합의 경우 자기 자신뿐만 아니라 앞의 모든 엘리먼트를 배제하고 구성해야 한다.- 왜냐하면 조합은 순서를 보지 않으므로 한 번 나왔던 엘리먼트는 다시 나와야 하지 않기 때문이다. - 이 말은 이전 엘리먼트보다 이후 엘리먼트의 값을 항상 더 크게 구성할 수있다는 말이기도 하다. public void dfs(List> results, LinkedListelements, int n, int start, int k) { //k번째 노드에 도달하면 결과에 추가 if.. [자바 알고리즘 인터뷰] 12장 그래프 (3) 순열 https://leetcode.com/problems/permutations/description/- 서로 다른 정수를 입력받아 가능한 모든 순열(Permutation)을 리턴하라 풀이 1) DFS를 활용한 순열 생성 - 순열이란 결국 모든 가능한 경우를 그래프 형태로 나열한 결과라고 할 수 있기 때문에 그래프로 표현해보면 다음과 같다. - 리프 노드(Leaf), 즉 A3의 모든 노드가 순열의 최종 결과이다.- 레벨이 증가할수록 자식 노드의 개수가 점점 적어진다. A0의 자식 노드는 3개였다가 A1의 자식 노드는 2개, A2의 자식 노드는 1개 순으로, 이는 순열의 수식이기도 한 3*2*1 형태이기도 하다. public void dfs(List> results, List prevElements,.. [자바 알고리즘 인터뷰] 12장 그래프 (2) 전화번호 문자 조합 https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/ - 2에서 9까지 숫자가 주어졌을 때 전화번호로 조합 가능한 모든 문자를 출력하라 풀이 1) 모든 조합 탐색 -모두 조합하는 형태로 전체를 탐색한 후 백트래킹하면서 결과를 조합할 수 있다.- digits는 입력값이며, 각 자릿수에 해당하는 키판 배열을 DFS로 탐색하면 결과가 완성된다, - 입력값인 digits의 자릿수 단위로 반복하고, 현재 자리 숫자에 해당하는 모든 문자를 탐색하면서 지금까지 구성된 문자열을 path 변수에 저장해 넘기면서 재귀 탐색한다. public void dfs(List result, Map> dic, String digits.. 이전 1 2 3 4 ··· 6 다음
