알고리즘2022. 2. 27. 21:47
728x90

[ 문제 ]

https://programmers.co.kr/learn/courses/30/lessons/42578

 

코딩테스트 연습 - 위장

 

programmers.co.kr

 

 

[ 코드 ]

def solution(clothes):
    dic={}
    c = 1
    
    # ["yellowhat", "headgear"] 이러한 items를 읽어옴
    for items in clothes:
        if items[1] in dic: # "headgear"가 이미 dic={} 안에 있다면
            dic[items[1]] += 1 # "headgear": +1
        else:               # "headgear"가 처음 나왔다면
            dic[items[1]] = 1  # "headgear" : 1
    
    #print(dic)	 #결과 {'headgear': 2, 'eyewear': 1}
    for v in dic.values(): # 여기서 2, 1을 의미
        c = c* (v+1)  # 안 쓴 경우까지 고려하기 위해 v+1
        # ex. headgear의 경우 "yellowhat", "bluesunglasses", "안 씀" (총 3가지)
        
    #for k, v in dic.items(): #(참고) 이렇게 key,value 이용 가능
    #    print(k," ",v)
    
    return c-1 # 최소 한 개 이상은 입음. 다 안 입는 경우 -1

 

경우의 수를 계산하는 법을 알아야 한다!

 

반응형
Posted by mminky

댓글을 달아 주세요

파이썬2021. 6. 13. 20:46
728x90

* 문제

https://www.acmicpc.net/problem/15973

 

15973번: 두 박스

표준 입력으로 두 박스의 정보가 한 줄에 하나씩 주어진다. 각 박스의 정보는 왼쪽 아래 꼭짓점 좌표 (x1, y1)과 오른쪽 위 꼭짓점 좌표 (x2, y2)로 구성되는데 이들 좌푯값 x1, y1, x2, y2 (x1 < x2, y1 < y2)

www.acmicpc.net

 

[ 코드 ]

# box1의 a점(ax,ay), box1의 b점(bx,by)
ax,ay=0,0
bx,by=0,0
# box2의 c점, d점
cx,cy=0,0
dx,dy=0,0

def point(ax,ay,bx,by,cx,cy,dx,dy):
    if((ax,ay)==(dx,dy) or (bx,by)==(cx,cy) or (bx,ay)==(cx,dy) or (ax,by)==(dx,cy)) :
        return True

    else:
        return False

def line(ax,ay,bx,by,cx,cy,dx,dy):
    # 꼭짓점 하나 일치
    if(((bx,by)==(cx,dy) and by>cy) or (((bx,ay)==(cx,cy) and dy>ay))
    or((dx,cy)==(ax,ay) and by>cy) or ((dx,dy)==(ax,by) and dy>ay)
    # 변 일치
    or ((bx,by)==(cx,dy) and (bx,ay)==(cx,cy)) or ((ax,ay)==(dx,cy) and (dx,dy)==(ax,by))
    or ((cx, cy) == (ax, by) and (bx, by) == (dx, cy)) or ((ax, ay) == (cx, dy) and (dx, dy) == (bx, ay))
    # 그 사이(a,b의 한 변에 c,d가 겹침)
    or (ax==dx and (ay<cy<by or ay<dy<by)) or (bx==cx and (ay<cy<by or ay<dy<by))
    or (by==cy and (ax<cx<bx or ax<dx<bx)) or (ay==dy and (ax<cx<bx or ax<dx<bx))
    # 그 사이(c,d의 한 변에 a,b가 겹침)
    or (ax == dx and (cy < ay < dy or cy < by < dy)) or (bx == cx and (cy < ay < dy or cy < by < dy))
    or (by == cy and (cx < ax < dx or cx < bx < dx)) or (ay == dy and (cx < ax < dx or cx < bx < dx))
    # 내부 한 변 일치(ab안에 cd)
#    or (ay==cy and ax<cx<bx and ax<dx<bx and ay<dy<by) or (ax==cx and ay<cy<by and ay<dy<by and ax<dx<bx)
#    or (by==dy and ax<cx<bx and ax<dx<bx and ay<cy<by) or (bx==dx and ay<cy<by and ay<dy<by and ax<cx<bx)
    # 내부 한 변 일치(cd안에 ab)
#    or (ay==cy and cx<ax<dx and cx<bx<dx and cy<by<dy) or (ax==cx and cy<ay<dy and cy<by<dy and cx<bx<dx)
#    or (by==dy and cx<ax<dx and cx<bx<dx and cy<ay<dy) or (bx==dx and cy<ay<dy and cy<by<dy and cx<ax<dx)
    ):
        return True
    else:
        return False

