본문 바로가기

JAVA/Java2021-4_Algorithm

 (9)
[브루트포스][java] 순차탐색, 경우의 수 Sequential search(순차탐색) -시간복잡도 : O(N) if 정렬이 되어있는 경우 이진탐색 -시간복잡도 : O(logN) 경우의 수 -순열(Permutation) : 선택 순서가 결과에 영향을 미치는 경우 ex package Basic_Algorithm.concept.브루트포스; //가장 큰 두자리 수 구하기 public class PermutaionTest { static int N=4; static int[] Nums={1,2,3,4}; static int solve(int cnt, int used, int val){ int ret=0; //ret 리턴할 값 if(cnt==2) return val; for (int i = 0; i < N; i++) { if((used&1
[자료구조][java]Data Structure (선형자료구조 비선형자료구조) 자료구조란? - 효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 법 (각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것) 분류(선형자료구조, 비선형자료구조) 선형자료구조 : 자료를 구성하는 데이터를 순차적으로 나열시킨 구조 (데이터가 한 줄로 줄 서 있다) -배열(Array) -연결리스트(Linked List) -스택(Stack) -큐(Queue) 비선형자료구조 : 하나의 자료 뒤에 여러 개의 자료가 존재하는 구조 -트리(tree) -그래프(graph) 선형자료구조(배열, 연결리스트, 스택, 큐) 배열 : 가장 기본적인 자료 구조로 특정 자료형의 데이터를 일렬로 나열한 구조 - index를 이용하여 데이터 접근이..
[그래프탐색][자료구조][java]BFS 그래프 탐색 방법 : DFS, BFS BFS : 너비 우선 탐색 - 루트노드나 임의의 노드에서 시작하여 인접한 노드를 먼저 모두 확인한 다음 depth를 탐색 - Queue를 사용하여 데이터를 탐색 (FIFO 원칙) - 재귀적으로 동작하지 않음 구현방법(인접행렬, 인접리스트) 1. 인접행렬(adjacent array) package Basic_Algorithm.concept.그래프탐색; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Node{ int start; int end; public Node(int start,int end){ this.start=start; this.end=end; } } p..
[그래프탐색][자료구조][java]DFS 그래프 탐색 방법 : DFS, BFS DFS : 깊이 우선 탐색 (1->2->4->8->5->->(8)->6->3->7) - 루트 노드나 임의의 노드(정점)에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색한 후 돌아와 다른 노드로 탐색하는 방법 - Stack 자료구조를 이용하여 데이터 탐색 장점 - 한 경로상의 노드들만 기억하면 되어 저장공간 수요가 적음 - 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음(BFS와 비교했을 때의 장점) 단점 - 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있음 - 얻어진 해가 최단 경로가 된다는 보장이 없음 구현방법(인접행렬, 인접 리스트) 1.인접행렬 2차원 행렬을 이용하여 - 세로(열) : 출발정점 번호, 가로(행) : 목적정점 번호 연결되어있..
문제4_그래프탐색(Depth-First Search 와 Breadth-First Search) ex) 미로 찾기, 출구 찾기, 물건 찾기 Node(vertex) Edge(간선) DFS(Depth-First Search) Stack이용 0->2->6->5->1->4->3->7 1. 처음 방문한 0을 스택에 넣는다. 0 2. 0에 대해 인접한 애를 스택(1, 2)에 넣는다. 3. 이 중에 인접한 2을 꺼낸다. 0->2 4. 2에 대해 인접한 (5, 6)을 스택에 넣는다 5. 이 중에 인접한 6을 꺼낸다. 0->2->6 6. 이제 6에 인접한 애가 없으니까 5를 꺼낸다. 0->2->6->5 7. 이제 5에 인접한 애가 없고 2에 인접한 것도 다 방문을 하였기 때문에 1을 방문하러간다. 8. 1을 꺼낸다. 0->2->6->5->1 9. 1에 인접한 (3,4)를 스택에 넣는다. 10. 이 중 인접한 4를 ..
문제3_정렬알고리즘(버블,선택,삽입 O(N^2) 병합,퀵,힙 O(logN) ,계수 정렬 O(log(N+K)) 정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 라이브러리 정렬 O(NlogN) 버블: O(N^2), 선택 : O(N^2), 삽입 : O(N^2), 퀵 : O(NlogN), 계수 : O(N+K) 버블 선택 삽입 퀵 예시 [7,5,9,0,3,1,6,2,4,8] 병합 정렬 예시[5, 3, 2, 1, 6, 8, 7, 4] 계수 정렬 [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2] 1.버블정렬 O(N^2) : 가장 쉽고 직관적인 정렬로, 첫번째 자료와 두번째 자료를 두번째 자료와 세번째 자료를 ... 이런식으로 n-1번째와 n번째 자료를 비교 교환하면서 자료를 정렬하는 방식 동작 : 제일 끝에 가장 큰 수를 놓는 방식으로 package Basic_Algorithm; public class ..
문제2_정렬된 수에서 하나의 수 찾기 단순 반복문을 이용하면 O(N)의 시간 복잡도가 걸리는데-> 이진탐색을 이용하면 O(logN)의 시간 복잡도로 수행하여 구현할 수 있다. 수의 예 [12 25 31 28 54 66 70 83 95 108] 83의 위치 : 8번째. 88의 위치 : 없음. target번호만 바꿔서 확인하면 됨!! package Basic_Algorithm; public class Test02_find_num_binarysearch { public static void main(String[] args) { int[] sorted_numbers={12,25,31,28,54,66,70,83,95,108}; int target=88; int left=0; int right=sorted_numbers.length; int mid=..
문제1_Find_Max And Min Number Max와 Min이 배열의 몇 번째에 있는지 순서를 찾아라(index+1) (조건 : 한번의 반복문만 사용할 것) 수의 예 : [10 55 23 2 79 101 16 82 30 45] 답 최댓값 6번째 101 최솟값 4번째 2 package Basic_Algorithm; import java.util.Scanner; public class Test01_find_maxmin { public static void main(String[] args) { // 숫자 10개 입력받아서 배열 만들 때 사용 // Scanner scan=new Scanner(System.in); // int[] numbers=new int[10]; // for (int i = 0; i < 10; i++) { // int num=scan..

티스토리툴바