https://ksbgenius.github.io/linux/2021/01/13/apt-apt-get-difference.html

https://probe29.tistory.com/47

https://www.youtube.com/watch?v=-zQ-7hLBBc4&ab_channel=%EC%98%A8%EB%9D%BC%EC%9D%B8%EC%BD%94%EB%94%A9%EC%8A%A4%EC%BF%A8%EC%BD%94%EB%93%9C%EC%9E%87 

https://eunjinii.tistory.com/4

https://nyangnyangworld.tistory.com/23

https://velog.io/@jnine/%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%ED%8A%B9%EC%A7%95-%EB%B0%8F-%EC%9E%A5%EB%8B%A8%EC%A0%90-%EC%A0%95%EB%A6%AC

https://ryusae.tistory.com/7

https://mangkyu.tistory.com/96

14888_연산자 끼워넣기 (Python)

0. 출처

• 유형 : 백트래킹 (silver 1)
• 링크 : 14888번: 연산자 끼워넣기

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

'''
1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>
'''

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

# 백트래킹 (Python3 통과, PyPy3도 통과)
import sys

N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))  # +, -, *, //

maximum = -1e9
minimum = 1e9


def dfs(depth, total, plus, minus, multiply, divide):
    global maximum, minimum
    if depth == N:
        maximum = max(total, maximum)
        minimum = min(total, minimum)
        return

    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
    if minus:
        dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)


dfs(1, num[0], op[0], op[1], op[2], op[3])

print(maximum)
print(minimum)

(4) 정리

(5) 참고

참고 풀이

14712_넴모넴모 (Easy) (Python)

0. 출처

• 유형 : 백트래킹 (silver 1)
• 링크 : 14712번: 넴모넴모 (Easy)

1. 기록

• 22/04/04 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
2 2

- 예제 출력 1 -
15

- 예제 입력 2 -
2 3

- 예제 출력 2 -
57

- 예제 입력 3 -
3 5

- 예제 출력 3 -
22077

(3) 코드

import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[0] * (m + 1) for _ in range(n + 1)]
answer = 0


def dfs(cnt):
    global answer
    if cnt == n * m:
        answer += 1
        return

    x = cnt // m + 1
    y = cnt % m + 1

    dfs(cnt + 1)
    if graph[x - 1][y] == 0 or graph[x][y - 1] == 0 or graph[x - 1][y - 1] == 0:
        graph[x][y] = 1
        dfs(cnt + 1)
        graph[x][y] = 0


dfs(0)
print(answer)

(4) 정리

문제 가지수가 왜 저렇게 나오나 해서 직접 그려보았다.
넴모넴모가 없는 경우까지 count 해주면 출력값이랑 똑같이 나온다.

힌트를 나중에 봤는데 각 칸 별로 넴모가 있는 경우 없는 경우로 경우의 수를 계산하면
넴모가 4격자를 채우는 경우를 포함한 모든 경우를 좀 더 빨리 구할 수 있긴하다.
문제풀이 방식은 힌트를 기초하여 풀은 방식이다.

풀이 방법을 이해하는데 한참걸렸다.
우선 각 칸을 1로 차례차례 채우며 cnt를 증가시킨다.(넴모를 둔다는 의미)
만약 해당 칸에 넴모를 둬서 2x2 격자넴모가 완성되는 경우는 1을 두지 않고 0으로 남긴채로 cnt를 증가시킨다.
그리고 다시 나머지 칸을 채운다.
전체 격자 수만큼 cnt가 채워진 경우 answer를 1증가시킨다. (answer는 문제 조건에 맞게끔 칸이 채워진 경우를 의미)

# 2 x 3 의 격자의 경우 맨 처음에 이렇게 넴모가 채워진다.
# graph[1][1] 에 넴모(1)를 채우면 문제 조건에 만족하지 못하므로 이 경우는 건너뛰고 cnt만 증가시켜 진행한다.
1 1 1
1 0 1

# 그 다음 이런 식으로 graph[1][2]에 넴모를 제외한 식으로 확인하고
1 1 1
1 0 0

# 그 다음은 이렇게 graph[1][0] 에 넴모를 제외하고 그 뒤에 넴모를 채우는 방식으로
1 1 1
0 1 0

이렇게 해당 칸에 넴모를 넣는 경우와 빼는 경우를 문제에서 주어진 조건에 맞게끔 채우는 경우를 백트래킹 방식으로 반복한다.

(5) 참고

참고 풀이
이해잘되는 풀이

16987_계란으로 계란치기 (Python)

0. 출처

• 유형 : 백트래킹 (silver 1)
• 링크 : 16987번: 계란으로 계란치기

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

'''
1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>
'''

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3
8 5
1 100
3 5

- 예제 출력 1 -
3

- 예제 입력 2 -
3
1 100
8 5
3 5

- 예제 출력 2 -
2

- 예제 입력 3 -
1
123 45

- 예제 출력 3 -
0

- 예제 입력 4 -
8
222 117
176 92
287 6
284 81
221 96
263 96
188 40
225 1

- 예제 출력 4 -
4

- 예제 입력 5 -
6
65 281
272 145
233 175
229 12
99 88
142 159

- 예제 출력 5 -
6

(3) 코드

import sys

def check(eggs):
  count = 0
  for egg in eggs:
    if egg[0] <= 0:
      count += 1
  return count

def dfs(index, eggs):
  global answer

  if index == n:
    # 마지막 계란 까지 집은 경우
    answer = max(answer, check(eggs))
    return

  if eggs[index][0] <= 0:
    # 현재 계란의 내구도가 다 달았을 때 다음 계란으로 넘어간다.
    dfs(index + 1, eggs)

  else:
    # 현재 계란의 내구도가 남아있을 때 다른 계란들과 부딪친다. (현재 계란 제외, 내구도가 없는 계란 제외)
    is_all_broken = True
    for i in range(len(eggs)):
      if index != i and eggs[i][0] > 0:
        is_all_broken = False
        eggs[index][0] -= eggs[i][-1]
        eggs[i][0] -= eggs[index][-1]
        dfs(index + 1, eggs)
        eggs[index][0] += eggs[i][-1]
        eggs[i][0] += eggs[index][-1]

    # 모든 계란이 깨져있는 경우 dfs를 바로 빠져나와준다.
    if is_all_broken:
      dfs(n, eggs)

n = int(input())
eggs = []
answer = 0
for _ in range(n):
  eggs.append(list(map(int, input().split())))

dfs(0, eggs)
print(answer)

(4) 정리

예제 입력1 과 예제 입력2 의 결과가 왜 같은지 이해가 안되서 엄청 헤맸다.
처음에 모든 경우의 수로 다 쳐본다고 생각하고 시작했던게 이유였다.

• 무조건 가장 왼쪽(처음)의 깨지지 않은 계란을 먼저 들고 계란 치는 행위를 시작한다.(이때 어느걸 먼저 치던지 상관없다.)
• 경우1) 들었던 계란이 깨진 경우 깨지지 않은 다음 계란을 들고 계란 치는 행위를 반복한다.
• 경우2) 들었던 계란으로 다른 계란을 쳤는데 다른 계란이 깨지지 않은 경우 다음 계란을 들고 계란치는 행위를 반복한다.
• 모든 계란이 깨진 경우 종료한다.
• 마지막 계란을 들었을 경우도 종료한다.

(5) 참고

참고 풀이
이해가 쉬운 풀이