def null(ax,ay,bx,by,cx,cy,dx,dy): #cy>by or ay>dy
    #dx<ax or bx<cx or min(cy,dy)>max(ay,by) or min(ay,by)>max(cy,dy)
    #우,좌,상,하 바깥에서 안 접할 때
    if(bx<cx or dx<ax or by<cy or dy<ay):
        return True
    #안에서 안 접할 때
    elif(bx-ax<dx-cx and by-ay<dy-cy and (cx<ax<dx and cx<bx<dx) and (cy<ay<dy and cy<by<dy)): #속에 들어감
        return True
    elif(bx-ax>dx-cx and by-ay>dy-cy and (ax<cx<bx and ax<dx<bx) and (ay<cy<by and ay<dy<by)): #속에 들어감
        return True
    else:
        return False


# main 함수
ax,ay,bx,by=map(int,input().split())
cx,cy,dx,dy=map(int,input().split())

if(line(ax,ay,bx,by,cx,cy,dx,dy)):
    print('LINE')
elif (point(ax,ay,bx,by,cx,cy,dx,dy)):
    print('POINT')
elif(null(ax,ay,bx,by,cx,cy,dx,dy)):
    print('NULL')
else:
    print('FACE')

 

[ 결과 ]

 

 


-----------------------------------------------------

case를 다 따져주는 것이 쉽지는 않은 것 같다.

아래의 그림을 보고 빠진 부분이 없는 지 확인해보면 좋을 것 같다 :)

 

* point

 

* line

아마 여기 코드 사진에 오타가 있을 것이다. 코드는 위에 첨부한 것을 참고하면 될 것 같다 :)

 

 

* null

 

 

 

※ 제 글이 도움이 되었다면 공감 부탁드려요 :)

반응형
Posted by mminky

댓글을 달아 주세요

파이썬2021. 6. 6. 19:28
728x90

* 문제
https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로

www.acmicpc.net


[ 해결 원리 ]
하노이탑 개념에 대해 그림으로 쉽게 설명해두었으니 참고하면 좋을 것 같다 :)
https://mminky.tistory.com/116

[ C ] 분할정복 - 하노이탑 (a divide-and-conquer algorithm for the Towers of Hanoi problem)

[ 문제 ] Write a divide-and-conquer algorithm for the Towers of Hanoi problem. The Towers of Hanoi problem consists of three pegs and disks of different sizes. The object is to move the disks that a..

mminky.tistory.com



[ 코드 ]
**하노이탑 파이썬 - 시간초과가 떴다면**
print(count) 대신 print(2**n - 1) 를 해라!
-> 하노이탑의 총 옮긴 횟수는 2^n - 1으로 정해져 있다.
(하지만 개인적으로 옮길 때 마다 count를 증가시켜서 총 count를 출력하는 게 맞다고 생각한다.
근데 그렇게 하면 시간 초과가 된다..)

import sys input=sys.stdin.readline n = int(input()) #count = 0 #옮긴 횟수 #ans='' def hanoi(disk_num,from_peg,to_peg,tmp_peg): global count,ans if(disk_num==1): print(from_peg,to_peg) # ans += '{} {}\n'.format(from_peg,to_peg) # count += 1 return hanoi(disk_num-1,from_peg,tmp_peg,to_peg) print(from_peg,to_peg) # ans += '{} {}\n'.format(from_peg, to_peg) # count += 1 hanoi(disk_num-1,tmp_peg,to_peg,from_peg) print(2**n - 1) #count를 하니 시간 초과 뜸 # (처음)1 에서 (최종)3으로 이동함 # 2는 거치는 곳일 뿐! hanoi(n,'1','3','2') #print(count) #print(ans)



[ 결과 ]
와.. 진짜 시간초과 너무한거 아니냐고....
몇 번을 시도해서 결국 통과되었다.. 너무해..

반응형

