Python

[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] 백준 - 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..

큐(queue)

큐 스택과 같이 데이터를 임시 저장하는 자료구조이다. 하지만 스택과 반대로 가정 먼저 넣은 데이를 가장 먼저 꺼내는 선입선출(FIFO: First In First Out) 구조를 가진다.예: 놀이공원에서 보통 줄 서는 구조 큐에 데이터를 넣을 떄는 인큐(enqueue), 큐에서 데이터를 꺼낼 때는 디큐(dequeue) 함수를 정의 데이터를 직접 꺼내는 것이 아니라 두개의 포인터(front, rear) 를 사용해서 위치를 나타낸다. 코드 # 고정 길이 큐 구현하기 with 링 버퍼. # 기존의 리스트로 dequeue 구현 시 시간 복잡도가 O(n) 으로 상당히 비효율적이다. # 이를 해결하기 위해 링 버퍼를 사용. from typing import Any class FixedQueue: class Empt..