Greedy

01 Feb 2022 in Data Structures & Algorithms on Data Structures & Algorithms

Canal of Overschie, Paul Signac

Algorithm is a set of well-defined instructions to solve a particular problem.
It takes a set of input and produces a desired output.

• 1. What is Greedy algorithm?
• 2. Greedy Example Problem
  • 2.1 Problem : Until it becomes 1
  • 2.2 Solution : Until it becomes 1
  • 2.3 Problom : Multiply or Add
  • 2.4 Solution : Multiply or Add

Qualities of Good Algorithms

---

• Input and output should be defined precisely.
• Each step in the algorithm should be clear and unambiguous.
• Algorithms should be most effective among many different ways to solve a problem.
• An algorithm shouldn’t include computer code. Instead, the algorithm should be written - in such a way that it can be used in different programming languages.

1. What is Greedy algorithm?

---

Greedy algorithm means a method to choose only good things from the current situation.

• A typical greedy algorithm requires the ability to come up with minimal ideas to solve a problem.
• It is important to analyze the legitimacy of the greedy solution.
  • Examine whether an optimal solution can be obtained by iteratively selecting the one that looks the best.

In a greedy algorithm problem, it is necessary to be able to come up with a minimal ideas for solving the problem and examine whether this is justified.

2. Greedy Example Problem

2.1 Problem : Until it becomes 1

---

Until a certain number N becomes 1, one of the following two processes is repeatedly selected and performed. However, the second operation can be selected only when N is divisible by K.

1. Subtract 1 from N.
2. Divide N by K.

For example, if N = 17, K = 4
1) 17 - 1 = 16
2) 16 // 4 = 4
3) 4 // 4 = 1

The number of times the entire process is executed becomes 3. This is the minimum number of times to make N equal to 1.

Difficulty: 1 | Solving Time: 15 minutes | Timeout: 2 seconds | Memory limit: 128 MB

Input conditions
In the first line N (2 <= N <= 100,000) and K (2 <= K <= 100,000) separated by spaces, each given as a natural number.

Output conditions
In the first line, print the minimum value for the number of times that one or two processes must be performed until N becomes 1.

Input Example	Output Example
25 5	2

2.2 Solution : Until it becomes 1

---

Since K is greater than 2, dividing by K will always reduce N faster than subtracting 1.
Also, N will always becomes 1.

Dividing as many as possible guarantees an optimal solution!

# title: 'UntilItBecomes1.py'
# Get input with N, K separated by spaces
n, k = map(int, input(). split())
result = 0

while True:
    # Subtract until N is divisible by K
     target = (n // k) * k
     result += (n - target)
     n = target
    # Escape from loop when N is less than K (not more divisible)
     if n < k:
     break
    # Divide by K
     result += 1
     n //= k
 
# Subtract 1 for the last remaining number
reslut += (n - 1)
print(result)

2.3 Problom : Multiply or Add

---

Given a string s where each digit consists of only numbers (0 to 9), check all numbers one by one from left to right, and insert the ‘x’ or ‘+’ operator between the numbers to find the largest number that can be made as a result. Write a program to retrieve it. However, unlike the usual way of calculating x before +, it is assumed that all operations are performed in order from the left.

Difficulty: 1 | Solving Time: 30 minutes | Timeout: 1 second | Memory limit: 128 MB | Previous: Facebook interview

Input conditions
The first line is given a string S of several numbers. (1<=S.length<=20)

Output conditions
Print the largest possible number in the first line.

Input Example 1	Output Example 1
02984	576

Input Example 2	Output Example 2
567	210

2.4 Solution : Multiply or Add

---

In most cases, ‘x’ makes the value larger than ‘+’. For example, 5+6=11 and 5X6=30.

• However, if any of the two numbers is ‘0’ or ‘1’, it is more efficient to perform ‘+’ rather than ‘x’

Therefore, when performing an operation on two numbers, if one of the two numbers is less than 1, ‘+’ it, and if both numbers are 2 or more, ‘x’ is the correct answer.

# title: 'MultiplyOrAdd.py'
data = input()

# Replace the first character with a number
result = int(data[0])

for i in range(1, len(data)):
     # If either number is '0' or '1', '+' rather than 'x'.
     num = int(data[i])
     if num <= 1 or result <= 1:
         result += num
     else:
         result *= num

print(result)

https://www.freecodecamp.org/
https://www.programiz.com/
https://www.geeksforgeeks.org/
https://blog.naver.com/PostList.naver?blogId=ndb796
이것이 코딩테스트다,2020,나동빈,한빛미디어