그리디 기초 테크닉 익히기2 - 특별한 정렬, 사고 전환, 상쇄, 올바른 순서 부분문자열 몇개 있는지, 원소 상태 바꾸기-

1. 문제1 3216번: 다운로드 (acmicpc.net) 3216번: 다운로드 첫째 줄에, 다운로드 시작하고 몇 초 후에 노래를 듣기 시작하면, 끊김 없이 들을 수 있는지 출력한다. 그러한 시간이 여러개라면, 가장 빠른 것을 출력한다. www.acmicpc.net 2. 풀이 생각보다 어렵더라..? 다운로드 하면서 음악 재생시간을 누적해오고.. 어느 순간에 음악을 재생시키면.. 모든 다운로드 시간을 커버하면서 음악이 연속으로 흐를수 있게 할려면.. 다운로드가 언제 끝나는지 알아야하는데.. 이게 가능한가?? 리스트를 구성하면서 미리 더해서 남은 시간을 구해놓기도 하고.. 그리디의 기본인 정렬을 해서 짧은 시간부터 다운로드 해나가야하나? 생각은 했는데 정해진 순서대로 다운받아야하기 때문에.. 정렬은 할 수 ..

• format_list_bulleted 그리디 알고리즘
• · 2023. 9. 13.
• textsms

제켄도르프 분해 응용 - 정수를 피보나치 수의 합과 차로 표현하기

1. 문제 8229번: Fibonacci Representation (acmicpc.net) 8229번: Fibonacci Representation The Fibonacci sequence is a sequence of integers, called Fibonacci numbers, defined as follows: Fib0=0, Fib1=1, Fibn=Fibn-2+Fibn-1 for n > 1 Its initial elements are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Byteasar investigates representations of number www.acmicpc.net 2. 풀이 어떤 정수를 최소 개수의 피보나치 수만을 사용해서 합과 차로 표현..

• format_list_bulleted 그리디 알고리즘
• · 2023. 9. 13.
• textsms

C++ 알고리즘 기초22 -배열 심화2(최대, 최소 찾기, 정렬하기, 그리디 연습)-

1. 연습문제1 n개의 원소와 q개의 질의가 주어졌을 때 n개의 원소에 대해 각 질의를 수행하는 프로그램을 작성해보세요. 질의의 종류는 다음과 같습니다. 1 a a번째 원소를 출력합니다. 2 a 숫자 a가 있는지를 판단합니다. 만약 있다면 해당 원소가 몇 번째 원소인지를 출력합니다. 숫자 a가 2개 이상 있다면 index가 더 작은 원소를 출력합니다. 만약 a가 없다면 0을 출력합니다. 3 a b a번째 원소부터 b번째 원소까지 순서대로 공백을 사이에 두고 출력합니다. 문제 요구하는대로 구현하면 된다 a번째랑 index가 a인 것은 다르니까 헷갈리지 말고 C++ 특성상 첫 숫자 1,2,3중 하나를 받아 1,2,3인지 체크하고, 1,2면 하나만 더 받고 3이면 2개를 받고 #include using nam..

• format_list_bulleted C++ 기초
• · 2023. 7. 2.
• textsms

다이나믹 프로그래밍+BFS+그리디 - 정확히 K번만에 목표에 도달할 수 있는가?

1. 문제 28069번: 김밥천국의 계단 (acmicpc.net) 28069번: 김밥천국의 계단 첫 번째 줄에 계단 개수에 해당하는 $N$, 계단을 오르는 횟수 $K$가 주어진다. $(1 \leq N, K \leq 1\,000\,000)$ www.acmicpc.net 2. 풀이1 그냥 보면 두가지 행동중 하나를 할 수 있는 전형적인 BFS문제 1) 한칸을 올라간다 2) $\left \lfloor \frac{i}{2} \right \rfloor$만큼 올라간다 0번부터 시작한다고 명시되어 있으니 BFS처럼 풀어보면.. 정확히 K번 행동해야하면서 매 행동마다 queue의 길이만큼 순회시키는데 해당 좌표 i가 i+1과 i+i//2를 이동할 수 있으면 queue에 넣어주고.. K번 행동한 후에 n이 queue에 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 6. 20.
• textsms

그리디 알고리즘 - 효과적으로 겹치는 구간을 하나로 합치는 방법(스위핑 기본)

1. 문제 2170번: 선 긋기 (acmicpc.net) 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 2. 풀이 x와 y 사이 선을 긋는데, 총 얼마만큼 선을 그었는지 구하는 문제 한번 그어진 곳을 또 긋는다고 해서, 중복해서 세지 않는다 어려워보여도 예제를 보고 머릿속으로 생각해보면 생각보다 문제가 간단하다 4 1 3 2 5 3 5 6 7 수직선 위에 1,3을 찍고 그어본다. 그러면 그은 길이가 2인데 이제 2,5를 찍고 그어본다 그러면 총 그은 길이는 4임을 알 수 있는..

• format_list_bulleted 그리디 알고리즘
• · 2023. 6. 9.
• textsms

경이로운 그리디 알고리즘3 -가장 효율적으로 좌우로 이동하는 방법-

1. 문제 1461번: 도서관 (acmicpc.net) 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 2. 풀이 문제를 좀 파악부터 해보면 배열의 원소가 책의 위치이며 0에서 시작해서 이동을 해가지고 m개 이내의 책을 들고 다시 0으로 돌아와서 책을 둔 다음에, 이런 식으로 모든 책을 회수해야할때, 최소 이동거리를 구해라 마지막에 모든 책을 회수할때는 0으로 돌아오지 않아도 된다 ---------------------------------------------------------------------------..

• format_list_bulleted 그리디 알고리즘
• · 2023. 6. 3.
• textsms