Coding Warehouse

This post is quite related with the previous question.

2023.03.21 - [Algorithm] - 백준 15649, 15650 python with Recurion and Backtracking

In 15649 show the result of Combination, this time we just want  a Permutation

Problem #15650

https://www.acmicpc.net/problem/15651

N, M = list(map(int, input().split()))

ans=[]
def dfs():
    if(len(ans) == M):
        print(*ans)
        return
    else:
        for i in range (1, N+1):
            ans.append(i)
            dfs()
            ans.pop()
        
dfs()

Simple note
Dude, we have actually used this algorithm before in problem #15649(almost same isn'it?).

For this particular problem, we don’t need to worry about having duplicates. So we just keep adding a value to our array from the beginning over and over again. That’s why I left the value of index i untouched.

Problem #15651

https://www.acmicpc.net/problem/15652

N, M = list(map(int, input().split()))


ans=[]
def dfs(a):
    if len(ans)==M:
        print(*ans)
        return
    else:
        for i in range(a,N+1):
            ans.append(i)
            dfs(i)
            ans.pop()

dfs(1)

By analyzing the desired output, It’s clear that each subsequent element is always greater than or equal to the previous one. Therefore, we modify the parameter of the recursive function to pass a larger value each time. It’s as simple as that.

https://www.acmicpc.net/problem/15649

This is my code:

N, M = list(map(int,input().split()))

ans =[]
mark = [0 for _ in range(N)]

def dfs():
    if len(ans)==M:
        print(*ans)
        return
    
    for i in range(1, N+1):
        if not bools[i-1]:
            ans.append(i)
            mark[i-1] = 1
            dfs()
            ans.pop()
            mark[i-1] = 0
    
dfs()

Approach

• When encountering the return statement, it implies that the function should backtrack to the starting point.
    → Remove the recently added value and continue the process.
• To avoid visiting the same node again, create a 'mark' list to keep track of visited nodes.
• In the code, the iterator 'i' serves both as an 'index' and 'value'. 
  Be cautious when using 'i' as the index of the 'mark' list.
  
  

https://www.acmicpc.net/problem/15650

This is my code:

N, M = list(map(int, input().split()))

ans =[]
def dfs(start):
    if len(ans)==M:
        print(*ans)
        return
    
    for i in range(start,N+1):
        ans.append(i)
        dfs(i+1)
        ans.pop()
dfs(1)

Approach

• Typically, when an output displays a combination, it implies that the output is closely related to the order of the input range.
• The currently added value is always greater than the previous one.
   == The deeper the recursion, the larger the value required.
• It can be assumed that the index value must increase whenever a recursion occurs.
  
  

Combination? Permutation?

1. Overview

A combination is a subset of elementes from a given set. In combination, we only care about whether an element is inclued in a subset or not. However in Permutation, the order of subset is important. It become a different case as the order of a subset though it has the same elements.  

The number of distinct ways to choose “r” elements from the set of “n” elements can be expressed mathematically with the following formula:

2. Recursive Algorithms to Generate Combination

n Combination r can be divede into two case. First case, we include the first item, then we need to choose " r-1" elements from the remaining  "n-1"items. And second case, when we discard the first item, then we need to select "r" elements out of the remaining "n-1" items.

Now we could implement them into recursive way.

int[] arr = {1, 2, 3};
boolean[] visited = new boolean[arr.length];

for (int r = 1; r<=arr.length, 0, r){
	combination(arr, visited, 0, r)
}

void combination(int[] arr, boolean[] visited, int depth, int r) {
	if(r == 0) {
		for (int i=0; i<visited.length; i++){
        	if(visited[i]){
            	System.out.print(arr[i]+" ");
        	}
        System.out.println();
    }
    if(depth == arr.length) {
            return;
		return;
	}
	} else {
    	//1 incursive happen : include the current item and mark at visited array.
		visited[depth] = true;
		combination(arr, visited, depth + 1, n, r - 1);
        
 		//2 incursive happen : exclude the current item and mark at visited array.
		visited[depth] = false;
		combination(arr, visited, depth + 1, n, r);
     }
}
////////////print//////////////
1
2
3

1 2
1 3
2 3

123
////////////////////////////////

The combination method makes two recursive calls to itself. So the first call include the current element and it lose 1-r , however the second dose not include it. So it has the same r value. And everytime it has recursive call, the depth get +1.  

3. Recursive Algorithms to Generate Permutation

Permutation basically has the similar principle. It is different from the boolean array which we use to check the item's existence. Permutation just recursive the array as much as its depth.

int[] arr = {1, 2, 3};

	permutation(arr, new int[arr.length],  0, 3)
}

void permutation(int[] arr,int[] out, int depth, int r) {
	if(depth == r) {
		for (int i=0; i<visited.length; i++){
        	System.out.print(out[i]+" ");
        	}
        System.out.println();
    	}
	} else {
    	for (int i=0; i<arr.length; i++){
		int[] concatArray = Arrays.copyOf(out, out.length + 1);
        	concatArray[concatArray.length - 1] = arr[i]
		permutation(arr,concatArray, depth + 1,  r);
        }
        

     }
}
////////////print//////////////
1 1 1
1 1 2
1 1 3

1 2 1
1 2 2
1 2 3

1 3 1
1 3 2
1 3 3

2 1 1
2 1 2
2 1 3 

2 2 1
2 2 2
2 2 3

2 3 1
2 3 2
2 3 3

3 1 1
3 1 2
3 1 3

3 2 1
3 2 2
3 2 3

3 3 1
3 3 2
3 3 3

////////////////////////////////

What is Big O Notation?

