알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 검색 결과

해당 글 17건

알고리즘 풀이 - 백준 1201(NMK, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 1~N 수를 한 번씩 이용해서 LIS와 길이가 M이고, LDS의 길이가 K인 수열을 구하는 문제 2. 풀이 이 문제는 난이도가 높아 풀기가 꽤 어렵다. 우선, M, K의 길이로 LIS / LDS를 하나의 수열에서 만들어야 하는데 M과 K가 어떻게 주어지느냐에 따라 만들 수 있거나 만들 수 없는 경우가 있다. 그 조건부터 살펴보자. 결론부터 말하자면 그 조건은 다음과 같다. $M+K-1 \leq N \leq M*K$ 우선 좌측 조건 부터 살펴보자. 왜 N이 M+K-1보다 크거나 같아야 할까? 이 부분은 M과 K 길이를 지정했을 때, 가장 그 값을 최대한 크게 지정한 것..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 19. 20:22

알고리즘 풀이 - 백준 12904(A와 B, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 A와 B로만 이루어진 영단어가 있을 때, 영단어 S를 T로 바꿀 수 있는 지 없는 지 구하는 문제 2. 풀이 영단어 T를 다시 S로 만들 수 있는지를 체크하면 문제를 해결할 수 있다. 우선, 영단어 T를 분해하여 각 문자를 Deque 자료구조에 넣어 양 방향에서 뺄 수 있도록 구현한다. 그리고 현재 가장 마지막에 추가된 문자가 어느 위치인지를 체크할 수 있도록 별도의 변수를 만든다. 이를 통해 T → S로 변환하기 위해 어떤 문자를 제외해야 할지를 알 수 있다. 예를 들어, back=1이면, 다음에 뺄 문자는 앞쪽에 있다는 의미이며, back=-1이면 다음에 뺄 문자..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 18. 01:31

알고리즘 풀이 - 백준 12970(AB, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 N, K가 주어질 때, 아래 조건을 만족하는 문자열 S를 구하는 문제 - 문자열 S의 길이가 N이고 'A', 'B'로만 이루어져있다. - S에는 $0 = 0; j--){ // A의 개수를 각 위치에 놓는다. for(int a=i; a >= 0; a--){ // 현재 위치한 B의 앞에 A를 놓는데 // A*B가 temp보다 작은 경우에는 A는 a개 만큼 위치하고 B를 하나만 우선 놓는다. if(temp > a*j){ temp -= a*j; for(int t=0; t < a; t++){ sb.append("A"); cnt++; } sb.append("B"); cnt++;..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 18. 01:23

알고리즘 풀이 - 백준 1783(병든 나이트, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 병든 나이트가 NxM 크기의 체스판을 여행 방문할 수 있는 최대의 수를 구하는 문제 2. 풀이 나이트가 병이 많이 들었는지 아래와 같은 방식으로만 체스판 위에서 움직일 수 있다. 기본적으로 오른쪽으로만 갈 수 있는데, 높이 또한 제대로 주어지지 않으면 이동 또한 제한이 걸린다는 것을 알 수 있다. 이 문제는 다음과 같이 풀 수 있다. 이 내용을 직접 그려가면서 해보면 쉽게 이해할 수 있다! ① 높이(세로) 또는 너비(가로)가 1인 경우에는 현재 위치에서 절대 움직일 수 없다. ▶ 첫 위치 하나만 방문 가능하다. ② 높이(세로)가 2라면 2가지 방향(1상 2우, 1하 ..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 18. 00:54

알고리즘 풀이 - 백준 10610(30, 그리디(Greedy))

관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 최대 100,000개의 숫자로 이루어진 숫자 N은 0으로 시작하지는 않을 때, 30의 배수가 되는 가장 큰 수를 만들어 출력하는 문제 2. 풀이 문제를 잘 이해하자. 100,000까지의 숫자가 아니라, 100,000개의 숫자이다. 즉, 1~9까지의 숫자가 최대 100,000개 있을 수 있다는 의미이다. 당연히 단순 반복문을 통해서 30으로 나누어떨어지는 지 등을 구해서 해결할 수는 없다.(숫자가 너무 큰 데다가, 시간도 오래 걸림) 간단하게 생각해보자. 30으로 나누어 떨어지려면 어떻게 해야 할까? 30은 소인수 분해를 하면 2 x 3 x 5 가 된다. 여기서 2 x..
알고리즘 풀이(Problem Solving)/그리디(Greedy Algorithm) 2021. 4. 18. 00:18

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