(1/10) 문제 이해하는데도 오래걸려서 포기하려고 했던 문제,, 2번 정도 보고 완벽히 아니고 대충 이해가 갔다!
(1/11) 이해 완료~
- 코드:
정답 코드 중에 파이썬이 없어서 자바코드로 먼저 이해했다.
<코드 이해 돕기 위한 설명>
100 200 300으로 정렬한 뒤에 1번 퀘스트를 진행하면 경험치에서 100을 빼주고, 1번을 진행한 상태니까 100을 어딘가에 한번 더해줄 수 있다.(활성화 된 스톤이 1개니까) 그다음 2번 퀘스트를 진행하면 경험치에서 200을 빼주고, 200만큼을 어딘가에 두번 더해줄 수 있다. (활성화 된 스톤이 2개니까) 이제 3번 퀘스트를 진행하면 경험치를 빼줄 필요 없이 300을 어딘가에 두번 더해주면 된다.
< 내가 이해한 코드와 문제 설명>
"예를 들어서 2,3 번째 아케인스톤이 활성화되어있고(2개가 활성화 되어있네! 그럼 해당 퀘스트를 제외하고 다른 아케인스톤에 해당 퀘스트의 경험치를 2번 뿌릴 수 있음) 첫번째 퀘스트를 진행했을 경우, 첫번째 아케인스톤을 획득하고 2,3번째 아케인스톤에 첫번째 퀘스트의 경험치가 쌓이고 첫번째 아케인스톤 경험치는 0이 된다."
즉, 진행한 퀘스트에 따른 아케인스톤 경험치가 0이 되므로 감소되는 경험치를 최소화하기 위해서는 오름차순으로 정렬해주는 것이 맞다. 퀘스트별 아케인스톤 경험치는 다른 아케인스톤에 본인 경험치를 줄 수가 있는데 활성화 개수에 따라 몇번 줄 수 있는지 달라진다. 그리고 경험치를 주면 본인이 가지고 있던 경험치는 0이 되게한다.
import java.util.Arrays;
import java.util.Scanner;
public class TemplateA {
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int quest = scan.nextInt();
int activeS = scan.nextInt();
int [] arr = new int [quest];
for(int i = 0; i < quest; i++) {
arr[i] = scan.nextInt();
}
Arrays.sort(arr);
//오름차순으로 정렬해주어 최대 아케인스톤이 활성화 전까지
//감소되는 경험치를 최소화한다.
int count = 0;
//count는 최대 활성 아케인스톤 값까지 증가할 변수
int exp = 0;
//최대 경험치가 들어갈 변수
for(int i = 0; i < quest; i++) {
if(count < activeS) {
count ++;
//최대 아케인 스톤값이 될때까지 하나씩 더해줌
exp -= arr[i];
//최대 아케인 스톤 값이 되기 전까지는 하나의 경험치가 사라지게
//됨으로 그 아케인 스톤의 경험치를 총경험치에서 빼줌
}
exp += (arr[i] * count);
//이후 활성화된 아케인 스톤의 수와 경험치를 곱해줌
}
System.out.println(exp);
}
}
- 코드 이해 후 파이썬으로 구현
n, act = map(int, input().split())
k = list(map(int, input().split()))
k.sort() # 감소되는 경험치 최소화
cnt, exp = 0, 0
for i in range(n):
if cnt< act:
cnt+=1
exp -= k[i]
exp += k[i] * cnt
print(exp)
t = int(input())
num = 0
for _ in range(t):
k = int(input())
n = int(input())
k0 = [x for x in range(1,n+1)]
for a in range(k):
for b in range(1,n):
k0[b] += k0[b-1]
print(k0[-1])
1. 큰 문제를 작은 문제로 나눌 수 있을 때 - 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤 처리
-> 이 과정에서 메모이제이션(memoization) 사용해야함: 이미 계산한 결과를 배열에 저장
2. 작은 문제로부터 구한 결괏값을 큰 문제에서도 활용 가능
2가지 문제 풀이 방식
1. 상향식(바텀 업) 방식: 가장 작은 문제의 답부터 찾아가는 방식, 반복문 사용
2. 하향식(탑 다운) 방식: 가장 큰 문제부터 시작하여 작은 문제 순으로 답을 찾아가는 방식, 재귀 함수 활용
1. 상향식(바텀 업) 방식
# 계산된 결과를 memoization 하기 위해 리스트 초기화
d = [0] * 100
d[0] = 1 # a_1 = 1
d[1] = 1 # a_2 = 1
# 바텀 업 방식: 반복문 활용
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
n = 99
print("fibo({}): {}".format(n, fibo(n)))
2. 하향식(탑 다운) 방식
# 계산된 결과를 memoization 하기 위해 리스트 초기화
d = [0] * 100
# 탑 다운 다이나믹 프로그래밍 기법과 재귀 함수를 활용한 피보나치 수열 구현
def fibo (x):
# 종료 조건 (전달인자가 1 또는 2일 때 1을 반환)
if x == 1 or x == 2:
return 1
# 계산된 결괏값이 존재할 경우 해당 결과값 반환
if d[x] != 0:
return d[x]
# 계산된 결괏값이 존재하지 않을 경우 피보나치 수열의 결과를 반환
d[x] = fibo(x-1) + fibo(x-2)
return d[x]
n = 99
print("fibo({}): {}".format(n, fibo(n)))
- 코드: DP문제는 처음이라,, 되는 확률들의 횟수를 다 따로 저장해서 비교하는 방식으로 해야한다. 머릿속으로는 생각했는데 어떻게 해야할지 아예 감이 안잡혔다ㅠㅠ 상향식 하향식 방식이 있는데 상향식이 더 코드는 이해하기 쉬웠다. DP 알고리즘에 대해서 따로 정리하기!
n = int(input())
cnt = 0
while n>0:
if n%3==0:
n = n//3
cnt+=1
if n==1:
break
if n%2==0:
n = n//2
cnt+=1
if n%2==0:
n = n//2
cnt+=1
if n==1:
break
if n%3==0:
n = n//3
cnt+=1
n = n-1
cnt +=1
print(cnt)
- 정답 코드:
n = int(input())
d = [0] * (n + 1) ## d에 계산된 값을 저장해둔다. n + 1이라고 한 이유는, 1번째 수는 사실 d[1]이 아니고 d[2]이기 때문에, 계산하기 편하게 d[1]을 1번째 인 것 처럼 만들어준다.
print(d)
for i in range(2, n + 1): #11
## 여기서 왜 if 1빼는 방법, 2 나누기, 3 나누기 동등하게 하지 않고 처음에 1을 빼고 시작하는지 의아해 할 수 있다.
## 1을 빼고 시작하는 이유는 다음에 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 어차피 교체되기 때문이다.
## 즉 셋 다 시도하는 방법이 맞다.
## 여기서 if elif else를 사용하면 안된다. if만 이용해야 세 연산을 다 거칠 수 있다, 가끔 if continue, else continue를 쓰는 분도 계신데, 난 이게 편한듯.
d[i] = d[i - 1] + 1
print(d[i])
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1) ## 1을 더하는 것은 d는 결과가 아닌 계산한 횟수를 저장하는 것 이기 때문이다. d[i]에는 더하지 않는 이유는 이미 1을 뺄 때 1을 더해준 이력이 있기 때문이다.
print(d)
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
print(d)
print(d[n])
지난 시간에 이어서 데이터 분석가가 성장하기 위해 필요한 3가지 마인드셋(Mindset)에 대해 이야기해보고자 합니다.
여기서 마인드셋(Mindset)은 하나의 가치관 또는 사고 방식이라고 이해하셔도 좋을 것 같습니다.
성장하는 데이터 분석가는 1. 분석적 사고(Analytical mindset) 2. 문제-해결 논리(Problem-solving logic) 3. 의사소통 (Communicational skill) 이 3가지를 갖추어야 합니다.
그럼 두번째 문제-해결 논리에 대해 이야기 해볼까요?
[2] 문제-해결 논리
긴 역사에서 알수 있듯, 인간은 항상 새로운 문제를 찾아내고 그 것을 해결하기를 원합니다. 그리고 현대 사회에서 문제를 해결하는 주체는 대부분 기업들이였습니다. 그 이유는 자본주의 시장에서 가장 많은 고객을 확보할수 있는 방법은 (a.k.a 가장 돈을 많이 벌수 있는 방법은) 가장 빠르게 고객이 느끼는 문제점을 찾고 누구보다 빠르고 효율적으로 해결하는 것이기 때문입니다.
특히 21세기에 들어, 고객의 문제를 찾고, 또 어느 부분을 해결해주어야 고객이 만족할지를 알려주는 데이터 분석 기법이 비즈니스에서 널리 활용되기 시작했습니다.
대표적인 예시를 들어볼까요? - 코홀트 분석 - 퍼널 분석 - RFM 분석
데이터 분석가라면 많이 들어본 이 3가지 분석 기법은 특정 고객이 어느 부분에서 불편을 느끼고 어떻게 행동하는지를 알려주는 대표적인 분석 기법으로 자리잡았습니다.
이 분석 기법들의 공통점은 1. 고객이 느끼는 문제점을 데이터를 통해 찾아낸다 2. 어느 단계에서 문제가 있는지를 근거를 제시한다 3. 어떻게 문제를 해결할수 있을지 해결책을 제안한다 입니다.
대부분의 데이터 분석은 근본적으로 이러한 구조를 따르고 있습니다. 물론 미래를 예측하거나 보유하는 자원을 어떻게 잘 활용할지 다루는 분석도 존재합니다. 하지만 고객의 문제를 해결하는 것이 기업의 근본적인 특징이기 때문에, 많은 기업들이 문제-해결 능력을 활용하는 분석을 선호합니다.
-> 일단 dfs/bfs의 개념부터 알아가느라 정답을 먼저 보고 고민을 해봤다. 문제는 이해가 갔는데 정답 코드를 봐도 왜 저렇게 배열을 만드는지 이해가 안간다.. (12.28) -> 이해 완료!
import pandas as pd
import sys
n = int(input())
tree = [[] for _ in range(n+1)] # 빈 배열 생성
parent = [-1]*(n+1)
for _ in range(n-1):
a, b = map(int, input().split())
tree[a].append(b)
tree[b].append(a)
def dfs(n):
for i in tree[n]:
if parent[i] == -1:
parent[i] = n
dfs(i)
dfs(1)
for i in range(2, n+1):
print(parent[i])
--> tree의 배열을 보면 이런식으로 결과가 나오는데 각 노드 순서별로 어떤 노드와 연결되어있는지 나타내는 배열이다!
예) 0번 노드는 공백, 1번 노드와 연결된 노드는 4,6, 2번 노드와 연결된 노드는 2, 3번 노드와 연결된 노드는 5,6
