2024년 4월 4일

1. 2798 블랙잭

.-<아이디어는 어차피 3개 뽑는거니까 combinations써서 조합 구하고, sum구하고 그 중에서 filter를 통해 거르고 가장 큰거 뽑자! 라고 했는데, 코드는 짧지만 속도가 좀 느리다. 아무래도 전체를 다 구하려니까 그러는 것 같음.

코드비교

다른 사람들 코드를 보면, 우선 정렬한다→왜? 어차피 가장 큰 수를 골라야하기 때문에 큰수부터 정렬해서 하나씩 제거하는 느낌.

for문을 3번 돌리고, n-2 n-1 n으로 3개 범위를 이용하고, temp에 그 3개를 다 더한 뒤(sumnumber), M보다 작으면, result를 max(result, sumnumber)로 비교해서 최댓값을 추출한다.

data.sort(reverse=True)# 가장 큰 수를 골라야하기 때문에 
result = 0
length = len(data) 
for i in range(0, length):
    for j in range(i+1, length): #이전에서 하나 뽑았으니 제외 하고
        for k in range(j+1, length):#i에서 뽑았으니 그것보다 더 작은(즉, 큰수 우선 정렬에서 뽑은 수 보다 오른쪽인)
            sum = data[i]+data[j]+data[k]
            if sum <= M:
                result = max(result, sum)
                break

알게 된 점

  • 오류 : max()함수에서 lambda x를 통해 조건을 주어서 거르려고 했더니 안됨. 따라서 거르려면 보통 filter()함수를 쓰는게 맞다.
  • 람다 쓰는 위치가 다르다!
    • map,filter 등은 map(람다식, 적용할 것) map과 filter는 어떤 조건으로 이터러블한 객체에 적용시킬까이므로 조건이 중요하니 먼저 서술!
    • min,max 는 max(적용할 것, 람다식) 은 기본 이터러블한 객체에게 min, max, sum 을 적용시키는게 우선이라 이터러블 객체를 받는게 기본이고, 추가적으로 람다를 활용해 조건을 줄 수 있으므로 객체가 앞에 들어가야 함!
  • map(sum,)으로 각각 sum 적용시킬 수 있음. map은 그냥 for문이라고 생각하자.
  • 최댓값 구할 때 for문으로 하나하나 더한 다음, 그걸 max로 최댓값인지 비교하는 코드가 많다.

나의 코드

import sys
from itertools import combinations
N,M= map(int,sys.stdin.readline().strip().split())
card = map(int,sys.stdin.readline().strip().split())
print(max(filter(lambda x: x<=M,map(sum,combinations(card,3)))))

2. 2609 최대공약수와 최소공배수

아까 사용했던 최대값 구하기를 써서 풀었다! 수학적 공식을 이용해야한다는 생각이 잠깐 들었지만, 아까 배운걸 써보고 싶어서 일단 써봄.. 결과는 한 4ms정도 느리게 나왔다.

코드비교

일단 while문으로 답이 나올때 까지 돌리고, 그 가운데에서 식을 a,b = b, a%b로 했다.

유클리드? 정리라고 한다. 걍 넘어가도록하자.

a,b = map(int,input().split())
m = a*b
while a%b!=0:
  a,b = b,a%b
