✍️오늘 공부한 내용
📋새로 배우게 된 내용
- 저번에 문제풀이들을 참고하다가
lambda식을 보게 되었는데, 덜컥 겁(?)이 났다. 처음에는 람다식이 들어간 코드는 일부러 피하고 싶었는데, 오히려 안보니까(?) 더 궁금해져서 오늘 문제풀이에는 적극적으로람다식을 써볼까 생각을 했다.
# C배열에서 item j들의 길이를 반환하는 list
cm=list(map(lambda j:len(j),C))
# C배열에서 길이가 가장 긴 문자열보다 길이가 크거나 같은 문자열 i를 필터링해서 반환하는 list
max_s=list(filter(lambda i: len(i)>=max(cm),C))- 그리디 풀이 방법 참고 출처
1) 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
2) 가능한 모든 방법을 다 고려한다.
3) 실제 답을 구할 수 있는지 적용한다.
📚여기서 2)의 모든 방법에는 다음과 같은 방법 등이 있다.
① Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법
② 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
③ 재귀 호출
④ 비트마스크 - 2진수 표현 기법을 활용하는 방법
⑤ BFS, DFS를 활용하는 방법
🫥오해했던 점
오해라고까지는 아니지만배열이나 string에서 해당 문자열이나 item을 찾을때 find()함수를 쓰거나 for문을 돌면서 찾아야하는 줄만 알았다. 코드리뷰 중index()쓴다는 말을 들었고,아! string도 결국 iterable이면 당연히 인덱스로 접근할 수 있지!싶었다. 혼자 코드를 들여다보는 것보다는 여러명의 관점이나 풀이방식을 보는 방식이 생각을 넓힐 수 있어서 신기하면서 즐겁다.
🤯어려웠던 점
- 1700번 멀티탭 스케줄링문제를 풀면서 12%까지 맞았다가
틀렸습니다가 떠서 좀 애먹었다. - 2098번 외판원 순회은 dfs bfs에서 방문했던 문제였는데 dp로는 감이 오지 않아서 풀이들을 검색해보니
비트마스킹를 사용했다는 걸 알게 되었다. [참고 출처]비트연산자는 알겠는데 비트마스킹은 뭐지? 다른 건가?
😸어려움을 해결한 방법
- 처음에는 질문게시판에 나와있는 반례들을 넣어보며 정답을 맞추기에 좀 급급했다. 하지만 코드를 tweak해가면서 반레들은 맞춰갔지만, 시행착오를 반복하면서
이게 맞나?싶었다.
- 결론은 짰던 로직을 다시 정리해서 말로 써보고, 내가 쓴 코드가 거기에 부합한 지 주석으로 달아놨다.
- 그러다보니 (1)
itm = deque(I[N:])로 짰던 코드에서 중복할 경우는 제외할 조건을 고려하지 않았다는 걸 발견했고, (2) 검사해서 교체해줬던 물품을 또 다시 검사한다는 점을 발견했다 - (1)은 단순히 N번째 물품부터 검사할뿐, N개 안에서의 중복을 고려하지 않아서 아래와 같이 중복을 제외하고 있는 멀티탭 구멍개수만큼 물품을 꽂도록 하고
for indx,i in enumerate(I):
if i not in itm: #이미 꽂았던 멀티탭이 아니라면
itm.append(i) #deque에 추가하고
s=indx #사용물품의 인덱스 저장하기
if len(itm)==N: #구멍이 더이상 없다면
break #forloop 벗어나기
itm.extend(I[s+1:]) #deque에 검사해야할 나머지 물품들 추가해주기
I=list(itm)- (2)에서 교체를 했는데 또 교체를 하려는 경우를 방지하기 위해 교체 여부를 bool값으로 저장할 변수를 하나 만들어줘서 사용했다.
- 고민한 흔적& pseudo코드를 수기로 적음 (전체 코드)
++넣어봤던 반례까지
# logic
## 멀티탭을 연결하지 않았을때는 꽂아주지만, 중복한 경우는 다음 중복되지 않은 멀티탭을 꽂아준다.
## 가장 나중에 교체해줘야할 경우에 교체 횟수가 최소가 되므로 해당 index에 물품을 교체하도록 한다.
## 이미 물품이 꽂아져있거나 아예 꽂아지지 않는 경우는 교체를 해주지 않는다.
from collections import deque
from sys import stdin
N, K = map(int, stdin.readline().strip().split()) #N:구멍,K:사용물품개수
I=list(map(int, stdin.readline().strip().split()))
# itm = deque(I[N:]) #중복해서 넣지 않는 경우 생각 안함..
itm = deque() ##deque로 구현해서 하나씩 leftpop하자.
s=0 ##중복된 멀티탭은 새로 꽂아주지 않으므로 앞으로 검사할 멀티탭의 index를 저장할 변수 선언
for indx,i in enumerate(I):
if i not in itm: #이미 꽂았던 멀티탭이 아니라면
itm.append(i) #deque에 추가하고
s=indx #사용물품의 인덱스 저장하기
if len(itm)==N: #구멍이 더이상 없다면
break #forloop 벗어나기
itm.extend(I[s+1:]) #deque에 검사해야할 나머지 물품들 추가해주기
I=list(itm)
ans=0 #멀티탭 분리 횟수
def greedy(n:int,k:int,itm:deque,ans:int)->int:
plugged= list(I[:n]) #이미 꽂아있는 멀티탭 배열
if k==1 or n>=k : # 꽂아야할 게 하나밖에 없거나 구멍개수가 사용해야할 거 보다 많다면 뽑을 필요가 없다
return 0
while itm: #검사해야할 물품deque가 없을때까지
changed=False #검사를 해주고 바꿔끼웠을 상태를 체크해줄 변수
curr= itm.popleft() #현재 사용할 물품
unplug=[] #가장 나중에 사용할 물품을 고르기 위해 물품의 검사 물품에서의 인덱스를 넣을 배열
l=None #가장 나중에 쓸 물건
if curr in plugged: #현재 검사물품이 멀티탭에 꽂아있다면
continue
elif curr not in plugged: #그렇지 않다면
for m in plugged: #꽂아있는 물품들 중에서
if m not in itm: # 한번만 사용하고 다시는 검사 안할 물품이라면
plugged[plugged.index(m)]=curr #그 해당 물품을 교체해준다
changed=True #교체를 했으므로 다음 물품 검사를 위해 검사했음을 표시
ans+=1 #멀티탭 분리를 했으므로 1증가
break
else:
unplug.append(itm.index(m)) #다시 사용할 물품이 있는 경우 뺴야할 후보에 등록
if len(unplug)>0 and not changed: # 뺴야할 후보가 있고 아직 교체를 해주지 않았다면
l=plugged.index(itm[max(unplug)]) # 가장 나중에 뺴줘야할 물품을 골라서
plugged[l]=curr #현재 물품을 꽂아준다
ans+=1 #변경했으니 횟수 1증가
continue
return ans
# 구멍개수, 물품개수, 검사해야할 물품 deque,정답 변수
print(greedy(N,K,itm,ans))
#####반례####
# 3 100
# 56 71 70 25 52 77 76 8 68 71 51 65 13 23 7 16 19 54 95 18 86 74 29 76 61 93 44 96 32 72 64 19 50 49 22 14 7 64 24 83 6 3 2 76 99 7 76 100 60 60 6 50 90 49 27 51 37 61 16 84 89 51 73 28 90 77 73 39 78 96 78 13 92 54 70 69 62 78 7 75 30 67 97 98 19 86 90 90 2 39 41 58 57 84 19 8 52 39 26 7
# 정답: 80
#---------------------
# 3 14
# 1 4 3 2 5 4 3 2 5 3 4 2 3 4
# 정답: 4
# ------------------------
# 2 15
# 3 2 1 2 1 2 1 2 1 3 3 3 3 3 3
# 정답: 2
# ------------------------
# 2 4
# 5 3 1 5
# 정답: 1
# ------------------------
# 2 5
# 5 2 2 3 5
# 정답: 1
# ------------------------
# 3 9
# 1 2 3 4 1 1 1 1 3
# 정답: 1
# ------------------------
# 2 11
# 1 2 3 4 5 1 1 1 2 2 2
# 정답: 4
# ------------------------
# 2 15
# 3 2 1 2 1 2 1 2 1 3 3 3 3 3 3
# 정답: 2
# ------------------------
# 3 13
# 2 3 4 2 3 4 1 5 5 5 2 3 2
# 정답: 2
# ------------------------
# 4 20
# 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
# 정답: 4
# ------------------------
# 3 13
# 2 3 4 2 3 4 1 5 5 5 2 3 2
# 정답: 2
# ------------------------
# 4 20
# 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
# 정답: 4
# ------------------------
# 3 11
# 11 8 11 7 2 8 2 7 5 10 2
# 정답: 3
# ------------------------
# 3 5
# 1 1 1 1 2
# 정답: 0 # ??1아님? 2사용하려면 1번은 뽑아야할텐데..?
# ------------------------
# 2 10
# 1 1 2 1 1 2 1 1 2 1
# 정답: 0
-
비트마스킹에 대한 근본적으로 궁금했던 점들을 정리하자면
👤비트마스킹 ==
어떤 비트값에서, 특정한 비트값을 추출,보전,수정하는 기법
👥비트연산자를 통해서 하는 것! 👉비트마스킹, 비트연산
👤비트마스킹을 하는 이유? 1. 시간복잡도 O(1) 2. 코드 간결화 3. 메모리 사용 감소 & 캐시 효율적 4. 연관배열을 배열로 대체가능
🤔
4번 장점은 딱 와닿지는 않지만 추측해보기로는 dict()과 같은 연관배열은 구조가 복잡해지기 때문이 아닐까
🤔아쉬웠던 점
- 1946번 배열 대신 중복을 없애기 위해 set()과 인덱스 대신 바로 key로 접근하기 위해 dict()으로 구현하고 싶었는데,
틀렸습니다가 뜬다. 아직 반레처리가 잘 안된 듯하다.
😝느낀점
- 1700번 풀이들을 보면 대부분 배열로 접근했던 문제였는데, 최근 배웠던 deque를 적용해보면 어떨까해서 풀어봤는데 풀려서 뿌듯했다.
- 1946번도 1700처럼 pseudo 코드 수기화하고 마무리해봐야겠다.
👊다짐
- 모든 문제들을 pseudo 코드 수기화를 먼저하고 문제를 풀도록 하자.
이렇게 접근하면 되겠네단순히 생각만 하는게 아니라 직접 손으로 써봐야잠깐, 이렇게 접근하기로 했는데 여기서 꼬이네가 보이는 것 같고, 나아가서 반례를 하나 둘씩 수기로 넣는 것보다 더 효율적으로 예외상황 처리가 가능한 거 같다. - 곱셈전개식문제를 실수로(?) 풀고 있었는데 규칙 하나에서 막혀서 풀이를 완성하지 못했다. 이 문제도 revisit해서 풀어보도록 하자!
🚀오늘의 한줄평
- 가끔은 손이 덜 고생하려고 머리쓰다가 머리도 고생한다.😂
https://pyotato-dev.tistory.com/ 로 이사중 🚚💨🚛💨🚚💨