알고리즘 공부
-
[프로그래머스] 완전 탐색 - 소수 찾기알고리즘 공부/문제 풀이 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]); // 처리..
-
[알고리즘 개념] 힙 (heap)알고리즘 공부/알고리즘 개념 2020. 8. 11. 15:55
이진트리 : 모든 노드의 자식 노드가 2개 이하인 트리 구조 완전 이진트리 이진트리와 다르게 데이터가 루트 노드부터 시작하여 자식 노드가 왼쪽, 오른쪽 자식 노드 순서로 쌓이게 되는 트리를 말한다. 이진트리는 중간에 노드가 비어있을 수 있지만, 완전 이진 트리는 중간 노드가 비어있을 수 없는 형태이다. 힙 힙은 최대 힙과 최소 힙이 있다. 최대 힙은 구성하는 모든 노드가 '부모 노드가 자식 노드보다 크다'라는 규칙을 가진 것이다. 최소 힙은 반대로 구성하는 모든 노드에 대해 부모 노드가 자식 노드보다 작다는 규칙을 가진 것이다. 따라서 힙의 루트는 최댓값이나 최솟값이다. 따라서 힙은 최댓값과 최솟값을 쉽게 찾을 수 있는 자료 구조이다. 배열의 인덱스를 활용하여 자식 노드와 부모 노드를 찾기 쉽기 때문에 ..