Algorithm Problem/Python

[python] SWEA - 10726. 이진수 표현

🤔문제 해결 lv3 | 문자열, 진수 💨 bin(숫자) 를 이용하면 간단하게 숫자를 2진수로 바꿀 수 있다. (하지만 0b가 앞에 붙기 때문에 떼어줘야함) 💨 나머지는 뒤에서 N개만큼 가져와서 판단 ( N개가 안된다면 아웃, 0이 포함되어있다면 아웃) 💻소스 코드 for tc in range(int(input())): N, number = map(int, input().split()) bin_number = list(map(str, str(bin(number))[2:]))[-N:] print(f'#{tc + 1}', end=' ') if len(bin_number) < N: print('OFF') else: if '0' in bin_number: print('OFF') else: print('ON') 📕..

[python] 백준 - 14501. 퇴사

🤔문제 해결 S4 | 완전탐색 or DP 난이도가 S4인 만큼 완전탐색으로 해결해도 된다. 하지만 저번에 한번 풀어봤으므로 이번에는 DP로 해결해봤다. 일하는 날을 맨 뒤에서부터 계산해보자 7일을 선택하면 근무시간 초과로 이익 0 6일도 마찬가지 5일을 선택하면 이익 15 4일을 선택하면 이익은 20에, 5일에도 일할 수 있으므로 +15 해서 35 3일을 선택하면 이익은 10에 4일에도 일할 수 있으므로 (4일에 일하면 위에서 확인했듯이 5일도 일한다) +35 이므로 45 2일을 선택하면 이익은 20 1일을 선택하면 이익은 10에 4일부터 일할 수 있으므로 ( 아까 그 35 를 더한다) +35 이므로 45 결과적으로 1,4,5 일하면 45 또는 3,4,5 일하면 45 이 두가지의 경우가 최대이다. 한가지..

[python] 백준 - 14235. 크리스마스 선물

🤔문제 해결 S2 | 우선순위 큐 우선순위 큐 문제, 파이썬의 힙큐 모듈을 사용하자. 힙큐 모듈은 최소값을 반환하는 최소힙을 기본으로 한다. 따라서 음수로 값을 넣고 값을 뽑아서 다시 음수를 곱해주면 최대값이 된다. 인풋값이 0일 때 가지고 있는 선물이 있으면 선물을 나눠준다. 없으면 꽝 인풋값이 0이 아닐 때 선물을 충전한다. 💻소스 코드 import heapq if __name__ == '__main__': N = int(input()) pq = [] # 선물을 담을 리스트 ( 우선순위 큐 ) for _ in range(N): input_value = input() if input_value == '0': # 인풋값이 0일 때 if pq: # 선물이 있으면 선물 print(-heapq.heappop(..

[python] 백준 - 2014. 소수의 곱

🤔문제 해결 G2 | 수학, 우선순위 큐 DP로 구해보려고 했지만 역시 아니었다. 2**31 길이의 배열은 좀 아닌거 같다. 어려워서 알고리즘 분류를 보니 우선순위 큐로 해결하는 문제였다. 우선순위큐는 큐 안에 있는 값들 중 최소 값을 반환할 수 있다. 파이썬에서는 힙큐를 불러와서 사용하고 힙큐는 최소힙 기반으로 되어있다. 해결방법은 최초 힙큐에 주어진 소수를 넣는다. 힙큐에서 숫자를 하나씩 꺼내면서 주어진 소수들을 곱해서 힙큐에 넣는다. (이 때 꺼내는 횟수가 소수의 곱들 중에서 N번째 수이다) 하지만 이렇게 되면 중복이 발생한다. ( 2*3 이나 3*2 ) 3*2는 되지만 2*3은 안된다는 식으로 힙큐에서 꺼낸 수가 소수로 나누어 떨어지면 그 다음 소수는 건너뛴다. 결과는 아래와 같다 💻소스 코드 i..

[python] SWEA - 10761. 신뢰

🤔문제 해결 lv3 | 시뮬레이션 💨 예를 들어 B가 움직이면서 버튼을 누를 동안 O는 움직일 순 있어도 버튼을 누를 순 없다. (반대도 마찬가지) 💨 버튼을 누르는 순서가 있기 때문! 💨 하지만 움직일 순 있기 때문에 미리 버튼으로 이동해있어도 된다. 💨 클래스 한번 써보고 싶어서 써봄. 굳이 쓸 필요는 없다. (클래스도 반만쓴거라) 💻소스 코드 class Robot: def __init__(self): self.location = 1 self.time = 0 def status(self): print(f'위치:{self.location}, 시간:{self.time}') def operate(robot, button): # 현재위치와 눌러야 되는 버튼 global time # 시간이 같으면 로봇이동 i..

[python] 백준 - 3190. 뱀 (삼성 SW 역량 테스트 기출 문제)

🤔문제 해결 G5 | deque, 시뮬레이션 deque 를 이용하여 뱀을 만든다. deque의 앞쪽은 꼬리, deque의 뒷쪽은 머리 (반대로 해도 상관없음) 머리를 방향에 따라 한칸 늘린다.(deque에 머리 추가: append()) 벽에 부딪히지 않고, 뱀의 몸통에 부딪히지 않으면 통과 이 때 머리의 위치에 사과가 있으면 통과 없으면 꼬리를 줄인다.( deque에서 꼬리를 제거: popleft()) 매초 세주면서 해당 초에 오더가 있으면 ( 방향 바꾸기 ) 진행 방향을 바꿔준다. 주의: 사과를 먹으면 맵에서 사과 지우기 💻소스 코드 from sys import stdin from collections import deque input = stdin.readline def move_snake(direc..