프로그래민👨‍💻

스택을 사용하는 그리디 문제였다. 이 문제는 숫자의 앞에서부터 스택에 집어넣으며 순서를 지키며 가장 큰 수를 만드는 문제이다. 즉 다음과 같은 로직을 가진다. 현재 스택에 집어넣어야할 숫자에 대해서 만일 지울 수 있는 횟수가 남아있고, 스택의 top 값이 현재 숫자보다 작다면 스택의 top을 제거하는 것을 반복하고 현재 숫자를 스택에 push해주는 원리이다. 그후 최종적으로 N-K만큼의 길이를 스택의 bottom에서부터 보여주는 방식으로 해결할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 ..

1931.회의실 배정(링크)과 유사한 그리디 유형의 문제였다. 문제를 마주하였을 때 회의실 배정 문제와 상당히 유사하여 비슷한 방식으로 풀게 되었다. 우선 적으로 모든 회의를 시작 시간 기준으로 우선순위 큐에 넣어 정렬을 하였다. 그 후 현재 가장 빠른 시각에 시작된 회의의 끝나는 시간과 그 바로 다음에 시작하는 회의의 시작 시간을 서로 비교하여, 만일 현재회의 끝시간 > 다음회의 시작시간 이면 회의실을 하나씩 추가하는 방식으로 구현해보았다. 회의실 배정과 다른점은 회의실 배정은 하나의 회의실이기때문에 회의들을 1.끝나는 시간으로 회의정렬, 2. 현재 회의의 끝시간, 다음 회의의 시작시간 비교 이러한 방식으로 풀었지만, 이 문제는 회의실 자체를 늘리는 문제이기에 1. 시작 시간으로 회의정렬, 2. 현재 ..

그리디 하게 접근하여 풀수있는 문제였다. 처음엔 문제를 간단하게 생각하여 내림차순으로 정렬후 두개씩 묶는 방법으로 접근하였는데, 잘 생각해보니 음수에 대해선 오름차순으로 처리하는게 최대값을 출력할 수 있는 것을 알게되었다. 따라서 음수, 양수에 대한 pq를 따로 나누었고, 각 각의 pq에 대해서 2개씩 묶는 방식으로 처리해주었다. 또, 0에 대해서 음수가 홀수개수인경우에 대해서도 예외처리를 해주어야한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60..

이문제는 그리디를 이용하여 풀수있다. 문제를 풀기위해 여러가지 방법을 생각해보았다. +와 -에 대해 우선순위를 주는 방법도 생각해보았는데 구현이 생각보다 쉽지 않았다. 결론적으로 이 문제는 -를 기준으로 - 사이에있는 +와 숫자는 모두 연산해줘도 되는 문제였다. 그래서 우선 -를 기준으로 다 나누고, 모든 연산을 해주었다. 그 이후 맨앞에 것을 제외하고 모두음수로 만들어줄수있는 구성을 만들고 모두 더해주어서 풀 수 있었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 package study5; import java.io.BufferedReader; i..

그리디 알고리즘이다. 정확히 말하면 Interval Scheduling Greedy Algorithm 이다. 시간이 정해진 어떤일을 함에 있어 가장 문제에 따라 가장 최적의 효율을 낼수 있는 방법을 찾는 알고리즘이다. 이 알고리즘은 여러가지로 접근할 수 있다. 1. 일의 소요시간이 가장 짧은 순서로 접근 2. 일의 시작시간이 빠른 순서로 접근 3. 일의 끝시간이 빠른 순서로 접근 이 문제는 3번의 방법인 일의 끝 시간 기준으로 접근하여 보았다. 모든 노드들을 일의 끝시간으로 정렬을 한다음, 맨 처음 것을 선택 그 후 부터 다음에 나오는 노드의 시작점이 현재 노드의 끝점보다 같거나 크다면 선택후 현재 노드를 갱신해주는 방식으로 풀었다. 이와 비슷한 문제로 모든 회의를 수용하기 위해 회의실이 최대 몇개가 필..