'파이썬' 카테고리의 다른 글

[ Python ] 백준 10157 - 실패..  (0) 2021.06.13
[ Python ] 2차원 배열 (리스트)  (0) 2021.06.13
[ Python ] 백준 13300 파이썬  (0) 2021.05.31
[ Python ] 백준 10828 파이썬  (0) 2021.05.31
[ Python ] 백준 1735 파이썬  (0) 2021.05.31
Posted by mminky

댓글을 달아 주세요

파이썬2021. 3. 8. 15:43
728x90

* 몫

9를 4로 나눴을 때의 몫은 2이다. ( 9 = 4*2 +1 )

9//4

 

 

* 나머지

9를 4로 나눴을 때의 나머지는 1이다. ( 9 = 4*2 + 1 )

9%4

 

* 합

1부터 5까지의 합은 다음과 같이 구한다.

sum([1,2,3,4,5])

 

 

* 원 넓이, PI 값

반지름이 5인 원의 넓이를 구하는 방법이다.

 

이때, math의 PI를 import하는 방법이 두 개가 있다.

 

(방법1)

math를 해주기 때문에 math.pi 를 해야 한다.

>>> import math
>>> area=math.pi*5*5

 

(방법 2)

pi를 import 해주기 때문에 바로 pi 를 이용할 수 있다.

>>> from math import pi
>>> area=pi*5*5

 

* 지수 승 (a ^ n)

2^3 을 구하기 위해서는 2**3을 해줘도 된다.

하지만 math를 이용하기 위해서는 다음과 같이 pow를 이용해주면 된다.

math.pow(2,3)

 

* 루트 (√2)

( 루트2 를 구하기 위해서 2**0.5 를 해줘도 상관은 없다. )

math.sqrt(2)

 

 

* 자연로그 ln(x)

math 라이브러리에서는 그냥 log가 ln이다. (밑이 e)

math.log(2)

 

* 상용로그 log(x)

밑이 10인 상용로그는 다음과 같이 구한다.

math.log10(10)

 

* 밑이 특정한 로그

밑이 2인 로그에 4를 넣은 값은 다음과 같이 구한다.

log2(4)

math.log(4,2)

 

* sin

역시 math.sin을 이용하면 정확하게 나온다.

math.sin(30)

 

* degreee(도) 에서 radian(라디안) 으로 변경

math.radians() : degree -> radian 으로 변경

 

math.radians(30)

 

 

* 반올림

round를 이용한다.

round(숫자,반올림할자리수)

 

다음은 √3을 반올림해서 소수 둘째자리 까지 표현하는 예시이다.

 

둘째 자리 까지 반올림 됨

 

 

 

 

[ 연습문제 ]

 

* 환율구하기

>>> currency = 1112.39
>>> dollar = 3
>>> won = dollar * currency
>>> won
3337.17

 

* 대출 첫 달 이자 구하기

8000만원 대출 시 첫 달 이자(금리 1.72%)

 

빌린금액(loan) = 8000,0000

금리(interest rate) = 0.0172

첫 달 이자(first_mon) = 빌린금액 * 금리 / 12  (1년은 12달)

>>> loan = 80000000
>>> int_rate = 1.72/100
>>> first_mon = loan * int_rate / 12
>>> first_mon
114666.66666666667

 

반올림을 통해서 1의자리까지 표시

따라서 첫 달 이자는 114,667(약 11만원)

>>> round(first_mon)
114667

 

* 연복리 예금 만기 금액 구하기

정기예금 이자 2.7%, 3년 연복리 상품, 2000만원 예금시 만기 금액

 

예금액(deposit) = 2000,0000

이자율 = 0.027

기간 = 3년

 

만기금액 = 예금액 * (이자율 + 1) ^3

            = 2000,0000 * (1+0.027) * (1+0.027) * (1+0.027)

(1년이 지날 때 마다 이자가 붙는 형식이므로 원금+이자율을 3번 곱해줍니다.)

>>> deposit = 20000000
>>> int_rate = 2.7 / 100
>>> year = 3
>>> deposit * (int_rate+1)**3
21664133.659999996

 

※ 제 글이 도움이 되었다면 공감 부탁드려요 ◡̈

반응형
Posted by mminky

댓글을 달아 주세요