해당 글에서는 부등호 문제를 Python을 이용해 풀이하고자 한다. 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 🔷 문제 설명 더보기 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열..
해당 게시글에서는 [백준] 13305 주유소 문제를 해설하고 Python을 이용하여 풀고자 한다. 💡 문제 풀이 13305번 문제는 Greedy에 대한 문제로 각 단계마다 최적의 상황을 선택하여 최종적인 해답에 도달하는 방식의 알고리즘이다. 이 문제에서는 제일 오른쪽 지점에 도달했을 때 기름의 비용이 최소가 되는 것을 원하므로, 각 도시를 지나기 위해 기름의 비용을 계산할 때 상황에 따라 작은 값을 이용하여 계산해야 한다. 만약 앞 도시의 기름의 비용이 뒷 도시의 기름의 비용보다 싸다면, 앞 도시에서 주유하는 것이 비용이 적게 드므로 뒷 도시에서 주유하는 것이 아닌 앞 도시에서 미리 주유해야 한다. 따라서 왼쪽에서 오른쪽으로 순차적으로 이동하면서 최소 비용을 저장하여 (최소 비용)*(각 도시 사이 거리)..
해당 게시글에서는 [백준] 1522 문자열 교환 문제를 해설하고 Python을 이용하여 풀고자 한다. 💡 문제 풀이 1522번 문제는 투 포인터에 대한 문제로 두 개의 포인터를 조절하여 두 포인터가 가리키는 값이 특정한 조건을 만족하도록 하는 방식의 알고리즘이다. 투 포인터 알고리즘 중에서도 두 포인터를 일정한 간격으로 이동하는 슬라이딩 윈도우 알고리즘에 해당한다. 슬라이딩 윈도우인 이유는 아래 문제 해설에서 설명하겠다. 이 문제에서 구하고자 하는 값은 a와 b로만 이루어진 문자열에 대해 a를 모두 연속으로 만들기 위한 최소 교환 횟수이다. 예시를 통해 풀이 방법을 설명하기 전에 다음을 이해하자! 1️⃣ 교환 후 연속된 a 문자열의 길이는 입력된 문자열 속 a의 개수와 같다. 2️⃣ 즉, a의 개수와 동..
해당 게시글에서는 [백준] 12847 꿀 아르바이트 문제를 해설하고 Python을 이용하여 풀고자 한다. 💡 문제 풀이 1522번 문제는 투 포인터에 대한 문제 중에서도 슬라이딩 윈도우 알고리즘 문제에 해당한다. 슬라이딩 윈도우 알고리즘이 된 이유는 다음의 조건 때문이다. 한 번이라도 퇴직한 자를 다시 취직 시키지 않는다.(만약 취직을 한다면, 일을 시작 한 날부터 끝날 때까지 하루도 빠지면 안 된다.) 즉, 준수가 일을 할 수 있는 날(m)이 주어졌을 때 일을 시작한 날(st)로부터 m일 동안 빠짐없이 일해야 한다는 것이다. 따라서 준수가 최대 이익을 얻기 위해선 시작한 날(st)로부터 m일 동안 일했을 때의 이익을 모든 경우에 대해서 구하고 최댓값을 출력해주면 된다. m일이라는 길이가 계속 고정되기 ..
