알고리즘2022. 2. 23. 23:25
728x90

[ 문제 ]

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

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

 

 

[ 내가 푼 코드 ]

문제가 풀리기는 했으나 Greedy 알고리즘을 이용하지는 못했음

더보기
n,k = map(int,input().split())
a = []
coin = 0
for _ in range(n):
    a.append(int(input()))
a.sort(reverse=True)

for i in a:
    if k >= i:
        if k%i ==0:
            coin += k//i
            break
        coin += k//i
        k = k%i

print(coin)

 

 

[ 해결 아이디어 ]

 

* 그리디(탐욕) 알고리즘

: 눈 앞의 이익만 우선 추구하는 알고리즘

( greedy : 탐욕스러운, 욕심이 많은 )

 --> knapsack문제, 동전 문제(각 동전은 작은 동전의 배수)

 

 

입력에 보면 Ai는 Ai-1의 배수 라는 조건이 있다.

즉, 동전이 1, 5, 10, 50, 100 .. 이런 식으로 큰 동전은 작은 동전의 배수가 된다.

이러한 유형은 GREEDY 알고리즘으로 해결 할 수 있다.

 

 

[ 해결 코드 ]

n,k = map(int,input().split())
a = []
coin = 0
for _ in range(n):
    a.append(int(input()))
a.sort(reverse=True)

# GREEDY
for i in a:
    coin += k//i
    k = k%i
print(coin)

 

 

[ 결과 ]

반응형
Posted by mminky
알고리즘2022. 2. 23. 17:02
728x90

[ 문제 ]

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

 

11399번: ATM

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

www.acmicpc.net

 

 

[ 코드 ]

n = int(input())
p = list(map(int,input().split()))
p.sort()

total = 0
for i in p:
    total += i*n
    n -= 1

print(total)

 

 

[ 결과 ]

반응형
Posted by mminky
알고리즘2022. 2. 23. 15:53
728x90

[ 문제 ]

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

 

2839번: 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그

www.acmicpc.net

 

 

[ 코드 ]

n = int(input())
bag = 0

while 1:    # 계속 반복함
    if n%5 == 0:    #5의 배수이면
        bag += n//5 #몫 만큼 bag에 더함
        break       #n이 5의 배수이면 몫 만큼의 가방만 필요하므로 끝!
                # (예) n=10이라면 n//5 = 2 -> 2개의 가방만 있으면 됨
    # 예외처리
    if n<3:
        bag = -1
        break
    # 3kg은 빼주면서 가방 하나씩 더함
    n -= 3
    bag += 1

print(bag)

 

 

[ 결과 ]

반응형
Posted by mminky
알고리즘2022. 2. 23. 15:48
728x90

코딩테스트를 준비하기 위해 백준사이트를 이용하려고 하는데

어떻게 이용해야할지 고민이었다.

그러다 검색을 통해 결론을 도출했다.

 

1. 백준 사이트

그리디, 탐색, 다이나믹(동적) 프로그래밍 문제 풀기

2. 프로그래머스

코딩테스트 연습 ( https://programmers.co.kr/learn/challenges )

 

( 한 문제당 소요시간은 45분으로 잡는다! )

 

 

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

 

우선, 백준 사이트에서 원하는 알고리즘 별로 문제를 연습하는 방법이다.

문제 > 알고리즘 분류 로 들어간다.

 

여기서 원하는 알고리즘을 선택한다.

 

원하는 문제를 클릭하고 풀면 된다!

 

ex) 백준 - 그리디 알고리즘 모음

https://www.acmicpc.net/problemset?sort=ac_desc&algo=33 

 

문제 - 1 페이지

 

www.acmicpc.net

 

반응형
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. 5. 31. 00:37
728x90

[ 문제 ]

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

 

13300번: 방 배정

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수학여행에 참가하는 학생 수를 나타내는 정수 N(1 ≤ N ≤ 1,000)과 한 방에 배정할 수 있는 최대 인원 수 K(1 < K ≤ 1,000)가 공백으로 분리되어

www.acmicpc.net

 

 

[ 코드 ]

 

#n: student num
#k : max people# in one room
n, k = map(int, input().split())
st = [[0]*2 for _ in range(6)] #성별2개 6학년

#입력
for _ in range(n):
    # st[학년][성별]
    s,y= map(int, input().split())
    st[y-1][s-1] += 1
#    print(st[y-1][s-1])

room_num=0
for a in range(6):#학년
    for b in range(2):#성별
        #print(st[a][b])
        #math.ceil써도 :)
        if(st[a][b]%k == 0):
            room_num += st[a][b]/k
        else:
            room_num += st[a][b]//k + 1
print(int(room_num))

 

 

[ 결과 ]

반응형
Posted by mminky
파이썬2021. 5. 31. 00:34
728x90

[ 문제 ]

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

 

10828번: 스택

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

 

[ 코드 ]

#시간초과 시 추가하면 좋은 구문
# https://www.acmicpc.net/board/view/44990
import sys
input=sys.stdin.readline

n = int(input()) #명령의 수
stack=[]

def push(x):
    #리스트의 마지막에 추가
    stack.append(x) #딱히 int(x)할 필요는 없을 듯

def pop():
    if(len(stack)==0):
        print(-1)
    else:
        print(stack.pop())

def size():
    print(len(stack))

def empty():
    if(len(stack)==0): #비면
        print(1)
    else: #안 비면
        print(0)

def top():
    if(len(stack)==0):
        print(-1)
    else:
        print(stack[-1])


for i in range(n):
    command=input().split() #push 1 같은 애들 분리
    if(command[0] == 'push'):
        push(command[1])
    if (command[0] == 'pop'):
        pop()
    if (command[0] == 'size'):
        size()
    if (command[0] == 'empty'):
        empty()
    if (command[0] == 'top'):
        top()

 

 

[ 결과 ]

반응형

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

[ Python ] 백준 11729 - 시간초과 해결!!  (0) 2021.06.06
[ Python ] 백준 13300 파이썬  (0) 2021.05.31
[ Python ] 백준 1735 파이썬  (0) 2021.05.31
[ Python ] 백준 1475 파이썬  (0) 2021.05.31
[ Python ] 백준 1453 파이썬  (0) 2021.05.31
Posted by mminky