썸네일 [BOJ] #2531 회전초밥 (Python, Sliding window, 시간초과 해결) 🌱 문제https://www.acmicpc.net/problem/2531 🌱 풀이0. 입력받기input = sys.stdin.readlinen, d, k, c = map(int, input().split())belt = []for _ in range(n): belt.append(int(input())) *처음 생각했던 방법 (시간 초과 발생)최대 접시 수는 30,000개이니까 브루트 포스로 충분히 가능하다고 생각했습니다. 리스트를 돌면서 초밥의 종류만 세주면 되네!하고 아래와 같이 코드를 짰는데 시간초과가 발생하였습니다.answer = 0for i in range(n): belt.append(belt.popleft()) answer = max(len(set(list(belt)[:k] ..
썸네일 [BOJ] #10830 행렬 제곱 (Python, 분할정복) 🌱 문제  🌱 풀이이 문제의 관건은 100,000,000,000까지 가질 수 있는 매우 큰 지수를 효율적으로 처리하는 것입니다. 행렬을 반복적으로 곱하는 대신, 행렬의 거듭제곱을 분할 정복(Divide and Conquer) 기법으로 계산합니다. 1) 입력 받기N, B = map(int, input().split())matrix = []for _ in range(N): matrix.append(list(map(int, input().split()))) 2) 행렬 제곱을 구하는 함수(Divide and Conquer)def pow_matrix(matrix, B): """ 행렬 matrix를 B 제곱하는 함수 """ if B == 1: return [[element..
썸네일 [BOJ] #5430 AC (Python, Deque, 시간 초과 해결) 🌱 문제https://www.acmicpc.net/problem/5430 🌱 풀이1. 입력 받기T = int(input())for _ in range(T): p = input() p.replace("RR", "") p = list(p) n = int(input()) array = deque(eval(input()))테스트 케이스 개수인 T를 int로 받아서 해당 개수만큼 반복문을 들어갑니다.수행해야할 함수 p는 우선 string으로 받습니다. 이때, RR은 뒤집고 바로 뒤집기 때문에 배열에 아무런 변화를 주지 않으므로 replace()함수로 바로 지웠습니다. 그리고나서 string을 list로 바꾸어 이후에 반복문을 수행하며 함수 하나하나를 탐색할 수 있도록 하였습니다. 가..
썸네일 [프로그래머스] 가장 많이 받은 선물(파이썬, 구현, 2024 KAKAO WINTER INTERNSHIP) 🌱 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🌱 풀이 1. 변수 설정 문제 설명에 위와 같이 주고받은 선물과 선물 지수를 표로 나타내주는데, 이걸 그래도 구현하면 됩니다! table은 주고받은 선물의 개수를 담을 2차원 리스트이고, gift_index는 선물지수를 저장할 리스트입니다. answer는 다음 달에 각각 받을 선물 개수를 담을 리스트이다. 즉, answer 리스트에 있는 최댓값이 정답이 됩니다. table = [[0 for _ in range(len(friends))] for __ in range(len(friends))] gift_..
썸네일 [BOJ] #15486 퇴사2 (Python, Dynamic Programming, 시간 초과 해결) 🌱 문제 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 퇴사일과 각 일마다 상담에 소요되는 일수와 받을 수 있는 금액이 주어질 때, 얻을 수 있는 최대 이익을 출력하는 문제입니다. 백준 14501 퇴사 문제와 같은 문제인데, 시간복잡도를 줄여서 제출해야 맞출 수 있습니다. 🌱 풀이 1 - 시간 초과 dp = [0 for _ in range(n + 1)] for i in range(n): for j in range(i + meetings[i][0], n + 1): # i일 상담 진..
썸네일 [BOJ] #4179 불! (Python, BFS) 🌱 문제 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 🌱 풀이 지훈이가 미로에서 탈출할 수 있는 최소 거리를 구하는 문제인데, 불도 같이 사방으로 확산하기 때문에 움직이는 객체가 2개인 BFS 문제입니다. 1. 미로 정보와 지훈이와 불의 초기 위치 정보 우선 미로 정보를 graph에 저장합니다. 그리고 graph에서 지훈이의 초기 위치("J")와 불의 초기 위치("F")를 각각 jihoon_start와 fire_start에 저장합니다. h, w = map(int, input().split(..
썸네일 [BOJ] #2758 로또 (Python, Dynamic Programming) 🌱 문제 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 🌱 풀이1 - 백트랙킹 풀이(시간 초과) m개의 자연 수 중에서 n개를 고르는 문제라 당연히 백트랙킹이라고 생각하고 처음에는 백트랙킹으로 풀었습니다. def backtracking(n, m, lotto): if len(lotto) == n - 1: global answer answer += (m - (lotto[-1] * 2) + 1) return for i in range(lotto[-1]*2, m + 1): tmp = i for j in range(n - l..
썸네일 [BOJ] #15649) N과 M(1) (Python, Back tracking) 🌱 문제 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 출력 수열은 사전 순으로 증가 🌱 풀이 1) 파이썬 라이브러리 사용 백트랙킹 알고리즘의 대표적인 문제라고 해서 풀어본건데 문제 읽자마자 그냥 permutations 쓰면 되는 것 아님 ? ! ? 그래서 순열 뽑아주는 permutations 라이브러리 써서 제출하니까 정답,, 💙 from itertools import permutations n, m = map(int, input().spli..
썸네일 [BOJ] 11729 하노이 탑 이동 순서 (Python, Recursion) 🌱 문제 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 🌱 풀이 바킹독님의 알고리즘 강의 영상의 풀이법을 참고했습니다. 우선, 아래 그림처럼 n번째 원판을 1번 장대에서 3번 장대로 옮기기 위한 과정을 생각해보겠습니다. 1. n-1개의 원판을 1번에서 2번 장대로 옮긴다. 2. n번 원판을 1번에서 3번 장대로 옮긴다. 3. n-1개의 원판을 2번에서 3번 장대로 옮긴다. 이를 귀납적으로 설명하면, 원판 n-1개를 장대 a번에서 장대 b번으로 옮길 수 있다면, 원판 n개를 장대 a'에서 장대 b'..
썸네일 [프로그래머스] 광물 캐기 (Python, 구현) 🌱 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 작업을 끝내기까지 필요한 최소한의 피로도를 구하는 문제 광물을 모두 캐거나 곡갱이를 모두 사용하면 작업 끝남 어떤 광물을 어떤 곡갱이로 캐는지에 따라 소모되는 피로도가 다름 하나의 곡갱이로 5개의 광물을 캘 수 있음 🌱 풀이1 완전 탐색 → 시간 초과 처음에는 곡갱이(picks)의 개수가 최대 15개 이고, 광물(minerals)의 길이는 최대 50이라 완전탐색으로 풀 수 있겠다고 생각하였습니다. 왜냐하면 곡갱이 1개당 광물 5개를 캘 수 있으므로 최대로 필요한 곡갱이 수는 10개입니다. 또, 곡갱이..
썸네일 [프로그래머스] 과제 진행하기(Python, Stack, Implementation) 🌱 문제 https://school.programmers.co.kr/learn/courses/30/lessons/176962?language=python3# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🌱 풀이 1. 문자열로 받는 시간 정보를 처리 후, 정렬 for plan in plans: hh, mm = plan[1].split(":") plan[1] = int(hh) * 60 + int(mm) plan[2] = int(plan[2]) plans.sort(key=lambda x: x[1]) plans에 시작 시간과 소요 시간이 모두 문자열로 주어지므..
썸네일 [프로그래머스] 전력망을 둘로 나누기 (Python, BFS, 완전탐색) 🌱 문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🌱 풀이 n은 2 이상 100 이하인 자연수이고 wires는 길이가 n-1인 2차원 배열로, 시간복잡도가 $O(100^2)$을 넘지 않으므로 (n-1 배열 탐색($O(N)$) * BFS 시간복잡도($O(N)$)) 완전 탐색을 이용해서 풀이합니다. 1. 전력망(graph) 정보를 2차원 리스트 형태로 표현하기 graph = [[] for _ in range(n + 1)] for wire i..
라이브러리 브랜드 그룹 | hellomygreenworld

티스토리툴바