개발 기록

DFS 중복순열을 만드는 알고리즘이였는데 만들어진 배열 원소의 합이 주어진 특정 수와 똑같을 때 그 배열의 최소 사이즈를 구하는 것이였다. import java.util.Scanner; public class Main { static int n, m; //제일 큰수로 해야됨 ( 최소 개수를 구하는 것이기 때문에 ) static int answer = Integer.MAX_VALUE; static int[] arr; //L-동전 갯수 public void DFS(int L, int sum) { if (sum > m) return; if (sum == m) { answer = Math.min(L, answer); } else { for (int i = 0; i < n; i++) { DFS(L + 1, sum..

정점의 개수가 클때 인접행렬로 하기에는 비효율적 인접리스트 정점 개수만큼 리스트 객체 생성 간선 정보가 들어올때 해당 정점 리스트에 연결된 번호 추가 경로 탐색시 해당 정점 리스트의 사이즈만큼만 돌면 됨 연결된 선인지 확인할 필요가 없음(방문 했는지만 체크) 예시 ArrayList graph = new ArrayList(); int n = 5; //점 개수 int m = 9; //간선 개수 //점 개수만큼 리스트 생성 (0번째는 사용 x) for (int i = 0; i

그래프는 기호로 G(V,E) V- Vertex (점) E - edge (간선) 인접행렬은 그래프간의 관계를 배열로 나타낸 것 1. 무방향 그래프 방향이 없는, 양방향이라고도 볼 수 있다 *인접행렬 ex. 1과 2가 이어져 있으므로 graph[1][2] = 1; graph[2][1] = 1; 해당 점이 행과 열인 칸을 1로 채워준다 -행번호를 탐색해서 값이 1인 열이 행번호점과 연결된 점이라고 판별 가능 ⬇️1번행에서 2,3열 값이 1이므로 그래프에서 볼 수 있듯이 1번점은 2번과 3번점과 연결되어 있음 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 0 2. 방향 그래프 이동하는 방향이 정해진 그래프 *인접행렬 ex. 1에서 2로 이동하는 방향이므로 graph[1][..

이진트리 Binary Tree 각각의 노드가 최대 두 개 의 자식 노드를 가지는 트리 자료 구조 각각 왼쪽 자식, 오른쪽 자식 노드라고 한다 1. 전위 순회(preorder) - root(부모)먼저 root - left - right A-B-C-D-E-F-G 2. 중위 순회(Inorder) -root를 가운데로 left-root-right C-B-D-A-F-E-G 대칭 순회(symmetric)라고도 함 3. 후위 순회(postorder)-root를 마지막에 left-right-root C-D-B-F-G-E-A

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다. 재귀 호출이나 되부름이라고도 한다. 출처 ; 나무위키 ex. 재귀 함수를 이용해서 십진수를 이진수로 변경하는 함수 만들기 public class Main { public void binary(int n) { if (n == 0) return; else { binary(n / 2); System.out.print(n % 2); } } public static void main(String[] args) { Main T = new Main(); Scanner in = new Scanner(System.in); int n = in.nextInt(); T.binary(n); } } binary메소드 안에서 binary를..

배열 arr의 tmp값 인덱스 찾기 Arrays.binarySearch(arr, tmp) 복제 arr.clone();

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 배열에서 두번째 요소부터 타켓으로 설정 후 이전 숫자와 비교. (a). 타겟 : 7 . 이전 숫자인 3과 비교 -> 타겟이 더 크니까 위치 안 바뀌고 패스 (b). 타겟 : 2 . 이전 숫자 7과 비교 -> 타겟이 더 작음 -> 7의 위치를 한칸 뒤로 땡김 -> 더 이전 숫자 3과 비교 -> 타겟(2)가 더 작은 -> 3의 위치도 한칸 뒤로 땡김 -> 첫번째 자리에 타겟(2) 삽입 ... 같은 과정 반복 ** import java.util.Scanner; public class Main { public int[] so..

for (int i = 0; i arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } n과 n+1을 비교 후 자리 바꿈해서 정렬 배열 한 바퀴 돌면 제일 큰 수가 맨 뒤로 가기때문에 for문 엔드 인덱스가 하나씩 줄음.