Algorithm/백준42

• 

  백준 - 순회강연 문제 설명 강연날짜를 잡아 최대 수익을 얻을 수 있을 값은 무엇인지 구하는 문제이다. 단, 강연은 하루에 한번만 가능하다. 풀이 우선순위에 이익이 큰 순서대로 담고 현재 마감일자를 기준으로 강의를 담아낼 수 있는지 체크한다. 마지막 날짜에 최대한 큰 이익을 낼 수 있는 강의를 하는 것이 최대 수익을 얻을 수 있다. 만약 같은 데드라인을 가지게 되고 2번쨰로 큰 수익구조를 가지고 있다면 데드라인 -1 을 하며 강연이 비어있는 곳을 찾아낸다. 수익구조가 많으면 최대한 마감날까지 Lazy하게 미뤄야 최대 수익 구조를 가질 수 있게 된다. static class Node implements Comparable{ int profit,deadLine; public Node(int profit, int deadLin.. Algorithm/백준 2023. 5. 2.

• 

  백준 - 문제집 문제 설명 가장 쉬운 문제부터 풀수 있는 과정을 출력하는 문제이다. 단, 문제마다 먼저 풀어야 하는 문제를 모두 풀어야 다음 문제를 풀어야 한다. 주의사항 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 이점을 생각하면 낮은 번호의 문제부터 풀어야 하므로 일반 큐가 아닌 우선순위 큐를 이용해야 한다. 풀이 public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(reader.read.. Algorithm/백준 2023. 4. 30.

• 

  백준 - 가운데를 말해요 문제 설명 숫자를 입력 받을 때마다 중앙에 위치한 값을 출력하는 문제이다. min, max Heap 을 이용한다. maxHeap에는 작은 수를 min힙에는 큰 수를 넣어준다. (이름과 반대로 된 value들을 집어넣어준다.) 이렇게 minHeap에는 큰 값이 뒤로 밀려나고 maxHeap에는 작은값이 뒤로 밀리게 되면서 중앙값을 minHeap의 머리 또는 maxHeap 머리에 위치하게 된다. 그러면 이제 두 힙중에 어떤게 중앙값인지 선별해야 한다. 두 heap size()를 고르게 분포하기 위해 같은 Heap 사이즈를 갇는다면 max힙으로 몰아준다.(min으로 몰아줘도 상관없음) maxHeap이 더많다면 minHeap으로 이동한다. 이렇게 되면 maxHeap으로 이동한 혹시모를 큰수가 maxHeap에 머리.. Algorithm/백준 2023. 4. 29.

• 

  백준 - 죽음의 비 문제 설명 격자가 주어지고 출발지에서 도착지 까지는 체력이 소모된다. 출발지에서 도착지 까지 체력이 0이 되지 않으면서 가장 빠르게 이동하는 횟수를 구하는 문제이다. 출발지에서 도착지까지 해당 격자 공간안에 우산이 주어지면 우산의 내구성을 얻어 체력이 1씩 감소되는 경우를 우산으로 대체할 수 있다. 주의사항 일반 방문 T/F처리로는 목적지까지 온전히 갈수없다. 왜냐하면 빠르게 가는 것보다 체력이 도착지까지 0이 안되는 경우가 더 우선순위이기 때문이다. TRY DFS, 맨헤튼 거리를 통한 BFS 탐색 [FAIL] 방문 배열을 int로 선언한 현재 체력+우산의 내구도에 대한 흔적을 남기고 진행하기 이렇게 되면 가장 먼저 빠르게 목적지 인근에서 체력이0이 된 경우에도 뒤에 있는 노드들은 계속 진행할 수 있다... Algorithm/백준 2023. 4. 25.

• 

  백준 - 좋은 수열 문제 설명 숫자 1,2,3으로만 N길이의 좋은 수열을 만들 수 있는 수열중 가장 작은 수를 반환하는 문제이다. 여기에서의 좋은 수열은 인접한 두 개의 부분수열이 동일하지 않는 수열이다. 그리고 나쁜 수열은 인접한 두 개의 부분수열이 동일한 경우의 수열이다. ex) 33 32121323 123123213 주의사항 길이가 n자리를 만드는 것에 유념해아햔다. int 또는 long 형의 타입도 커버할 수 없다. 인접한 길이의 부분 수열 로직을 잘 작성해야한다. 앞자리에서 시작하는 부분 수열만을 체크하는 것이 아니라 중간 부분에서 시작한 부분수열에도 동일한 수열이 존재하면 그것은 나쁜 수열로 인식해야 한다. 풀이 static int n; static int arr[] = {1, 2, 3}; public stati.. Algorithm/백준 2023. 4. 25.