본문 바로가기

알고리즘

그룹 합의 차이가 최소인 두 그룹으로 나누기 문제 정수 배열 하나가 있다. 이 배열을 두 그룹으로 나누는데 각 그룹의 원소들의 합을 서로 뺐을 때 가장 최솟값이 되도록 그룹을 나누어라. 그리고 그 최솟값을 반환하라. EX) [-1,6,9] -> [-1,9] , [6] -> 최솟값: 2 int[] numbers = {.....}; Arrays.sort(numbers); int curGap = 0; for(int i=0; i= 0 && curGap > perhapsGap){ curGap -= numbers[i]*2; } } return Math.abs(curGap) 더보기
TreeSet과 Comparator - TreeSet 특징 TreeSet은 이진탐색트리이다. 검색, 정렬에 유리하나 추가, 삭제에는 취약하다. Set이라서 중복을 허용하지 않는다. 기본적으론 nature ordering을 지원하지만 Comparator 객체를 매개변수로 사용하면 임의의 정렬방법을 지정할 수 있다. 노드는 2개의 자식노드를 가지고 있고 본인보다 작은 값을 가진 자식노드는 왼쪽, 큰 값을 가진 자식노드는 오른쪽에 추가된다.(그림 참조) - Comparator를 응용한 TreeSet 정렬 TreeSet treeSet = new TreeSet(new Comparator{ public int compare(String o1, String o2){ if(o1.length() 더보기
XOR의 성질 - 명제와의 연산 p ⊕ T = ¬p p ⊕ F = p p ⊕ p = F - 최댓값, 최솟값 x < N ⊕ k (N은 자연수) ➜ N - k < x < N + k 더보기
최대공약수 & 최소공배수 - 최대공약수 private static int gcd(int p, int q){ if(q==0) { return p; } return gcd(q, p%q); } // gcd(p,q) == gcd(q, p%q)이다. // 리턴값이 1이라면 p와 q는 서로수이다. - 최소공배수 private static int lcm(int p, int q){ return (p*q)/gcd(p,q); } 더보기