개발 무지렁이

타겟넘버 🪅 모든 조합을 일일이 해야할 때(완전탐색), DFS로 구현할 수 있느냐 🪅 재귀함수를 사용할 때, 종료조건을 명시했느냐 class Solution { int result = 0; public void DFS(int[] numbers, int target, int index, int sum) { if(index == numbers.length) { if(sum == target) { result++; } return; } DFS(numbers, target, index+1, sum+numbers[index]); DFS(numbers, target, index+1, sum-numbers[index]); } public int solution(int[] numbers, int target) { in..

소수찾기 🪅 KeyPoint: 문자열을 쪼개서 순서 상관있게 조합할 수 있느냐 (순열) => recursive 🪅 KeyPoint: 중복을 어떻게 제거할 것이냐 => HashSet() 🪅 KeyPoint: 소수 찾는 알고리즘을 구현할 수 있느냐 => isPrime() ⚠️ String에 +연산자를 이용하면 char를 붙일 수 있다. ⚠️ .substring(i+1)은 i+1번째부터 마지막까지의 부분문자열을 의미한다. import java.util.*; class Solution { Set numberSet = new HashSet(); public void recursive(String comb, String others) { if(!comb.equals("")) { int num = Integer.pa..

분할정복 알고리즘인 퀵(Quick) 정렬 특정값을 기준으로 큰숫자와 작은숫자로 분할하자 (기준값, pivot) ❓ 분할정복 알고리즘이란 : 분할한 다음 각각 정렬하고 합치면 빠르다. 🕑 시간복잡도: O(N * log(2)N) [ 각 단계에서 N번씩 탐색 * 쪼개지는 깊이 ] [ 평균적으로 반씩 쪼개진다 ] 퀵(Quick) 정렬 코드 구현 1. 피벗을 맨 앞에있는 값으로 잡는다. pivot = A[start] 2. i = start + 1로 잡고 A[i]가 피벗보다 작으면 그냥 넘긴다. i++ 3. j = end로 잡고 A[j]가 피벗보다 크면 그냥 넘긴다. j-- - 엇갈리면 pivot과 swap, i > j - 엇갈리지 않으면 양쪽 인덱스 숫자를 swap 4. 엇갈리면 while문에서 빠져나와 재귀함수..

그래프의 모든 노드를 탐색하는 DFS(Depth First Search) 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 시작노드에서 출발하여 리프노드까지 내려가고 부모에게 올라가, 다시 리프노드까지 내려가는 것을 반복하는 과정을 ' 깊이우선탐색(DFS) '라고 한다. 🕑 시간복잡도: O(V + E) (V: 노드 수, E: 간선 수) [모든 정점을 한 번씩 방문하고, 그러기 위해 모든 간선을 한 번씩 검사했으니] DFS와 재귀함수 DFS는 재귀함수로 구현하며, 재귀함수란 '자기 자신'을 Function call(함수 호출)하여 동작하는 방식을 말한다. (종료조건과 재귀적확장이 있어야 한다.)DFS 코드 구현, 백준 1260 DFS 🪅 에지리스트를 인접리스트로 구현할 수 있는가 🪅 ..