알고리즘 공부
-
[알고리즘 개념] 동적계획법알고리즘 공부/알고리즘 개념 2020. 8. 22. 17:54
동적 계획법 영어로 하면 Dynamic Programming이다. 큰 문제를 작은 문제로 나누어 푸는 문제를 일컬어 동저계획법이라고 한다. 이 점에서 분할 정복과 비슷하지만, 가장 큰 차이점은 동적 계획법에서는 쪼개진 작은 문제가 중복되지만, 분할 정복은 절대로 중복될 수가 없다는 점이다. 따라서 동적 계획법은 작은 문제의 결과를 저장해둔다. 이미 계산한 값을 저장해 두는 메모리를 캐시라고 하며 같은 문제가 다시 등장하였을 때 이를 이용하여 문제 해결 속도를 향상할 수 있다. 조건 작은 문제의 반복이 일어나는 경우. 단, 이 작은 문제의 결과는 같아야 한다. 즉, 어떤 문제가 여러 개의 부분 문제로 쪼개어질 수 있어야 하며 이 부분 문제는 같은 부분 문제이거나 재귀 알고리즘을 통해 해결되어야 한다. 피보..
-
[프로그래머스] 탐욕 알고리즘 - 단속카메라알고리즘 공부/문제 풀이 2020. 8. 18. 23:40
public static int solution(int[][] routes) { int answer = 0; // routes[0] 오름차순 정렬 Arrays.sort(routes,new Comparator() { public int compare(int[] o1,int[] o2) { return o1[0]-o2[0]; } }); int point=routes[0][0]; int pre_count=0;// 전에 센 값 while(point Integer.compare(a[1], b[1])); int camera=-30001; for(int[] route:routes) { if(camera
-
[프로그래머스] 탐욕 알고리즘 - 섬 연결하기알고리즘 공부/문제 풀이 2020. 8. 18. 17:01
문제를 읽고 최소 스패닝 트리를 만드는 문제라는 것을 알았고 크루스칼 알고리즘을 이용하였다. static int solution(int n, int[][] costs) { int answer = 0; ArrayList in=new ArrayList(); int[][] adj = new int[n][n];//인접한 섬들을 알려주는 배열, 0으로 초기화 상태 for(int i = 0; i < costs.length; i++) { //선은 양방향 adj[costs[i][0]][costs[i][1]] = adj[costs[i][1]][costs[i][0]] = costs[i][2]; } in.add(0); while(in.size()
-
[프로그래머스] 탐욕 알고리즘 - 조이스틱알고리즘 공부/문제 풀이 2020. 8. 18. 15:02
public static int solution(String name) { int answer = 0; char[] arr = name.toCharArray(); char[] temp=new char[arr.length]; int left = 0, down = 0, up = 0, right = 0; char check; // 진행방향 나타내는 변수 //temp 초기화 for(int i=0;i 0; i--) { if(arr[i] !='A') { right=i; break; } } //더 적은 수로 check 초기화 check = right
-
[프로그래머스] 탐욕 알고리즘 - 큰 수 만들기알고리즘 공부/문제 풀이 2020. 8. 17. 20:30
public static String solution(String number, int k) { String answer = ""; char[] chs=number.toCharArray(); int[] nums=new int[number.length()]; int max_index=0; int l=number.length(); int left=0;//남은 제거할 수 //가능한 앞자리 중 가장 큰 수 찾기 for(int i=0;i 숫자 max_index=(nums[max_index]
-
[프로그래머스] 탐욕 알고리즘 - 체육복알고리즘 공부/문제 풀이 2020. 8. 17. 11:59
static int solution(int n, int[] lost, int[] reserve) { int answer = 0; int lost_index=0, reserve_index=0; int[] students=new int[n+2];//1~n번까지, 앞뒤로 하나씩 추가하여 따로 예외처리하지 않음 // 순차적으로 들어오지 않을 수 있기 때문에 Arrays.sort(lost); Arrays.sort(reserve); // students 배열 만들기 for(int i=1;i
-
[알고리즘 개념] 탐욕 알고리즘알고리즘 공부/알고리즘 개념 2020. 8. 16. 18:52
탐욕 알고리즘 탐욕 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 즉, 동적 프로그래밍을 보완하는 알고리즘인 것이다. 탐욕 알고리즘은 각 단계에서 조건에 맞는 최선의 선택을 하는 기법이다. 그렇기 때문에 모든 문제에 대해서 탐욕 알고리즘이 통하지 않는다. 예를 들면, 지금 선택하면 1개의 마시멜로우를 받고, 1분을 기다리면 2개의 마시멜로우를 준다고 했을 때 탐욕 알고리즘은 1개의 마시멜로우를 받는 선택을 내린다. 따라서 어떤 문제가 탐욕 알고리즘이 통하는지 잘 판단하여야 한다. 탐욕 알고리즘은 다음과 같은 과정을 거친다. 1. 해 선택 : 현재 가장 최적인 해를 구하여, 이를 부분해 집합에 추가한다. 2. 적절성 검사 : 새로운 부분해 집합이 적절한..