전체 글
-
[프로그래머스] 탐욕 알고리즘 - 체육복알고리즘 공부/문제 풀이 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. 적절성 검사 : 새로운 부분해 집합이 적절한..
-
[프로그래머스] 완전 탐색 - 소수 찾기알고리즘 공부/문제 풀이 2020. 8. 16. 16:37
문제를 크게 두 부분으로 나눌 수 있다. 1. 낱말카드로 생성가능한 모든 수 만들기 2. 소수 검사 1번이 되게 애를 먹여서.. 결국 다른 사람의 코드를 참고했다. (참고 : https://hoho325.tistory.com/201) 핵심은 바로 순열을 이용하는 것이다. 순열과 set 자료구조를 이용하여 중복없는 숫자들을 생성하고 소수인지 검사하여 개수를 세어주면 된다. package Programmers; import java.util.*; public class bruteforce2 { static char[] chs; static boolean[] visited; //순열 탐색할때 사용 static HashSet set; static char[] select; static int solution(S..
-
[프로그래머스] 완전탐색 - 카펫알고리즘 공부/문제 풀이 2020. 8. 16. 12:21
static int[] solution(int brown, int yellow) { int[] answer = {0,0}; int m; // yellow 가로 길이 int n; // yellow 세로 길이 (m>=n) for(m=1;m=n && brown==2*m+2*n+4) {//brown 조건 만족 answer[0]=m+2; answer[1]=n+2; } } } return answer; } 어렵지 않게 해결하였다 같은 레벨문제인 소수 찾기가 .. 어려울뿐..
-
[알고리즘 개념] 완전 탐색알고리즘 공부/알고리즘 개념 2020. 8. 14. 19:51
완전 탐색 컴퓨터의 순기능을 이용하여, 모든 경우의 수를 탐색하는 방법이다. 모든 경우를 살펴보기 때문에 무조건 답을 찾을 수 있다는 장점이 있지만, 답을 찾는데 시간이 효율적이지 못하다는 단점이 있다. 따라서, 탐색할 요소가 적거나 N제한이 작은 경우에 완전 탐색을 사용한다. 구현 방법 1. 반복문 이용 - for문과 if문을 이용하여 코드를 작성한다. 재귀를 이용하는 것보다 코드 작성이 쉽지만, 중첩이 많이 일어난다는 단점이 있다. for(int i = 0 ; i < n ; i++) for(int j = i + 1; j < n; j++) for(int k = j + 1; k < n; k++) for(int l = k + 1; l < n; l++) cout
-
[프로그래머스] 힙 - 이중순위큐알고리즘 공부 2020. 8. 14. 14:46
static int[] solution(String[] operations) { int[] answer = {0,0};// 초기값 설정 // 최대값과 최소값을 처리하는 두개의 큐를 각각 만든다 PriorityQueue maxQ=new PriorityQueue(); PriorityQueue minQ=new PriorityQueue(); for(int i=0;i0) { answer[0]=maxQ.peek()*-1; answer[1]=minQ.peek(); } return answer; } 우선순위 큐를 이용하는 문제이다. 자바에서 제공하는 우선순위 큐 자료구조를 이용하고 싶어.. 최대힙과 최소힙을 나누어서 처리하도록 하였다. 최대힙과 상반되는 최소힙은 숫자를 넣을 때 -1값을 곱하여 처리하였다.
-
[프로그래머스] 힙 - 디스크 컨트롤러알고리즘 공부/문제 풀이 2020. 8. 12. 00:00
https://codevang.tistory.com/316 참고하여 해결하였다. import java.util.*; class Job{ int s;//요청된 시간 int t;// 걸리는 작업 시간 public Job(int s,int t){ this.s=s; this.t=t; } } class Solution { public int solution(int[][] jobs) { int answer = 0; int end = 0; // 수행되고난 직후의 시간 int jobsIdx = 0; // jobs 배열의 인덱스 int count = 0; // 수행된 요청 갯수 // 원본 배열 오름차순 정렬 (요청시간 오름차순) Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]); // 처리..