그리디 검색 결과

해당 글 18건

알고리즘 풀이 - 백준 12015(가장 긴 증가하는 부분 수열 2, 그리디(Greedy))

관련글 관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 가장 긴 증가하는 부분 수열(LIS) 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 가장 긴 증가하는 부분 수열의 길이를 구하는 문제 2. 풀이 이 문제는 가장 긴 증가하는 부분 수열(LIS) 관련 포스팅을 참고하면 됩니다. 관련 포스팅은 여기를 참조 해당 포스팅에 모든 내용을 정리하였습니다. 다만, 이 문제의 경우, N의 크기가 백만으로 크기 때문에 단순 2중 반복문으로 해결 시, 시간 초과가 발생합니다. 따라서 위 포스팅의 가장 마지막 부분을 참고하여 O(nlogn)으로 해결할 수 있는 방법으로 풀어야 합니다. 3. 코드 아래의 코드를 통해 정답을 알아보자. import ja..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 13. 20:58

알고리즘 풀이 - 백준 2109(순회강연, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 N개의 대학에서 d일 안에 강연 시 p만큼의 강의료를 지불할 때, 가장 많은 돈을 벌도록 순회강연을 하는 경우, 그 강의료의 최대값을 구하는 문제 2. 풀이 이 문제는 초반에 잘못 이해하여 너무 쉽게 풀고자 했다. 각 강연은 d일 안에 와서 하는 것이므로 반드시 d일에 하는 것이 아니라 1일 후 부터 d일 후 중 하루를 골라 진행하면 된다. 풀이 방법은 다음과 같다. ① 우선 각 강의의 정보를 저장하는 별도 Class를 생성하여 강의 정보를 저장한다. ② 강의들을 강의료를 많이 주는 순서대로 정렬한다.(즉, 강의료 기준 내림차순 정렬) ③ 강의료가 높은 강의부터 시작..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 13. 20:51

알고리즘 풀이 - 백준 1202(보석 도둑, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 N개의 보석 중 가방에 넣을 수 있는 최대 K개의 보석을 훔치고자 한다. 각 가방의 최대 담을 수 있는 무게는 C라고 할 때, 각 가방에 1개씩 넣어 최대로 훔칠 수 있는 보석의 가격을 구하는 문제 2. 풀이 보석이 최대 N개인데 N은 최대 1백만, 가방은 최대 K인데 30만개 이다. 각 가방마다 보석을 넣으려면 단순 2중 반복문을 수행하여 진행하게 되는 경우, 무조건 시간 초과가 발생한다. 따라서, 이 문제는 시간 초과가 발생하지 않도록 우선순위 큐를 이용하여 문제를 풀어야 한다. 우선순위 큐 포스팅은 여기를 참조 이 문제는 단순하게 각 가방에 들어갈 수 있는 모든..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 13. 20:29

알고리즘 풀이 - 백준 1285(동전 뒤집기, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxN 행렬로 동전이 앞 뒤로 놓여 있는 경우 1회 연산에 1행 또는 1열의 N개 동전을 모두 뒤집을 수 있을 때, 뒷면이 위를 향하는 동전의 개수를 최소로 하는 연산의 수를 구하는 문제 2. 풀이 각 동전은 행 또는 열을 바꿀 때, 그 결과가 바뀔 수 있다. 즉, 모든 동전은 2번의 변환이 가능하다. 따라서 접근 방식은 다음과 같다. 3x3 크기의 행렬로 동전이 있다고 가정하자. 그러면, 행을 바꾸는 경우는 아래와 같이 총 7가지가 있다. ① 모든 행을 바꾸지 않는 1가지 ② 모든 행을 다 바꾸는 1가지 ③ 2개의 행을 골라 바꾸는 3가지 ④ 1개의 행을 골라 바꾸..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 12. 22:56

알고리즘 풀이 - 백준 2138(전구와 스위치, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 N개의 스위치와 전구가 있을 때, 각 전구는 켜지거나(1) 꺼지거나(0)의 2가지 상태를 가지고 스위치를 누르면 자기 자신과 양 옆 스위치의 상태가 변할 때, N개의 전구를 특정 상태로 만들기 위해 눌러야 하는 스위치의 최소 횟수를 구하는 문제 2. 풀이 행렬 관련 문제와 유사하다.(관련 포스팅은 여기) 각 전구는 켜지거나 꺼지거나의 경우 뿐이므로 좌측 부터 체크하여 목표 상태와 값이 다른 경우 스위치를 눌러 주는 방식으로 해결이 가능하다. 그런데, 이 문제에서는 스위치를 누르면 자신 보다 좌측(이전) 위치에 있던 전구 또한 영향을 받기 때문에 가장 좌측의 있는 전구..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 12. 22:27

알고리즘 풀이 - 백준 1080(행렬, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 0 또는 1로만 이루어진 행렬 A, B가 있을 때, A를 B로 바꾸는 데 필요한 최소 연산의 횟수를 구하는 문제로, 연산은 전체 행렬의 3x3의 부분 행렬을 0이면 1로, 1이면 0으로 모두 바꾸는 것이다. 2. 풀이 각 행 / 열의 모든 위치는 0 또는 1이다. 즉, 기존에 1이었다면 바꾸거나 바꾸지 않거나의 경우로 나뉠 수 있다. 접근 방법은 다음과 같다. 우리는 A → B 행렬로 무조건 변환해야 한다. 따라서 최소의 연산을 통해 변환하려면 서로 다른 부분이 있는 경우에만 연산을 수행하면 된다. 예를 들어 5x5 크기의 A 행렬이 있다고 가정하자. 그러면 각 행/..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 12. 21:59

알고리즘 풀이 - 백준 11399(ATM, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 1대의 ATM에 N명의 사람이 줄을 섰을 때, m번째 사람이 돈을 인출 시 걸리는 시간은 Pm이라고 하면 모든 사람이 대기 시간을 합쳐 모두 돈을 인출 시에 걸리는 최소의 시간을 구하는 문제 2. 풀이 이 문제는 그리디로 해결 가능한 제일 쉬운 수준의 문제이다. 전체 대기 + 인출까지 모든 인원이 수행할 수 있도록 합이 최소가 되려면 뒤의 사람이 걸리는 시간이 최소가 되어야만 한다. 예를 들어 아래를 보자. 인원이 3명이 있을 때, 각 인원이 인출 시 걸리는 시간은 다음과 같다. 사람 3명 - 10, 6, 4 그러면, 오래 걸리는 사람이 앞에 있으면 뒤의 사람들은 대..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 11. 15:45

알고리즘 풀이 - 백준 1931(회의실 배정, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 회의실이 1개일 때, N개 회의에 대한 사용표를 만들고자 한다. 회의의 시작/종료 시간이 주어질 때, 겹치지 않도록 회의실을 쓰는 최대 회의의 수를 구하는 문제 2. 풀이 이 문제는 대표적인 그리디 알고리즘으로 해결 가능한 활동 선택(Action Selection) 문제이다. 최대한 많은 회의를 수행하기 위해서는 끝나는 시간을 기준으로 정렬을 수행하면 된다. 왜냐하면, 무조건 일찍 끝나는 회의를 우선 수행한 뒤, 다음 회의들을 수행하면 가장 최대의 회의를 진행할 수 있기 때문이다. 즉, 시간이 겹치지만 않는다면 무조건 더 빠르게 끝나는 회의를 우선적으로 수행하고 이후..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 11. 15:23