전체 글215 11659: 구간 합 구하기 4(java) 문제풀이 m부터 n까지의 부분 합은 0부터 m까지의 부분 합에서 0부터 (n-1)까지의 부분 합을 뺀 값임을 이용한다. 입력된 수들을 저장할 arr 배열과 0부터 n까지의 배열을 저장할 sum 배열을 선언했을 때, i부터 j까지의 부분 합은 (sum[j]-sum[i-1])이다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new.. 2024. 9. 2. 백준 3477: 버그왕(java) 문제풀이 파일이 끝날 때까지 입력받고, replaceAll()을 사용해 "BUG"를 ""으로 변경해 주면 되는데, 이상하게 계속 오류가 나던 문제이다.이때 BUG가 더 이상 존재하지 않을 때까지 replaceAll() 작업을 계속해야 한다는 점에 주의해야 한다.while((str=br.readLine())!=null) { while(str.contains("BUG")) { str=str.replaceAll("BUG", "");}문제에 주어진 "ABUBUGGB"의 경우, 첫 번째 replaceAll()로 BUG를 삭제(밑줄 친 부분)하면 " ABUGB"가 되어 다시 BUG 문자열이 생기므로, 이 경우 while문을 이용해 문자열에 BUG가 존재하지 않을 때까지 반복해야 한다. 전체 코드import jav.. 2024. 8. 31. 백준 10816: 숫자 2(java) 문제풀이 해시맵을 사용한 방법 또는 이분 탐색을 이용한 방법 2가지로 풀이할 수 있다.1. 해시맵 사용 카드와 그 카드의 개수를 각각 키와 값으로 가진 해시맵을 사용한다.if(hm.containsKey(input)) hm.put(input, hm.get(input)+1);else hm.put(input, 1);입력된 숫자가 해시맵에 존재하지 않을 경우(=처음으로 등장한 카드일 경우) 지금까지 한 장 등장한 것이므로 해시맵에 을 삽입하고, 입력된 숫자가 해시맵에 이전에 삽입된 적 있는 숫자일 경우 이전보다 한 장 더 등장한 것이므로 (n, (지금까지 해당 카드 개수)+1)을 삽입한다.if(hm.containsKey(input)) sb.append(hm.get(input)+" ");else sb.append.. 2024. 8. 28. 히프 응용-LPT 알고리즘 LPT(Longest Processing Time first): 가장 긴 작업을 우선적으로 할당하는 방법- 서로 다른 소요 시간을 가지는 작업들을 가장 짧은 시간 내에 마무리해야 할 때 LPT를 이용해 근사의 해를 찾을 수 있다. m개의 기계와 n개의 작업이 있고, 각 작업에 걸리는 기계의 사용 시간이 다르다고 가정하자. 모든 기계를 가동하여 최소의 시간 내에 작업들을 모두 끝내는 문제를 머신 스케줄링(machine scheduling)이라 한다. 이때 LPT를 활용해 문제를 해결할 수 있다. 아래와 같이 기계 사용 시간에 따라 정렬된 7개의 작업이 있고 동일한 기계가 3대 있을 때,J1J2J3J4J5J6J78765321 LPT 알고리즘은 각 작업들을 가장 먼저 사용 가능하게 되는(=이전 작업이 가장 빨.. 2024. 8. 26. 히프 정렬 히프 정렬(heap sort): 히프를 사용하는 정렬 알고리즘- 최대 히프를 이용하여 n개의 요소를 O(nlog₂n)의 시간 복잡도로 정렬- 정렬되지 않은 1차원 배열이 존재할 때, 배열의 데이터들을 차례대로 최대 히프에 추가- 한 번에 하나의 요소를 히프에서 꺼내 배열의 뒤쪽부터 저장- 배열은 오름차순으로 정렬됨 히프 정렬 복잡도- 히프 트리의 전체 높이는 log₂n이므로 하나의 요소를 히프에 삽입하거나 삭제할 때 히프 재정비에 log₂n만큼의 시간 소요- 요소의 개수가 n개일 때 전체적으로 O(nlog₂n)의 시간 소요- 삽입 정렬 알고리즘 시간 복잡도가 O(n²)인 것에 비해 효율적- 히프 정렬은 전체 자료 정렬 보다는 가장 큰 값 몇 개만이 필요할 때 가장 유용히프 정렬 구현#include #in.. 2024. 8. 26. 히프의 구현 - 히프는 1차원 배열로 표현될 수 있음- 히프의 각 요소들을 구조체 element로 정의하고, element의 1차원 배열을 만들어 히프 구현#define MAX_ELEMENT 200typedef struct { int key;} element;typedef struct { element heap[MAX_ELEMENT]; int heap_size; //현재 히프 안에 저장된 요소 개수} HeapType; - 히프를 생성하려면 아래와 같은 방법을 사용HeapType heap;HeapType* heap = create(); //동적 할당 이용삽입 연산- 히프에 새로운 요소가 들어오면, 일단 새로운 노드를 히프의 마지막 노드로 삽입- 삽입 후에 새로운 노드를 부모 노드들과 교환하여 히프의 성질을 만족하도록 .. 2024. 8. 25. 백준 31860: 열심히 일하는 중(java) 문제풀이 우선순위 큐를 이용하는 문제다.PriorityQueue queue=new PriorityQueue(Comparator.reverseOrder());우선순위 큐 queue를 생성하되, 중요도가 높은 일부터 먼저 처리하게끔 해야 하므로 Comparator.reverseOrder()를 지정해야 한다. 이후 queue에서 poll한 값을 K와 비교해 K 이하일 경우 삭제된 채로 continue하고, K 초과일 경우 이 값에서 M만큼 뺀 값을 다시 queue에 삽입한다. 위 과정을 queue가 공백 상태가 될 때까지 반복하고, 한 번 반복할 때마다 count를 1씩 증가시킨다.import java.io.BufferedReader;import java.io.IOException;import java.io.. 2024. 8. 25. 백준 28107: 회전초밥(java) 문제풀이 손님 큐와 초밥 큐, 2개의 우선순위 큐를 이용해 풀이한다. customer 우선순위 큐에 { 초밥 종류, 손님 번호 }를 원소로 가지는 배열을 삽입한 후 초밥 종류에 따라 오름차순으로 정렬하고, 같은 종류의 초밥일 경우 손님 번호 순으로 정렬한다.PriorityQueue customer=new PriorityQueue(new Comparator() { @Override public int compare(int[] o1, int[] o2) { if(o1[0]==o2[0]) { //같은 초밥일 경우 return o1[1]-o2[1]; //손님 순서로 정렬 } return o1[0]-o2[0]; //초밥 종류로 정렬 }}); 이때 Comparator 수정을 통해 정렬 규칙을 추가해 .. 2024. 8. 25. 백준 11286: 절댓값 힙(java) 문제풀이 작은 수부터 출력해야 하므로 최소 우선순위 큐로 풀이하되, 절댓값은 같지만 부호가 다를 경우 순서를 조정해야 하므로 Comparator를 수정한다.class NewComparator implements Comparator{ @Override public int compare(Integer o1, Integer o2) { if(Math.abs(o1)>Math.abs(o2)) { //o1의 절댓값이 더 크면 자리 변경 return Math.abs(o1)-Math.abs(o2); } else if(Math.abs(o1)==Math.abs(o2)) { //절댓값이 동일하면 음수를 앞으로 보냄 return o1-o2; } else { return -1; .. 2024. 8. 24. 백준 23757: 아이들과 선물 상자(java) 문제풀이 우선순위 큐를 사용해 쉽게 해결할 수 있다. 선물이 가장 많이 담겨있는 상자부터 열어야 하므로 최대 우선순위 큐를 사용하고, PriorityQueue 객체 생성 시 내림차순 정렬을 위해 Comparator.reverseOrder()을 지정한다. 누군가 선물을 가져갔던 상자에서 또다시 가져가도 된다는 점에만 주의하면 된다. 원하는 만큼(n) 선물을 가져간 후(poll) 남은 상자는 다시 정렬에 포함시켜야 하므로(add) 아래와 같이 작성할 수 있다.queue.add(queue.poll()-n); 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Co.. 2024. 8. 24. 이전 1 ··· 3 4 5 6 7 8 9 ··· 22 다음
