[TIL] 백준 풀이 정리

※ 시험을 앞두고 Week01주차에 공부했던 알고리즘을 연습한다. ※

1. 완전 탐색 연습 문제  (14888번 - 연산자 끼워넣기)

import sys

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
plus, minus, multiply, divide = map(int, sys.stdin.readline().split())

# sys상 가장 큰수를 저장
resultMax = -sys.maxsize
resultMin = sys.maxsize

'''
count : 현재 접근하는 nums 인덱스
total : 앞의 연산 결과
plus, minus, multiply, divide : 각 연산이 가지고 있는 개수
'''
def dfs(count, total, plus, minus, multiply, divide) :        
    global resultMax, resultMin
    if count == N :
        resultMax = max(resultMax, total)
        resultMin = min(resultMin, total)
        return
    if plus :
        tmp = total + nums[count]
        dfs(count+1, tmp, plus-1, minus, multiply, divide)
    if minus :
        tmp = total - nums[count]
        dfs(count+1, tmp, plus, minus-1, multiply, divide)
    if multiply :
        tmp = total * nums[count]
        dfs(count+1, tmp, plus, minus, multiply-1, divide)
    if divide :
        '''
        // 와 / 의 차이점
        https://gksdudrb922.tistory.com/207 참고
        '''
        tmp = int(total / nums[count])
        dfs(count+1, tmp, plus, minus, multiply, divide-1)

# 맨 앞의 값에 연산자가 들어갈 일이 없으므로 바로 시작
dfs(1, nums[0], plus, minus, multiply, divide)
print(resultMax)
print(resultMin)

• 연산자 // 와 / 의 차이점 (참고 : https://gksdudrb922.tistory.com/207)
  • 기본적으로 / 연산을 수행 결과로 실수형이 나오는 것은 알고 있다. (↔ // 연산 수행 결과 정수형)
  • 문제에서 조건 : 나눗셈은 정수 나눗셈으로 몫만 취한다. → 소수점은 버린다는 의미
  • 위의 조건으로 // 사용하여 문제를 풀면 틀린다.
  • 왜냐하면 양수일 때는 차이가 나지 않지만 음수로 나눌 때는 // 연산자는 결과 값보다 작은 정수 중 가장 큰 정수 도출

import sys

def main() :
    N = int(sys.stdin.readline())
    nums = list(map(int, sys.stdin.readline().split()))
    plus, minus, multiply, divide = map(int, sys.stdin.readline().split())

    resultMax = -sys.maxsize
    resultMin = sys.maxsize
    
    def dfs(count, total, plus, minus, multiply, divide) :        
        nonlocal resultMax, resultMin
        if count == N :
            resultMax = max(resultMax, total)
            resultMin = min(resultMin, total)
            return
        if plus :
            tmp = total + nums[count]
            dfs(count+1, tmp, plus-1, minus, multiply, divide)
        if minus :
            tmp = total - nums[count]
            dfs(count+1, tmp, plus, minus-1, multiply, divide)
        if multiply :
            tmp = total * nums[count]
            dfs(count+1, tmp, plus, minus, multiply-1, divide)
        if divide :
            tmp = int(total / nums[count])
            dfs(count+1, tmp, plus, minus, multiply, divide-1)

    dfs(1, nums[0], plus, minus, multiply, divide)
    print(resultMax)
    print(resultMin)

main()

이 코드는 위의 코드와 살짝 다른 점은 전체 코드를 main() 함수로 감싸줬다.

내가 배운 거는 첫번째 코드처럼 global 키워드를 사용하면 오류가 발생한다는 것이다.

• global : 전역변수에 접근하기 위한 키워드
  • 전역변수는 모든 함수 바깥에서 선언되어 있어야한다.
• nonlocal : 지역변수와 전역변수의 중간쯤 특성을 가진 변수를 위한 키워드
  • 이 변수는 키워드가 선언된 코드 블럭의 바깥 변수와 바인딩된다.
  • 주의할 점은 위의 경우와 같이 함수 안에 함수를 만든 코드 블럭 내에서만 사용가능하고 전역변수에는 접근할 수 없다.

---

2. 재귀 함수 연습 문제 (17478번 - 재귀함수가 뭔가요?)

import sys

N = int(sys.stdin.readline())

def statement(n) :
    print("_"*4*n, end="")
    print('"재귀함수가 뭔가요?"')
    if  n == N : 
        print("_"*4*n, end="")
        print('"재귀함수는 자기 자신을 호출하는 함수라네"')
        print("_"*4*n, end="")
        print("라고 답변하였지.")
        return 
    print("_"*4*n, end="")
    print('"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
    print("_"*4*n, end="")
    print("마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.")
    print("_"*4*n, end="")
    print('그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."')
    statement(n+1)
    print("_"*4*n, end="")
    print("라고 답변하였지.")

print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")
statement(0)

---

3. 순열 구현해보기 (10819번 - 차이를 최대로)

import sys

# 입력받기
N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

# 최종 결과값 저장할 변수
result = 0

# 사용여부를 저장할 배열
used = [0] * N
   
# 순열 생성 함수
def generate(chosen, used):
   global result
   if len(chosen) == N:
      # 현재 리스트의 차이의 합을 저장할 변수
      sum = 0
      for i in range(N-1):
         sum += abs(chosen[i]-chosen[i+1])
      result = max(result, sum)
      return 
   
   # 순열생성
   for i in range(len(nums)):
      if not used[i]:
         chosen.append(nums[i])
         used[i] = 1
         generate(chosen, used)
         used[i] = 0
         chosen.pop()
generate([], used)
print(result)

• 순열 : 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것
• from itertools import permutations : python 내장 함수로 순열을 구해준다.
• 위의 내장함수를 사용하면 금방 풀리지만 공부를 위해 구현해보았다.
  • generate(chosen, used) : 순열 생성 함수
  • 첫번째 부분 : chosen의 길이가 N일 경우 = 새로운 수열 하나 완성 → 원하는 결과값 얻기
  • 두번째 부분 : 순열 생성 재귀 부분

위의 코드에 입력값

chosen의 변화 과정

• 위의 이미지는 chosen의 원소 변화 과정을 앞쪽 일부분만 보여준다.
• 순열을 생성할 때 뒷부분부터 바꿔가면서 순열을 새로 만들어 간다.
• 이러한 방식으로 전체 수열을 구한다.

---

코치님의 말씀을 들으면서 내가 이해했다고 생각하고 그냥 넘어간 문제들도 많을 것같다.
문제에 대해 설명을 할 때 확실하게 설명하는 부분과 아닌 부분을 생각하고 공부할 내용을 알아가야겠다.
그리고 코드를 한번 풀고난 후 2-3일 후에 다시 풀어보는 시간을 가져야겠다. 
일주일동안 문제를 풀고 나름대로 복습을 했지만, 나는 너무 코드 리뷰식으로 한것 같아 아쉽다.
처음인 사람처럼 다시 마음을 다잡고 집중해서 공부하자👩🏻‍💻