We need to know how to derive the time complexity of codes. When you have loops, and recursion it might be little tricker to know how their running time or space requirements grow as the input size grows. This Big O notation is a framework to analyze and compare the number of operations of codes.

Basically, Big O notation care about the worst-case in sceneario. For example, when you have to sort elements in array which are in totally reverse order. It will take the most operation to sort them compare to other cases. And the chart show most common orders of growth of algorithms specified in Big O notation. We will find more information about the each case.

O(1) - Constant time complexity

O(1) has comstant operation time to work on. In this case, all the basic operation such as comparision, assignments, and reading a variable are included. When you have 100,000 variables to assign, it take the same time with one variable to assign

O(n) - Linear time complexity

O(n) describe an algorithms whose operation will grow linearly and in propotion to the size of the input data. In this case,

for (int i=0; i<array.length; i++){
	statement1;
	statement2;
}

this example is the case. And if you loop through only the half way of the array, you could think it becomes O(1/2*n). But that is not true and vice versa. It still have the same O(n). 

O(log n) - Logarithmic time complexity

O(log n) basically means time goes up linearly while the n goes up exponentially. An example is binary search tree. Whenever we move from one node to another, the operation's number to find the number become half. If you take 2 seconds to compute 100 elements, then 3 seconds to compute 1000 elements.

O(n²) - Quadratic time complexity

O(n²) represents an algorithm whose operation gorws proportional to the square of the size of the input data set. This is common with codes that involve nested loops statements. 

기본적으로 모든 알고리즘은 기존에 있던 문제를 해결하기 위해 고안되었다.

우리를 괴롭히는 녀석이 아니란 말이지..

What is Dynamic Programming?

다이나믹 프로그래밍이란 DFS, BFS 처럼 어떤 고안된 방법을 따라가는 것이 아니라 경우의 수가 너무 많거나 반복적으로 존재하는 연산과정을 줄여나가기 위한 알고리즘이다. 즉 일종의 최적화 알고리즘이다.

Then how we could distinguish DP from others?

• 보통 DFS나 BFS로 풀 수 있는 문제의 경우의 수 마지노선은 5백만개 정도 인데, 그걸 훠어얼씬 뛰어넘는 경우일 때.
• 각각의 경우의 수 안에 반복적인 연산이 많이 있는 경우

How I get my attitude adjust to DP?

• 어떤 정보를 어떻게 쌓아야 연산횟수를 줄일 수 있을까 에 대하여 고민해야한다.
• 고민은 집중을 하되 30분은 넘지 않도록 해야한다.
• 최대한 다양한 문제를 접하고 소스코드를 보더라도 직접 구현하도록 노력한다.

이하의 내용은 내가 문제를 풀면서 잘못 접근한 것에 관한 개인적 고찰이다

https://www.acmicpc.net/problem/15990

T = int(input())

for i in range(0, T):
    N = int(input())
    
    # 1st problem
    dp=[]
    for i in range(0,11):
        dp.append([])

	# 2nd problem
    dp[1] = ["1"]
    dp[2] = ["2"]
    dp[3] = ["12", "21", "3"]

	# 3rd problem, totally mess up :)
    for i in range(4, N+1):
        
        for j in range(1,i):

            len1 = len(dp[j])
            len2 = len(dp[i-j])

            for k in range(0,len1):
                for l in range (0, len2):
                    if(dp[j][k][-1] != dp [i-j][l][0]):
                        if(dp[i].count(dp[j][k]+dp [i-j][l]) == 0):
                            dp[i].append(dp[j][k]+dp [i-j][l])

    print(sum(dp[N]))

1. 일단 기본적으로 리스트에 빈리스트를 추가해주는 방식의 접근은 좋지 않다. 시간을 더 많이 잡아먹게 된다.
2. 처음엔 정수형으로는 풀이 방식이 존재하지 않는다고 판단을 하였었다. 내눈엔 접근 방식이 보이지 않았거든...
   • 하지만 문제를 푼 시점에서 생각을 해보자면, 문제에서 판단이 되는 근거는 숫자식에서 마지막 숫자만 중요하다는 점이다.
   • 어떤 숫자를 덧셈식으로 표현한다고 했을때, 마지막 숫자자리에 올 수 있는 경우의 수는 1,2,3으로 고정되어 있다
3. 문자형으로 접근을 했기 때문에, 뒤에 새로이 붙게되는 숫자를 일일히 비교하면서 같지않은 경우에 추가해주는 매우 원시적인 접근 방식을 사용했다. ㅠㅠ
   • 마지막 자리에 오는 숫자는 고정되어 있기 때문에,  새로만들 숫자는 중복되는 경우만 피해서 만들어주면 된다.

물론 일일이 비교하는 방식으로 접근했기 때문에, 문제의 의도와 틀렸고 실제 주어진 실행시간도 많이 초과하였다.

그래도 작동은 된다.. ㅠㅠ 새로 풀어서 맞추었지만.. 정답을 올리는 포스팅은 아니기때문에 자세한 내용은 생략

dp = [[0 for _ in range(3)]for _ in range(100001)]

dp[1] = [1, 0, 0]
dp[2] = [0, 1, 0]
dp[3] = [1, 1, 1]


for i in range(4, 100001):
    dp[i][0] =  (dp[i-1][1] + dp[i-1][2])%1000000009
    dp[i][1] =  (dp[i-2][0] + dp[i-2][2])%1000000009
    dp[i][2] =  (dp[i-3][0] + dp[i-3][1])%1000000009
    

T = int(input())  
for i in range(T):
    n = int(input())
    print(sum(dp[n]) %1000000009)