.png&blockId=3197e115-ee0d-4d9c-9f5d-4b57cb28634e)
•
회의 날짜: 2022/12/27
•
회의 장소: discord 라운지
•
참석자: 김솔배, 구연지, 안지영
[회고 사진]
[문제]
[이번 스터디 공부한 내용]
김솔배
•
문제의 접근방법을 못찾다가 지난 스터디때 풀었던 부분수열의 합과 문제가 비슷하다는것을 깨달아서 다시 부분수열의 합을 찾아보았다.
부분수열의 합 코드
•
Arr의 index(0)가 depth라고 생각하고 하나씩 연산을 해주면 된다고 판단이 되었다.
•
하지만 어떻게 4개의 연산자를 처리할지 갈피를 잡지 못해서 검색을 통해 알아보았다.
•
연산자 배열에서 하나씩 체크하며 조건에 따라 계산하면 답을 구할수 있다.
해결코드 - DFS로 해결
import java.util.Scanner;
public class Main {
static int[] arr;
static int[] skills = new int[4];
static int Max = -100000000;
static int Min = 100000000;
static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int i = 0; i < 4; i++) {
skills[i] = sc.nextInt();
}
Main m = new Main();
m.solution(arr[0], 0);
System.out.println(Max);
System.out.println(Min);
}
private void solution(int sum, int depth) {
// 종료조건
if (n - 1 == depth){
// System.out.println(sum);
if(Min > sum) {
Min = sum;
}
if(Max < sum){
Max = sum;
}
return;
}
for (int i = 0; i < skills.length; i++) {
if (skills[i] != 0) {
skills[i]--;
if (i == 0) {
solution(sum + arr[depth + 1], depth + 1);
} else if (i == 1) {
solution(sum - arr[depth + 1], depth + 1);
} else if (i == 2) {
solution(sum * arr[depth + 1], depth + 1);
} else if (i == 3) {
solution(sum / arr[depth + 1], depth + 1);
}
skills[i]++;
}
/*
* 3
3 4 5
1 0 1 0
* 3 + 4 * 5
* 3 * 4 + 5
* */
}
}
}
Java
복사
구연지
(1) 55, 555, … 처럼 연산자 없이 붙는 경우를 생각해주기
def solution(N, number):
num_dict1 = {}
num_dict2 = {}
digit_list = [11111, 1111, 111, 11, 1]
for i in digit_list:
num_dict1[N * i] = number // (N * i)
number = number % (N * i)
num_dict2[i] = number // (i)
number = number % (i)
print(num_dict1)
print(num_dict2)
num1 = num_dict1[N * 11111] * 5 + num_dict1[N * 1111] * 4 + num_dict1[N * 111] * 3 + num_dict1[N * 11] * 2 + \
num_dict1[N * 1] * 1
num2 = num_dict2[11111] * 5 + num_dict2[1111] * 4 + num_dict2[111] * 3 + num_dict2[11] * 2 + num_dict2[1] * 1
if N == 1:
if num1 + num2 <= 8:
return num1 + num2
else:
return -1
else:
if (num2 == 0):
if num1 <= 8:
return num1
else:
return -1
else:
if (num1 + num2 + 1) <= 8:
return num1 + num2 + 1
else:
return -1
Python
복사
→ 제곱 수로 나타낼 때가 유리한 경우(ex. (4+4)*4 + (4/4) = 31)를 생각해주어야 한다.
(2) 직전 계산을 저장하기 → 연산이 순서대로 이루어지지는 않음
def after_cal(N, before_list1, length):
aft_list = []
aft_list.append(int(str(N)*(length+1)))
aft_list.append(int("1"*(length)))
for num in before_list1:
aft_list.append(num + N)
aft_list.append(num - N)
aft_list.append(num * N)
aft_list.append(num / N)
return aft_list
def solution(N, number):
bef_list = [N]
length = 1
for i in range(1, 9):
if (number in bef_list):
return length
else:
bef_list = after_cal(N, bef_list, length)
length += 1
return -1
Python
복사
(3) 이전에 구했던 숫자를 모두 저장한 후에 꺼내서 쓰기 → 시간 초과 → 해결 중
def after_cal(N, list1, list2, length):
aft_list = []
aft_list.append(int(str(N)*(length+1)))
aft_list.append(int("1"*(length)))
for num1 in list1:
for num2 in list2:
aft_list.append(num1 + num2)
aft_list.append(num1 - num2)
aft_list.append(num1 * num2)
if(num2 != 0):
aft_list.append(num1 / num2)
return aft_list
def solution(N, number):
bef_list = [[N]]
length = 1
for i in range(1, 9):
if (number in bef_list[i-1]):
return length
else:
# 2이면 1: 0,0 ->
# 3이면 2: 0,1/ 1,0 ->
# 4이면 3: 0,2/ 1,1/ 2,0
after_list = []
for j in range(i):
after_list = after_list + after_cal(N, bef_list[j], bef_list[i-j-1], length)
bef_list.append(after_list)
length += 1
return -1
Python
복사
안지영
DP 문제이다. 연산자 우선순위가 존재하기 때문에 앞에서 부터 무작정 계산을 하면 안된다. 따라서 다음의 규칙에 따라 dp에 저장하고 계산한다.
1개 짜리는 [5] 밖에 없다.
2개 짜리는 1개 & 1개로 나타낼 수 있다. 여기에 추가로 이어붙인 숫자를 추가해준다. [5+5, 5-5, 5*5, 5/5, 55]
3개 짜리는 1개 & 2개, 2개 & 1개로 나타낼 수 있다. 여기에 추가로 이어붙인 숫자를 추가해준다.
… 이렇게 8개짜리 까지 for문으로 계산해보고 도중에 목표 숫자가 나타나면 몇개짜린 지 반환해주고, for문을 모두 돌았는데도 목표 숫자가 나오지 않으면 -1을 반환한다.
def solution(N, number):
if(N == number): return 1
dp = [[N]]
for num in range(1,8):
value = [int('{}'.format(N)*(num+1))]
for i in range(1,num+1):
j = num+1-i
for a in dp[i-1]:
for b in dp[j-1]:
value.extend([a+b,a-b,a*b])
if(b!=0): value.append(a//b)
if number in value:
return num + 1
dp.append(value)
return -1
Python
복사
[어려웠던 부분]
•
김솔배DFS문제라는 것을 떠올리기가 어려웠다.
각 연산자들을 어떻게 순서대로 처리할지 떠올리기가 어려웠다.
시간복잡도를 계산하기도 어려웠다.
BFS보다 DFS를 어려워 하는것 같다.
Plain Text
복사
•
구연지Dynamic Programming이라고 떠올리기가 어려웠던 것 같다.
그래서 연산자가 붙어있지 않은 경우를 기준으로 생각했던 것 같다.
또한 모든 경우를 저장해줄 때 계산 시간을 어떻게 줄여주는지를 떠올리는 것이 까다로웠다.
Plain Text
복사
•
안지영우선순위 연산을 어떻게 처리해야할지가 어려웠던 것 같다. 지금까지는 앞에서 부터 계산해서 저장하는 dp
문제들을 주로 풀었었는데, 여기에 추가적인 로직을 해주어야 해서 어려웠다.
Plain Text
복사
[금주의 꿀팁 & 인사이트!]
•
김솔배배열에서 하나씩 무언가를 처리할때는 DFS를 사용할 수 있다는 것을 깨달았다.
DFS를 할때 for문을 이용해 조건들을 추가할 수 있다는 것도 알게 되었다.
Plain Text
복사
•
구연지이전의 경우가 다음 경우에 영향을 미치면 무조건 dynamic programming을 이용해보자!
Plain Text
복사
•
안지영DP! 어떤 값들을 저장해서 어떻게 지속적으로 써먹을 지를 잘 생각하는게 중요하다.
Plain Text
복사
[금주의 느낀 점]
•
김솔배확실히 하나씩 하나씩 연습하다보니 개념들을 점점 알아가게 되는것 같다.
앞으로도 꾸준히 알고리즘공부를 해서 취업할때 알고리즘때문에 못하는 일이 없도록 하자!
Plain Text
복사
•
구연지아직도 Dynamic Programming이 까다롭다 ㅠㅠ
Plain Text
복사
•
안지영문제에 따라 어떤 방법을 쓸지 어떻게 잘 알 수 있을까 아직 갈 길이 먼 것 같다!
Plain Text
복사
