[TIL 2024. 03. 11]

오늘 한 일

• 오늘의 코드카타 10문제
• 오후 알고리즘 세션: stack(2)
• 알고리즘 문제: N과 M(1) 마무리, 연산자 끼워넣기
• 쇠막대기, 바이러스, 1로 만들기, 123 더하기 (복습)
• TIL 작성 

 

오늘의 리뷰

1. N과 M(1)

• 기저조건 => 받은 입력값의 리스트 길이와 M이 같아질 때. 즉, 받은 입력값(숫자)를 모두 사용했을 때가 더 이상 쪼개질 수 없는 기저조건임.
• ==> 기저조건시의 프린트문에서 join은 str을 대상으로 하는 연산이므로, map함수를 이용하면 됨
• 나는 아무래도 보기 편하게 1부터 인덱스를 주는 게 좋음.. 단, 1로 시작할 거라면, 끝은 N+1이어야 한다는 것 주의하기!
• 백트래킹의 핵심 부분이 if문임. 해당 숫자가 ans의 리스트 안에 있는지 확인함으로써, 탐색 대상을 줄일 수 있음
• for문 내: if~not => append.ans() =>재귀 호출 => ans.pop()
• 정리하면, 해당 함수는 기저조건을 만나기 전까지_for문을 계속 돌면서 가능한 조합들을 찾음. append 후에 재귀적으로 함수를 호출하는 것은 (ex. [1, 2])와 같은 조합을 만드는 과정임. 즉, append로 1을 stack에 push하고 새로운 재귀함수를 호출하여 뒤에 2를 붙여서 조합하나를 만들고 print했다가, 다시 pop으로 2를 제거하고 3을 붙여보는 과정..계속..!
• (cf. 파이썬에서의 대표적 stack은 list다~) 

 

2. 연산자 끼워넣기

• 해당 함수의 parameter(매개변수)는 무엇무엇이 필요한가?
• => cum_num(현재까지 계산된 값), num(=depth)를 떠올릴 수 있어야.
• 최댓값과 최솟값을 구해야 하는데, 변수를 어떻게 줘야하는지?
• => 연산자의 계산 결과는 양수로 아주 커질수도, 음수로 아주 작아질 수도 있음
• ==> 따라서 0으로 초기화할 수 없고, import sys를 사용해야 함. 최댓값을 만약 0으로 초기화하면 연산의 결과가 모두 음수로 나왔을 경우에는 최대값이 업데이트되지 않음. 마찬가지로 최솟값을 0으로 초기화하면 연산의 결과값들이 모두 양수인 경우에는 최솟값이 업데이트 되지 않음. 따라서 최댓값은 아주 작게, 최솟값은 아주 크게 초기화해야 함. 그래야 아주 작은 해당 수보다 크면 최댓값이 업데이트 되고, 아주 큰 해당 수보다 작으면 최솟값이 업데이트 됨. 이때의 초기화 시에는 sys.maxsize와 -sys.maxsize를 활용하면 됨.
• 기저조건은 뭐가 되야할까?
• => depth가 N과 같아야.
• 기저조건 충족 전의 조건문은 모두 if를 사용해야 함 => 각각의 연산자는 중복으로 사용될 수 있기 때문임
• 항상 '나눗셈'은 주의! => 해당 문제에서는_'몫'만 사용하므로, int()로 변환 필요.
• 디버깅 모드로 연산자 조합의 변화 과정을 보면..

arr = [1, 2, 3, 4, 5, 6] (++-*/인 경우)

++-*/

++-/*

++*-/

++*/-

++/-*

++/*-

+-+*/

+-+/*

+-*+/

+-*/+

+-/+*

+-/*+

... (총 60가지 <= 6!/2!) (cf. stack: LIFO)

[백준] 14888번: 연산자 끼워넣기 - 파이썬/python

 

3. 완탐/재귀/백트래킹/DFS에 대하여

• 완탐은 재귀, 백트래킹, dfs 등을 통해서 구현될 수 있음.

문과생이 적어보는 백트래킹 (재귀와 DFS 를 곁들인)