Java/알고리즘 (51) 썸네일형 리스트형 [자바 알고리즘 인터뷰] 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.. [자바 알고리즘 인터뷰] 12장 그래프 (1) 섬의 개수 https://leetcode.com/problems/number-of-islands/description/ - 1을 육지로, 0을 물로 가정한 2차원 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라(연결되어 있는 1의 덩어리 개수를 구하라) 풀이 1) DFS로 그래프 탐색 - 입력값이 정확히 그래프는 아니지만 사실상 동서남북이 모두 연결된 그래프로 가정하고 동일한 형태로 처리할 수 있으며, DFS 재귀를 이용해 네 방향 각각의 탐색을 끝마치면 1이 증가하는 형태로 육지의 개수를 파악할 수 있다. - 먼저 여기서는 행렬 입력값인 grid의 행, 열 단위로 육지(1)인 곳을 찾아 진행하다가 육지를 발견하면 그때부터 dfs()를 호출해 탐색을 시작한다. //행렬을 모두 탐색 for(int i=0; .. [자바 알고리즘 인터뷰] 12장 그래프 그래프 - 객체의 일부 쌍(Pair)들이 '연관되어' 있는 객체 집합 구조 오일러 경로 - 모든 간선을 한 번씩 방문하는 유한 그래프 해밀턴 경로 - 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로 - 최적 알고리즘이 없는 N-P 완전 문제 해밀턴 순환- 해밀턴 경로 중에서 원래의 출발점으로 돌아오는 경로 외판원 문제(Travelling Salesman Problem)- 한 번만 방문하여 출발지로 돌아오는 경로 중 가장 짧은 경로 그래프 순회(Graph Traversal)- 그래프의 각 정점을 방문하는 과정 - 그래프를 인접 리스트로 표현한 예- 인접 리스트는 출발 노드를 키로, 도착 노드를 값으로 표현 Map> graph = new HashMap();graph.put(1,Arrays.. [자바 알고리즘 인터뷰] ch 11 해시 테이블 (5) 완주하지 못한 선수 https://school.programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이 1) 해시 테이블을 이용한 풀이 - 참여한 선수 배열에서 완주한 선수 배열을 제외하면 1명이 남으며, 이 값을 찾아내는 문제다. - 동명이인이 등장할 수 있으므로, 이름을 키로 인원을 값으로 한 해시 테이블로 처리하여 동명이인인 경우에는 해당 키의 값을 +1 해준다. - 그런 다음 완주한 선수의 이름을 추출해 해시맵에서 하나씩 삭제하면 된다. 값을 -1 하다가 만약 1인 경우 해시맵.. [자바 알고리즘 인터뷰] ch 11. 해시 테이블 (4) 상위 k빈도 엘리먼트 https://leetcode.com/problems/top-k-frequent-elements/description/ - 빈도순으로 k개의 엘리먼트를 추출하라 풀이 1) 빈도수를 저장하고 빈도순으로 엘리먼트 추출 - 각 엘리먼트의 빈도를 추출하고 이를 빈도순으로 저장하거나 정렬한 다음, k번만큼 추출하면 문제를 풀이할 수 있다 . - 각 엘리먼트의 빈도 추출- 입력값 nums를 반복하며 빈도수를 저장할 해시맵 frequencyMap을 선언하고 여기에 빈도를 저장한다. - 처음 빈도를 계산한다면 0으로, 기존에 값이 있다면 그 값을 가져오고 모두 +1을 한다. //각 엘리먼트의 빈도수를 저장할 해시맵 선언, 엘리먼트=> 빈도수Map frequencyMap = new HashMap();//각 엘리먼.. 이전 1 2 3 4 5 ··· 7 다음
