2022 07

✨ 2022-07-07

주제 : 그리디(Greedy)

• Aiden
  • 문제1
    • 코드1
  • 문제2
    • 코드2
• Hayden
  • 문제1
    • 코드1
  • 문제2
    • 코드2
• Hoon
  • 문제1
    • 코드1
  • 문제2
    • 코드2
• Sawyer
  • 문제1
    • 코드1
    • 코멘트

import sys #입력을 받기 위해 input()보다는 sys.stdin.readline() 이 시간적으로 이득
input = sys.stdin.readline

n, k = map(int, input().split()) #입력받고 

count = 0 #답으로 입력할 카운트값

while bin(n).count('1') > k: # 이진수로 바꿧을때 1의 개수 > 최대물병수
n = n+1
count +=1
print( count)

bin(n).count('1') 은 이진수이기 때문이다. 이진수의 특성상 2가 되면 자릿수가 올라간다.
1 = 1
2 = 10
3 = 11
4 = 100
5 = 101
여기서 보면 자연수 1은 1이다 1개가 남는다.
2는 1이 2개 모여서 이진수 10이고 2L가 하나인 1개의 물통이다.
3은 1이 2개 모여서 2L 1개 1L는 1개 있기 때문에 2개가 만들어진다.
하지만 카운트하면 2이므로 2개의 물병이기 때문에 n = 3 , k =1 에서 해당되지 않아 while문을 실행한다.
결국에 이진수이기 때문에 64 32 16 8 4 2 1
각자리수에서 자릿수가 올라가는 순간
1은 2개
2는 4개
4는 8개 로 같은 양의 물로 맞춰진다. 그래서 1의 개수는 결국 짝이 안 맞춰진 물병이다.!

• 문제2
  • 코드2
  • 코멘트

# 보물
import sys
input = sys.stdin.readline #input속도가 빠른 것으로 바꿔준다

n = int(input()) #입력 int로 받고

A = list(map(int,input().split()))  # 2개 다 입력받기
B = list(map(int,input().split()))

#여기서 중요한것은 B는 재배열하지말라고했지만 A만 바꿔줄수 있으면 결국에 원하는대로 바꿔서 곱해줄수 있으므로 B도 정렬해준다.
# 그래서 b는 오름차순 a는 내림차순 정렬
sort_b = sorted(B) 
sort_a = sorted(A,reverse=True)


result = 0
그냥 곱해준다.
for i in range(n) :
    result += sort_a[i] * sort_b[i]


print(result)

# 쉬워서 설명할게없다..

✨ 2022-07-14

주제 : 깊이 우선 탐색(DFS)

• Aiden
  • 주제 관련 문제
    • 주제 관련 코드
    • 코멘트
      • 필요시 작성
  • 자유주제 문제
    • 자유주제 코드
    • 코멘트
      • 필요시 작성
• Hayden
  • 주제 관련 문제
    • 주제 관련 코드
  • 자유주제 문제
    • 자유주제 코드
    • 코멘트
      • 루트노드부터 시작해서
      • 왼쪽->오른쪽 순으로 자식노드가 있는지 검사한 후
      • 자식노드가 있으면 리프노드에 닿을 때까지 계속해서 재귀함수 호출
      • 리프노드일 경우 합계에 <이진수를 십진수로 변환한 값>을 더함
      • 마지막 리프노드에 이르기까지 위 과정 반복
• Hoon
  • 주제 관련 문제
    • 주제 관련 코드
  • 자유주제 문제
    • 자유주제 코드
• Sawyer
  • 주제 관련 문제
    • 주제 관련 코드
    • 코멘트

import sys
input = sys.stdin.readline

def dfs(num, arr):
    arr[num] = -2 # 삭제하는 노드 -2로 바꿔서 없는셈으로침 부모노드번호를 -2로 바꿈(없는것) 
    for i in range(len(arr)): # arr 리스트 개수만큼 for문 돌리기
        if num == arr[i]: # 첫번째 for문 구동은 부모 노드가 삭제노드 일 때 동작
            dfs(i, arr) # 자식노드 첫번째 노드부터 다시 넣어서 밑에를 다짤라냄

n = int(input()) # 전체 노드 개수 
arr = list(map(int, input().split())) # 부모 노드 번호가 리스트에 기입되어 있음.
k = int(input()) # 삭제하는 노드
count = 0

dfs(k, arr) # 함수돌리기
count = 0 
for i in range(len(arr)):
    if arr[i] != -2 and i not in arr: # -2가 아니고 부모노드가 아닌것만 골라냄
        count += 1
print(count)

• 자유주제 문제
  • 자유주제 코드
  • 코멘트
    • BFS 문제이다.

✨ 2022-07-28

주제 : 깊이 우선 탐색(DFS) & 너비 우선 탐색(BFS)

• Aiden
  • 주제 관련 문제
    • 주제 관련 코드
    • 코멘트
      • 필요시 작성
  • 자유주제 문제
    • 자유주제 코드
    • 코멘트
      • 필요시 작성
• Hayden
  • 주제 관련 문제
    • 주제 관련 코드
    • 코멘트
      • 필요시 작성
  • 자유주제 문제
    • 자유주제 코드
    • 코멘트
      • 필요시 작성
• Sawyer
  • 주제 관련 문제
    • 주제 관련 코드
    • 코멘트
      • 필요시 작성
  • 자유주제 문제
    • 자유주제 코드
    • 코멘트
      • 필요시 작성