전체 글 검색 결과

해당 글 200건

알고리즘 풀이 - 백준 2875(대회 or 인턴, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 2명의 여학생과 1명의 남학생이 팀을 결성해 대회에 나가고, K명의 인원은 반드시 인턴쉽게 참여해야할 때, 여학생 수 N, 남학생 수 M명이 있는 경우, 인턴쉽 인원을 제외하고 최대의 팀을 결성할 수 있는 수를 구하는 문제 2. 풀이 난이도가 매우 낮은 그리디 문제이다. 여학생은 2명씩 팀을 맺어야 하니 최대로 팀을 맺을 수 있는 여학생의 경우는 n/2 팀이 가능하다. 남자는 1명씩이므로 최대 m개의 팀이 가능하다. 이 중 더 작은 수로 팀을 우선 결성 시킨 뒤, 남는 여자/남자의 인원 수를 합하여 인턴쉽에 보내야 하는 인원에서 제한다. 그리고 1개 팀은 3명이 구성..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 14. 21:50

알고리즘 풀이 - 백준 1744(수 묶기, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 길이가 N인 수열이 주어질 때, 수열의 두 수를 묶는 경우 곱셈을 하고 나머지는 덧셈을 할 때, 각 수는 두개씩 묶이거나 묶이지 않을 수 있다면 그 합이 최대가 되는 결과를 구하는 문제 2. 풀이 2개의 숫자를 곱하는 경우가 가능할 때, 숫자가 가장 커지는 합을 구하는 방법은 다음의 규칙을 따른다. ① 0 또는 음수는 가장 작은 수 2개를 곱해서 양수로 만들면 제일 큰 경우가 된다. ② 1은 다른 수와 곱하면 1을 낭비하게 되므로 그냥 덧셈 처리한다. ③ 1보다 큰 양수는 가장 큰 수 2개를 곱하면 제일 큰 경우가 된다. 위의 규칙을 활용하여 수를 입력 받을 때, 음..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 14. 21:33

알고리즘 풀이 - 백준 1541(잃어버린 괄호, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 +, - 또는 0~9까지의 최대 5번 이어진 숫자로만 이어진 방정식이 있을 때, 괄호를 적절히 넣어 최소값이 되는 경우의 결과를 구하는 문제 2. 풀이 아래의 예시를 보자. 1 + 2 - 3 + 4 - 5 + 6 + 7 + 8 - 9 + 10 위의 식에서 최소값이 되게 하는 경우는 다음과 같이 괄호를 지정했을 때이다. 1 + 2 - (3 + 4) - (5 + 6 + 7+ 8) - (9 + 10) 즉, 최소값이 되기 위해서는 -기호 이후에 차감을 하는 숫자가 최대한 커지도록 해야 한다. 따라서 - 이후에는 +로 연산되는 모든 숫자를 더하고 그 뒤에 빼주는 방식으로 저장..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 13. 22:35

알고리즘 풀이 - 백준 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