python

문제https://www.acmicpc.net/problem/2531백준 문제집 - 0x14강 - 투 포인터 알고리즘: 투 포인터, 브루트포스, 슬라이딩 윈도우풀이 문제의 조건을 정리해보면 다음과 같다.최대한 많은 종류의 초밥을 먹어야 함먹을 수 있는 초밥의 갯수는 k개쿠폰은 k개의 초밥과는 별개로 사용할 수 있음마지막 조건 때문에 살짝 헷갈렸었다.벨트 위의 연속된 k개의 초밥과 쿠폰초밥이 붙어있어야 하는 줄 알았는데 아니었다.🟦쿠🟦🟦초1 초2 초3🟦🟦 ← 이런식으로 선택해도 상관없음그냥 쿠폰초밥을 제외하고 선택한 접시가 k개이기만 하면 되는것이다. 또한 원형으로 돌아가는 벨트 위에 놓여있는 "회전" 초밥임을 유의해야한다.따라서 주어진 초밥 대열을 리스트로 저장 후 [:k]만큼을 뒤에 추가해준 ..

문제https://www.acmicpc.net/problem/13144백준 문제집 - 0x14강 - 투 포인터 알고리즘: 투 포인터풀이길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. 각기 다른 숫자로 이루어진 연속된 부분 수열의 갯수를 구하는 문제다.즉, 예제 2처럼 [1, 2, 3, 1, 2]가 주어졌을 경우 가능한 부분 수열은 아래와 같다.# 1개[1]. [2], [3], [1], [2]# 2개[1, 2], [2, 3], [3, 1], [1, 2]# 3개[1, 2, 3], [2, 3, 1], [3, 1, 2]# 4개, 5개는 불가능# 답: 12 위 예제만 보고 set()으로 관리하려 했으나 아래와..

문제https://www.acmicpc.net/problem/2230백준 문제집 - 0x14강 - 투 포인터 알고리즘: 정렬, 투 포인터풀이N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다. 기존 투 포인터 문제들은 left를 첫번째 값..

문제https://www.acmicpc.net/problem/2295백준 문제집 - 0x13강 - 이분탐색 알고리즘: 이분 탐색, 해시를 사용한 집합과 맵풀이N(5 ≤ N ≤ 1,000)개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라.예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다.우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x,..

문제https://www.acmicpc.net/problem/2805백준 문제집 - 0x13강 - 이분탐색 알고리즘: 이분 탐색풀이상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나..

문제https://www.acmicpc.net/problem/16401백준 문제집 - 0x13강 - 이분탐색 알고리즘: 이분 탐색풀이명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막..