print(b)
print(m//b)

나의 코드

import sys
from itertools import combinations
N,M= map(int,sys.stdin.readline().strip().split())
result =0
for i in range(1,min(N,M)+1):
    if N%i ==0 and M %i == 0:
        result = max(i,result)
        
print(result)
print(N*M//result)

3. 11050 이항 계수 1

  • 2번: n개중 k를 선택하는 조합의 수는 결국 n개 중 선택받지 못한 아이템들의 조합의 수와 같다.
  • 3번: 이항계수의 정의를 이용하여 3번과 같은 식을 도출해낼 수 있다.
  • 4번: 파스칼의 삼각형과 관련이 깊다.

python math의 factorial(n-k)를 사용하면 좋을듯..

코드비교

이항계수란 주어진 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 개수이므로 조합의 개수를 넣어버리면 되는 아주아주 간단한 사실 ^^

len(list(combinations(range(N), K)))#매우 간단 ㅋㅋ
#1부터 N가지 수에서 K를 뽑는 갯수= nCk임..!!^^

알게 된 점

오류: 아니 팩토리얼 제대로 썼으면서 ㅋㅋㅋㅋ 바보 같이 n!/(n-k)!k!를 왜 n!/n-k)! * k!로 이해했을까..?

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

바보..

나의 코드

import sys
import math
N,K= map(int,sys.stdin.readline().strip().split())
print(math.factorial(N)//math.factorial(K)//math.factorial(N-K))

2024년 4월 5일

1. 10816 숫자 카드 2

딱 든 생각은 개수를 세야 하니까 관련 내장 함수 쓰자! 해서 colllections 의 Counter를 활용했다. 문자열 출력하는 것 때문에 (for문에서 각자 print하면 뒤에 \n가 붙어서..) list에 넣고 했다. 딴 사람도 counter로 했던데 속도가 좀 빨라서 list를 새로 넣는것 때문인지 궁금해 string으로 더했다. 결과는 시간초과 ^^

알게 된 점

  • string concat의 시간복잡도는 O(N^2)d이다.
    • 파이썬에서 string A + string B를 하면 O(len(A))+O(len(B))로 완전히 새로운 스트링을 만듦. 즉, 새로운 메모리에 복사해야 하니 압도적으로 느리다..^^(참고 블로그)

코드비교

생각보다 counter가 더 오래걸린다.. in이 더 오래 걸릴 줄 알아서 함수 썻더닝..in이야 있으면 dic[num]에 +1 추가하면 되고, 더 시간 줄일 수 있는 건 join에다가 list comprehension 써서 값을 그대로 꽂기!

함수 그대로를 안에 꽂는 느낌이랄까

print(' '.join(str(counter[i]) if counter[i] else "0" for i in card_count))
# 참일때 실행할 것 if 참조건 else 거짓일때 실행할 것 for문

나의 코드

import sys
from collections import Counter
#상근 소지 카드 갯수
N= sys.stdin.readline().strip()
#숫자카드에 적힌 정수
card_num = sys.stdin.readline().strip().split()
M= sys.stdin.readline().strip()
card_count = sys.stdin.readline().strip().split()
answer = ""
counter = Counter(card_num)

print(' '.join(str(counter[i]) if counter[i] else "0" for i in card_count))

#고치기 전 코드 
import sys
from collections import Counter
#상근 소지 카드 갯수
N= int(sys.stdin.readline().strip())
#숫자카드에 적힌 정수
card_num = sys.stdin.readline().strip().split()
M= int(sys.stdin.readline().strip())
card_count = sys.stdin.readline().strip().split()
answer =[]
counter = Counter(card_num)
for i in card_count:
    if counter[i]:
        answer.append(counter[i])
    else:
        answer.append(0)
print(' '.join(map(str,answer)))

2. 9012 괄호

생각 과정 - ()갯수차이? x())(도 된다. ( 이게 있으면 )이게 있어야 한다. 즉, )는 (보다 먼저 나오지 못한다. 크기도 그닥 안크니까 왼쪽부터 보면서 )이 (이거 보다 크면 아웃시키자!

→예외 발생 1. 둘다 갯수는 짝지어지는데 위치가 안좋은 경우 ex) )()( 처럼 처음이 ) 거나 끝이 (인 경우가 있다. 2. 최종적으로 갯수가 다른경우.

코드비교

()를 replace로 ‘’공복으로 바꾸니 남는게 없으면 YES고 있으면 NO라는…참 쉬운 사실.. 양파까는거 생각하면 될듯..? 어차피 ()로 이루어져 있다는 게 사실이니까 지우다 보면 밖에 있는 (()) 이것도 ()이렇게 되니까 벗길 수 있다!

나의 코드

import sys
n= int(input())
for i in range(n):
    bracket= list(sys.stdin.readline().strip())
    l = 0 
    r = 0
    isBracket = True
    if bracket[0]==")"or bracket[-1] =="(":
        print("NO")
    else:
        for one in bracket:
            if one =="(":
                l+=1
            else:
                r+=1
            if r>l:
                print("NO")
                isBracket = False
                break
        if r<l:
            isBracket = False
            print("NO")
        if isBracket: print("YES")

3. 2164 카드2

진짜 엄청 고민했던 아이.. 수학적으로 풀 수 있을 것 같아서 머리굴리다가 2의 제곱이 관련 있다는 걸 알고 무작정 제곱근만 출력한게 화근..^^ 또 이 규칙을 카드의 순서와 숫자로만 알아내려고 하니까 머리 터짐.

알게 된 점

  • list pop보다 del이 빠르고, list pop보다는 deque pop이 훨훨훨 낫다ㅏ…^^ 아니 list로 구현했는데 시간 초과돼서 뭐가 문젠지 했다 ㅠㅠ 그냥 문제 그대로 popleft로 꺼내고 오른쪽에 집어 넣고 반복하니 그냥 돼서 진심 허무..

코드 비교

이해 안돼서 이 블로그로 이해함.. 그냥 4일때는 답이 뭐, 5일떄는 답이 뭐.. 이렇게 알아야 하나부다..이 블로그는 귀납적으로 풀었던데 흠..

결론! 일단 머리 써서 안되면 구현으로 승부하자 ^^

내 코드

# 큐로 해결
import sys
from collections import deque
n= int(input())
numbers = deque([i for i in range(1,n+1)])
while len(numbers)>1: 
    if numbers:
        numbers.popleft()
        a =numbers.popleft()
        numbers.append(a)
    else:
        break

print(numbers[0])

#수학적으로 해결 
n= int(input())
bi = 1
if n ==1:
    print(1)
else:
    while bi<=5000000: 
        if n<=bi:
            print((n - (bi//2))*2)
            break
        else:
            bi*=2