알고리즘2021. 6. 16. 01:35
728x90


* 시간복잡도 O(nlgn) -> sorting
* 압핀에 고무줄 끼우는 거라고 생각!

[ step ]
1) closed path 그리기
2) turn left인 점만 포함


반응형
Posted by mminky
알고리즘2021. 6. 16. 01:34
728x90

반응형

'알고리즘' 카테고리의 다른 글

코딩테스트 대비 백준 사이트 이용법  (0) 2022.02.23
graham scan으로 convex hull 그리기  (0) 2021.06.16
[ Python ] 백준 5585  (0) 2021.06.14
[ Python ] 코드업 1229  (0) 2021.06.14
[ C ] tromino  (0) 2021.04.02
Posted by mminky
기사 자격증2021. 6. 16. 01:32
728x90

[ 설정 전 상태 ]
cos(ㅠ) = -1이라고 잘 나온다.


하지만 cos(180)은 이상한 값이 나온다.



[ 방법 ]
따라서 Rad이라고 설정되어있는 것을 Deg로 변경해줘야 한다. (반대의 경우는 Rad로 변경. 영상참고)

1) Shift
2) Set up
3) 3을 눌러서 Deg모드로 변환



[ 결과 ]
cos(180)=-1이라고 잘 나온다 :)



[ 영상 ]
cos(180)=-1로 잘 나오는데 cos(파이)는 이상한 값이 나온다.
이 경우 파이(rad)를 숫자(deg)로 변경해주는 세팅을
해줘야 한다.

 

반응형
Posted by mminky
알고리즘2021. 6. 14. 11:32
728x90

* 문제

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

 

5585번: 거스름돈

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사

www.acmicpc.net

 

[ 코드 ]

money=int(input())
bill = 1000
change = bill-money

n_500 = change//500
change%=500

n_100 = change//100
change%=100

n_50 = change//50
change%=50

n_10 = change//10
change%=10

n_5 = change//5
change%=5

n_1 = change

print(n_500+n_100+n_50+n_10+n_5+n_1)
반응형
Posted by mminky
알고리즘2021. 6. 14. 11:24
728x90

* 문제

https://codeup.kr/problem.php?id=1229 

 

비만도 측정 2

키 h와 몸무게 w가 공백을 기준으로 실수로 입력된다.(1≤w, h≤200) 반드시 double형을 사용해야 함. float으로 하면 오답처리되는 케이스가 있음.

codeup.kr

 

[ 코드 ]

def stand_weight(h):
    if h<150:
        sw=h-100
    elif 150<=h<160:
        sw=(h-150)/2 +50
    elif h>=160:
        sw=(h-100)*0.9
    return sw

#비만도
def overweight(w,sw):
    over=(w-sw)*100/sw
    return over

def grade(h,w):
    sw = stand_weight(h)
    over = overweight(w,sw)
    if(over <= 10):
        print('정상')
    elif(10<over<=20):
        print('과체중')
    elif(over>20):
        print('비만')

#main
h,w=map(float,input().split())
grade(h,w)

파이썬에서는 float해도 오류가 안나는 것 같다!

(double형이 없어서 그런가?)

 

[ 결과 ]

 

반응형
Posted by mminky
파이썬2021. 6. 14. 09:54
728x90

[ 코드 ]

import re
# 패턴 넣으면 정규표현식 이용해서 해당하는 것 리스트로 리턴(find)
def match_dna_list(pattern_s, content_s):
    pattern_s_r = pattern_s.replace('_', '.')
    # pattern_s_r='(?=(.A....))'
    pattern_s_r = '(?=(' + pattern_s_r + '))'
    find = re.findall(pattern_s_r,content_s)

    #print(find)
    return find


with open ('3.inp','r') as f:
    #.strip()을 해줘야 \n 이 없어짐
    # \n 이 있으면 완전 다른 문자가 되기 때문에 findall()하면 안 나옴
    pattern = f.readline().strip()

    # 나머지부분 읽음
    dna_seq=''
    for i in f:
        dna_seq += i.strip()

    with open('dna.out', 'w') as f2:
        # find 안에 값이 있다면
        if ( match_dna_list(pattern,dna_seq) ):
            f2.write('\n'.join(match_dna_list(pattern,dna_seq)))
        else:
            f2.write('No')

 

 

[ 결과 ]

3.inp

_A____
CCCCCCCCCCCCCAAAATTTTTTTTGGGGGGGGGAAATTT

 

dna.out

 

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

 

* 정규표현식에서 모든 문자는 . 이다.

pattern_s_r = pattern_s.replace('_', '.')

 

* 겹치는 문자를 찾는 방법은 다음과 같다.

(?=( 패턴 )) 형식으로 만든 후 findall에 넣어준다.

pattern_s_r = '(?=(' + pattern_s_r + '))'
find = re.findall(pattern_s_r,content_s)

 

 

* 리스트로 return된 값을 '\n' 기준으로 출력하는 방법.

단, 마지막은 \n 없이 출력한다.

'\n'.join(출력원하는리스트)

print('\n'.join(match_dna_list(pattern,dna_seq)))

 

이때, 정수 리스트인 경우는 다음과 같이 map으로 str로 변경해준다.

list1=[1,2,3]
print('\n'.join(map(str,list1)))

 

 

반응형
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. 13. 20:07
728x90

[ 코드 ]

#(r,c)가 편해서 백준과 반대로 받음
#변수는 내 맘대로받는거니깐
r,c=map(int,input().split())
idx=int(input())

# 답 찾는 함수
def find_ans(p):
    if(p>r*c): #out of range
        print(0)
    for i in range(r):
        for j in range(c):
            if(arr[i][j]==p):
                print(i+1,j+1)

# 배정 된 표 만들기
arr=[[0 for _ in range(c)]for _ in range(r)]
x,y=0,-1
num=1 #넣을 번호
add=1 #1 or -1
for i in range(c,0,-1):
    j=i+(r-c-1)
    for _ in range(i):
        y+= add
        arr[x][y] = num
        num+=1
    for _ in range(j):
        x+=add
        arr[x][y]=num
        num+=1
    add*=-1 #방향 바꿈


find_ans(idx)

 

 

직접 표를 만들어서 찾는 방식으로 코딩했다.

85%까지는 느리게 느리게 채점이 되더니 결국 틀렸다고 한다..ㅠ

다음에 좀 더 보완해야겠다!

반응형
Posted by mminky