Algorithm Problem

[python] 백준 - 14889. 스타트와 링크

🤔문제 해결 S3 | 브루트포스, 백트래킹 재귀 함수를 이용하여 A팀을 구한다. 전체 멤버의 절반이 될 때까지 팀을 구성 set으로 구한다. ( 교집합을 사용해서 B팀을 구하기 위해 ) 두 팀을 구했으면 각 팀의 모든 조합을 테이블에서 값을 계산해서 구해준다 이번에는 콤비네이션 모듈을 사용했다. 테이블의 값을 모두 더해주고 두 팀의 총합을 빼준뒤 절대값을 씌워서 차이를 구한다. 최소값으로 답을 갱신해준다. 💨 팀을 구할 때 콤비네이션을 쓰지 않은 이유는 콤비네이션은 모든 경우의 수를 구하기 때문 전체 회원 [0, 1, 2, 3] 일 때 A 팀이 0,1 B팀이 1,2 인 경우와 A 팀이 2,3 B팀이 0,1 인 경우의 답은 같지만 콤비네이션은 이 두가지 경우를 구하므로 비효율적 💻소스 코드 from ite..

[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..