천재지변으로 인해 일부 데이터가 유실되었습니다. 입양을 간 기록은 있는데, 보호소에 들어온 기록이 없는 동물의 ID와 이름을 ID 순으로 조회하는 SQL문을 작성해주세요.
JOIN을 얼마나 잘 활용하느냐를 묻는 문제이다.
ANIMAL_INS에는 없고, ANIMAL_OUTS에만 있는 데이터를 찾아달라는 것이다. 따라서, 1번으로 join을 해주는데, inner가 아닌 outer조인을 해줘야 한다. 그럼 어떻게 붙일까. 난 ANIMAL_INS를 Select 문의 from에 썼으므로, right join으로 ANIMAL_OUTS를 붙였다. 그리고 id가 같은녀석들로 붙였으며, 마지막에 where문을 사용하여, ANIMAL_INS.ANIMAL_ID IS NULL 을 조건으로 걸면 outs 테이블에만 있는 녀석들을 찾을 수 있다!
SELECT ao.ANIMAL_ID, ao.NAME FROM ANIMAL_INS ai
right join ANIMAL_OUTS ao
on ao.ANIMAL_ID = ai.ANIMAL_ID
where ai.ANIMAL_ID is null
def solution(n, t, m, p):
answer = ''
tmp=''
num=0
while(len(tmp)<t*m):
tmp+=getover10NotaNum(num,n)
num+=1
for i in range(t):
answer+=tmp[m*i+p-1]
return answer
def getover10NotaNum(num,nota):
ans=""
over="ABCDEF"
if num<nota:
tt=int(num%nota)
if tt>=10:
ans+=over[tt-10]
else:
ans+=str(tt)
else:
while num>=nota:
tt=int(num%nota)
if tt>=10:
ans+=over[tt-10]
else:
ans+=str(tt)
num=num/nota
ans+=str(int(num))
tmp=""
for i in range(len(ans)):
tmp+=ans[len(ans)-i-1]
return tmp
보면, 일단 충분한 만큼 tmp라는 곳에 N진수로 수를 더해가며 구한 문자열을 더해준다. 그리고, 최종적으로 answer에 순서에 맞게 점프점프하며 answer에 문자열을 더해넣어준다. 그러나 위 문제풀이의경우 정답률이 57%에 불과했다. getover10NotaNum()함수가 틀리지는 않았다. 제역할을 충분히 잘 하고있다. 그러므로 잘못된 부분은 마지막에 최종적으로 정답을 만드는 부분이라고 생각된다.
일단 뭐 오늘 새로 풀면서 다시 풀어서 전부 맞추게되었으니.. 아래 코드와 같이 풀었다 .
import sys
sys.setrecursionlimit(1000000)
def solution(n,t,m,p):
def getdiv(n, div):
words = "0123456789ABCDEF"
ans=""
tmp=[]
while n>=div:
tmp.append(words[divmod(n,div)[1]])
n=divmod(n,div)[0]
tmp.append(words[divmod(n,div)[1]])
return ''.join(tmp[::-1])
start=0
tmp = ''
while len(tmp)< (t)*(m+1) :
tmp += getdiv(start,n)
start+=1
answer = ""
idx = p-1
while len(answer) < t :
answer+=tmp[idx]
idx += m
return answer
훨씬 한눈에 보여서 좋다.. 아마도 언젠가 다시볼때 또 이게뭐람.. 이럴수도있겠지. 풀이는 기존과 비슷하다.(사람머리는 안바뀐다는건가 싶다..) 다만 다른점은 tmp에서 최종 answer를 구하는 과정인데 여기서 idx를 만든 후, 만족할때까지 idx에 m(참가인원수)를 더해줬다. 배수로 더해져가며 원하는 정답을 만들어주는데 한눈에 보이기에 간결하고 맘에든다.
보통의 코테에서 그리디유형의 문제는 창의력, 즉 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구
거스름돈
거스름돈으로 사용할 500원, 100원, 50원, 10원이 무한히 존재할 때, 손님에게 거슬러줘야할 돈이 N원이라면, 거슬러줘야할 동전의 최소 개수를 구하라. 단 거슬러줘야할 돈 N 은 항상 10의 배수이다.
→ 가장 큰 화폐단위부터 돈을 거슬러주는것. → 500, 100,50,10원 순으로 가는것이 Greedy알고리즘
def solution(coins, N):
answer=0
coins = sorted(coins, reverse=True)
for coin in coins:
answer += N // coin
N = N % coin
return answer
solution([10,50,100,500], 1260)
이런식으로 가장 큰 동전단위부터 순간순간으로 선택하는것이 그리디알고리즘이다.
#include<bits/stdc++.h>
using namespace std;
int n=1260;
int cnt=0;
int coins[4] = {500,100,50,10};
for (int i=0; i<4; i++) {
int coin = coins[i];
cnt += n/coin;
n %= coin;
}
cout << cnt << endl;
위와같은 방식으로 가장 큰 화폐단위부터 가장 작은 화폐단위까지 차례대로 확인해서 거슬러줄 수 있다 .
위 방식이 가능했던 이유는 갖고있는 동전 중 큰 단위가 항상 작은단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
예를들어 화폐단위가 500, 400, 100 의 경우 800원을 거슬러줘야한다면, 그리디알고리즘에서는 500 + 100*4 가 되어 5개가 된다.
하지만 400 + 400 의 두개의 동전으로 해결할 수 있다.
큰수의 법칙
N개의 수를 가진 array에 대하여, 해당 배열의 주어진 수들을 M번 더하여 가장 큰 수를 만드는데, 여기서 배열의 특정한 인덱스에 해당하는 수가 연속으로 K번 초과하여 더할 수 없는 상황.
n=5;m=8;k=3
data=[2,4,5,4,6]
data = sorted(data)
answer=0
cnt=0
while cnt<8:
for _ in range(k):
answer+=data[-1]
cnt+=1
answer+=data[-2]
cnt+=1
answer
위와같이 루프를 형성해서 반복을 시킬 수 있다.
하지만
#include <bits/stdc++.h>
using namespace std;
int n,m,k;
vector<int> v;
int main(){
// N,M,K를 공백을 기준으로 구분하여 입력받기
// cin >> n>>m>>k;
// for (int i=0; i<n; i++){
// int x;
// cin>>x;
// v.push_back(x);
// }
n=5; m=8; k=3;
v={2,4,5,4,6};
sort(v.begin(), v.end()); //입력받은 수 정렬
int first = v[n-1];
int second = v[n-2];
int cnt = (m/(k+1))*k;
cnt += m % (k+1);
int result = 0;
result += cnt*first;
result += (m-cnt)*second;
cout<<result<<endl;
}
위와같이 $(m/(k+1))*k$ 의 식을 통해서 한번에 카운팅을 진행해 버릴 수 있다.
이걸 보면, $(더할 수\ 개수 / (최대반복+1))\ *\ 전체숫자수$ 이다. 연속으로 더할 수 있는 횟수는 최대 K번이므로, 가장 큰수를 k번 더하고, 두번쨰큰수를 한번 더하는 연산의 반복이 된다.
1이 될 때까지
어떠한 수 N이 1이 될 떄까지 두 과정 중 하나를 반복적으로 선택하여 수행
N에서 1을 뺸다.
N이 K로 나누어떨어진다면 K로 나눈다.
이렇게 연산할 때 N을 1로 만드는 최소 수행 수를 구하기
예를들어 N = 17 , K=4라면,
1번수행 (N=16) 2번수행 (N=4) 3번수행 (N=1)로 종료
최종 3번 실행으로 종료
def solution(n,k):
answer=0
while n!=1:
answer+=1
if n%k==0:
n = n//k
else:
n -=1
return answer
solution(17,4)
#include <bits/stdc++.h>
using namespace std;
int n,k;
int main(){
// N,K를 공백을 기준으로 구분하여 입력받기
// cin >> n >> k;
n=17; k=4;
int answer = 0;
cout<<n<<endl;
while(n>1){
answer +=1;
if (n%k == 0){
n /= k;
}
else{
n -=1;
}
cout<<n<<endl;
}
return answer;
}
시각
주어진 시간 n 에 대하여 00시 00분 00초부터 n시 59분 59초까지 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수를 구하자!
여러 계산을 통해 하나하나 확인하지않고 곱셈을 통해 가능하겠지만.. 시간적 여유로 다음문제를 풀러 뛰어가야하는 상황이라면 얼른 완전탐색으로 코딩해서 돌리고 다음문제에 더 집중하는것이 맞다고 생각된다..
def solution(n):
cnt=0
for h in range(n+1):
for m in range(60):
for s in range(60):
if '3' in str(h)+str(m)+str(s):cnt+=1
return cnt
print(solution(5))
#include <bits/stdc++.h>
using namespace std;
// int h,cnt;
int h=5;
int cnt=0;
int main(){
for (int i=0; i<=h;i++){
for(int j=0;j<60;j++){
for(int k=0; k<60;k++){
if (i%10==3 || j/10==3 || j%10==3 || k/10==3 || k%10 ==3){
cnt+=1;
}
}
}
}
cout<<cnt<<endl;
}
gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] #[3, 7]
# gems = ["AA", "AB", "AC", "AA", "AC"] # [1, 3]
# gems = ["XYZ", "XYZ", "XYZ"]# [1, 1]
# gems = ["ZZZ", "YYY", "NNNN", "YYY", "BBB"]# [1, 5]
def solution(gems = gems):# 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아 구매하기
answer = []
gemkind=set(gems) ## O(n)
anslist=[]
for i,v in enumerate(gems): # 어짜피 한번은 다 돌아야해
tmp=[v,]
tmpidx=[i+1,]
for j,vv in enumerate(gems[i+1:]):
## 나랑 같은게 뒤에도 있는데, 아직 보석을 다 담지 못했어 -> 해당 인덱스부터 시작하는조합은 X야
if vv == v and len(tmp)<len(gemkind): break
if vv not in tmp:
tmp.append(vv)
tmpidx.append(i+j+1+1)
if len(tmp) == len(gemkind) :
# tmpidx[-1] - tmpidx[0]
anslist.append([tmpidx[-1] - tmpidx[0],tmpidx])
anslist = sorted(anslist, key=(lambda x : (x[0], x[1][0])))
# print(anslist)
if len(anslist[0][1])==1:
ans = [anslist[0][1][0] , anslist[0][1][0]]
else:
ans = [anslist[0][1][0], anslist[0][1][-1]]
return ans
solution()
$O(n^2)$ 의 방법으로 생각했다. 시작은 이러하다. 어떠한 인덱스(i) 에서 시작했을 때, 그녀석부터 뒤로가면서 보석을 담는다. 그런데! 만약, 동일한 보석이 발견됐는데, 아직 보석종류를 다 담지 못했다? 그 말은, i부터 시작하는 보석바구니는 최선의 구간이 아니라는 생각이다.
예를들어 첫번째 테스트케이스를 생각했을 때 gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] 에서, 0번인덱스로 시작을 한다면, j가 1씩 증가하며 보석을 검사한다, 그런데 gems[3]에 'DIA'가 또 발견이 됐다. 아직 에메랄드와 사파이어가 남아있는데 같은 보석을 발견한것이므로, 0번에서 시작하는 보석바구니는 최선의 구간이 아니라는것이다.
그렇게 gems[1] 또한 넘어가고, gems[2]에서 시작하면 RUBY , DIA , DIA, EMERALD, SAPPHIRE 를 발견한 순간, anslist에 붙이고, 다음 이터레이션을 시작한다.
결과는.. 정확도테스트는 다 맞췄으나, 효율성에서 OUT..
해결법 : 투포인터
1차원 배열에서 사용 가능하며 $O(n^2)$ 보다 작은 시간복잡도로 풀어야할 때 사용하기 좋은 알고리즘으로, start와 end 포인터를 움직이며 최적의 바구니를 만드는것이라 생가갛면 된다 . ex. N칸의 1차원배열에서, 그 부분배열 중 원소합이 M이 되는 경우의 수를 구하기 start , end = 0,0으로 시작 , 언제나 start <= end 이어야함 start와 end는 현재 부분배열의 시작과 끝 3-1. 현재 부분합이 M 이상이거나 , 이미 end = N 이라면 :: start ++ 3-2. 그렇지 않다면 end ++ 3-3. 현재 부분합이 M과 같다면 결과 ++
위 문제에 적용
s, e 두개의 포인터를 사용 바스켓에 모든 종류의 보석을 담을때까지 e를 이동하며, 바스켓에 추가 매 iteration에서 e를 이동가능한지 체크하여 수행한 수 바스켓이 가득찼는지 (모든종류의 gem을 담았는지) 검사 -> 바스켓이 가득찼다면? -> s를 이동하면서 바스켓에서 하나씩 빼면서 뺼 때마다의 answer가 최적인지 검사
def solution(gems):
answer = [1,len(gems)]
s,e = 0,0
lengem = len(gems)
gemkind = set(gems)
if len(gemkind) == 1 : return [1,1]
basket = {gems[0]:0}
while s<lengem and e<lengem:
if len(basket) < len(gemkind): # e 이동
if basket.get(gems[e]):
basket[gems[e]] +=1
else:
basket[gems[e]] = 1
e+=1
while len(basket) == len(gemkind): # s이동
if basket[gems[s]] > 1:
basket[gems[s]] -=1
else:
del(basket[gems[s]])
s += 1
if answer[1]- answer[0] > e-s:
answer = [s, e]
return answer
```
