Algorithm Problem/Python

[python] 프로그래머스 - 쿼드압축 후 개수 세기 (월간 코드 챌린지 시즌1)

🤔문제 해결 압축문제 백준에서도 비슷한 문제를 풀어본적이 있다. 리스트를 실제로 자르지 말고 나뉘는 인덱스만 구해서 해결하는게 좋다. 인덱스를 구할 때는 네모의 시작점의 위치만 구한다. 거기에 + 네모의 길이만큼 해주면 네모를 완성시킴 시작점을 기준으로 하면 위의 경우는 0, 0 그리고 크기는 8이다. 다음 4가지는 0, 0, 4 0, 4, 4 4, 0, 4 4, 4, 4 다음 네모는 크기를 절반으로 나누고 x에 더하거나 y에 더하거나 x와 y 둘다 더해서 시작값을 만든다. 다음은 이 네모가 모두 같은 숫자인지 판별하는 것인데 네모중 하나의 값을 초기값으로 잡고 네모안의 값을 하나씩 비교해가면서 초기값과 다른게 하나라도 있으면 압축할 수 없으므로 또 그 네모를 잘라준다! 💻소스 코드 def solutio..

[python] 프로그래머스 - 3진법 뒤집기 (월간 코드 챌린지 시즌1)

🤔문제 해결 3진법으로 만든다. 뒤집지마라 stack구조로 문자열을 쌓으면 저절로 뒤집은 형태가 나온다. 10진법으로 바꿔준다. 문자열은 앞에서부터, 3의 n승은 뒤에서부터 만들어준다. 💨 실제 대회시간 때 급하게 풀다가 n 이 3보다 작을 때 처리를 안해줘서 한두문제 틀리고 넘어갔다. ( 시간 깜빡하다가 늦게 입장 함😂 ) 💻소스 코드 def solution(n): answer = 0 # 3진법 mok = 0 nmg = 0 number = '' while True: mok = n // 3 nmg = n % 3 number += str(nmg) if mok < 3: number += str(mok) break n = mok print(number) # 10진법으로 바꾸기 leng = len(number)..

[python] 백준 - 5430. AC

🤔문제 해결 S2 | 자료구조, 데크, 구현 리버스와 제거 두가지 오더가 있다. 리버스를 하게 되면 O(N)의 시간복잡도 발생 그러므로 리버스를 하지말고 이게 뒤집힌 상황인지 아닌지만 구분해준다. 그 후 그대로이면 맨 앞의 숫자를 제거하고 뒤집힌 상황이면 맨 뒤의 숫자를 제거한다. 💻소스 코드 from collections import deque for tc in range(int(input())): # RR이면 원래상태이므로 제거해줌 order = input().replace('RR', '') n = int(input()) number = input()[1:-1] if number: number = deque(list(map(int, number.split(',')))) # R은 뒤집지 말고 my_re..

[python] 백준 - 2004. 조합 0의 개수

🤔문제 해결 S2 | 수학 진짜 팩토리얼로 구해서 문제를 해결하게 되면 시간초과 발생 끝자리가 0이라는 것은 10의 배수 10은 2와 5로 구성되어 있음 2와 5 짝이 맞아야 10이 되므로 2의 개수와 5의 개수중 더 작은게 10의 개수이다. 💻소스 코드 N, M = map(int, input().split()) # 진짜 팩토리얼로 구해서 문제를 해결하게 되면 시간초과 발생 # 끝자리가 0이라는 것은 10의 배수 # 10은 2와 5로 구성되어 있음 # 2와 5 짝이 맞아야 10이 되므로 2의 개수와 5의 개수중 더 작은게 10의 개수이다. def count_number(n, k): count = 0 while n: n //= k count += n return count five_count = count..

[python] 백준 - 2110. 공유기 설치

🤔문제 해결 S2 | 이분탐색 특정 범위 안에서 개수를 정한다? => 이분 탐색 공유기를 설치할 수 있는 최소간격과 최대간격의 중간값부터 시작 중간값(공유기 설치 간격)으로 공유기를 설치 했을 때 설치한 공유기가 부족하면 설치 간격을 좁혀서 더 많이 설치하자 설치한 공유기가 많거나 같으면 설치한 간격을 늘려서 덜 설치하거나 최대로 간격을 늘려보자 💻소스 코드 import sys N, C = map(int, input().split()) house = [int(sys.stdin.readline()) for _ in range(N)] # 정렬 house.sort() # 와이파이 간격을 얼마나 해야할지 모르니 최대거리와 최소거리의 중간부터 시작 left = 1 right = house[-1] - house[0..

[python] 백준 - 1735. 분수 합

🤔문제 해결 S2 | 수학 분수를 더해준다. ( 이 정도는 다 알고있을 것이다. ) 분자와 분모의 최대공약수(GCD)를 구한다. ( math 함수에 있는 기능 ) 분자와 분모를 GCD로 나누어준다. 💻소스 코드 import math a1, b1 = map(int, input().split()) a2, b2 = map(int, input().split()) bunjja = a1 * b2 + a2 * b1 bunmo = b1 * b2 my = math.gcd(bunjja, bunmo) bunjja //= my bunmo //= my print(bunjja, bunmo) 📕문제 확인 출처: BACKJOON ONLINE JUDGE 링크: https://www.acmicpc.net/problem/1735 1735..