본문 바로가기
반응형

파이썬 알고리즘8

[알고스팟] 쿼드 트리 뒤집기 https://algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 algospot.com 해설 분할정복을 이용한다. 각 구역은 4조각으로 나누면서 재귀를 호출한다. 재귀를 호출하면서 이미지를 상하 뒤집는다 서적에 나온대로 string을 매번 인덱스를 계산하는게 아니라 반복자를 이용하여 필요한 만큼 가져다 쓴다 lt : left top rt : right top lb : left bottom rb : right bottom def decomp.. 2023. 1. 6.
[알고스팟] 소풍 algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 algospot.com 해설 고등학교때 배운 조합 문제이다. 경우의 수가 중복되지 않도록 순서를 강제 해야 된다 import sys C = int(input()) for _ in range(C): N, M = map(int, sys.stdin.readline().rstrip().split()) flist = list(map(int, sys.stdin.readline().rstrip().split())) friends = [[] for _ in range(10)] i = 0 whil.. 2022. 12. 21.
[알고스팟] 보글게임 algospot.com :: BOGGLE 보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 algospot.com 해설 문제에서 적힌것과 같이 dp로 푸는 대표적인 문제이다. 문제와 부분문제의 개념에 대해 알아야 한다 나는 다음과 같이 정리했다 문제 : 문제에 주어지는 문제 부분문제 : 주어진 문제의 input에서 조각내어 input을 사용하는 문제 가령 인풋이 abcdef 가 들어왔다 하면, a를 빼면 bcdef 이렇게 조각내서 풀면 그게 부분문제 이다 부분문제로 완전탐색을 만들면 dp로 변환하기가 몹시 편리하다 1. 완전 탐색으로 풀기 아래 코드로 하면.. 2022. 12. 21.
[알고스팟] 록 페스티벌 https://www.algospot.com/judge/problem/read/FESTIVAL algospot.com :: FESTIVAL 록 페스티벌 문제 정보 문제 커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 www.algospot.com 풀이 대충 보아하니 무식하게 for문 돌려서 전체 케이스로 풀어도 될거 같은 조건인데 파이썬으로 그렇게 푸니 시간초과가 납니다. 다른사람들 답을 보니 c언어에서는 그냥 무식하게 포문만 돌려도 되던데 말이죠. 특정구간의 합을 빠르게 구하기 위한 알고리즘 방법으로는 세그먼트 트리, 그리고 합을 누적해서 배열을 만드는 방법이 있는데, 문제에서는 값의 수정이 .. 2022. 12. 20.
파이썬 약수 구하기 1. 설명 어떤수의 약수를 구하면 N=A*B 형태로 나타낼 수 있다. 하나의 약수, 예를들어 A를 구하면 B는 N/A로 구할 수 있다 A와 B가 값이 다르다면 2개를 세어주어야 하고, A와 B가 같다면 1개만 세어주어야 한다 작은숫자부터 약수 A를 구한뒤 A*A가 N(N은 A*B)보다 작다면, A와 B는 다른값이므로 2개를 세어준다. 여기서 B는 A보다 큰값을 가지게 된다. 만약 A를 구하고, A*A가 N이라면 A와 B는 같은 값이다. 이후 A보다 큰값에서 약수 계산은 이미 계산되어있으므로 불필요하다 이때 시간복잡도는 루트N이다 def divisor(x): i = 1 result = 0 while i*i 2022. 12. 13.
[프로그래머스] 디펜스 게임 https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 게임을 하다 죽었다고 치자. 죽었을 때 과거의 적들중 가장 값이 큰값에 k를 소모하면 더 오래 게임하지 않을까? 알고리즘 과정은 다음과 같다 while문을 돌리면서 게임을 한다 게임을 하다가 죽으면 이전 적들중 가장 큰 값에 k를 사용한다 => 이전적들은 heapq로 저장하면 가장 큰놈을 찾을 수 있다 내가 실수한점 k는 죽었을 때 한번만 써야 하는데, 죽었을 때 k를 while문으로 전부.. 2022. 12. 12.
[프로그래머스] 쌍둥이 빌딩 숲 https://school.programmers.co.kr/learn/courses/30/lessons/140105?language=python3# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 나머지 연산이 있는걸 보니 전형적인 dp 문제이다. (n,c) 를 (n-1,c-1) 과 (n-1,c)로 나누어 생각한다. 새로들어온 n이 두개가 다 가장 뒤로 배치된다고 하자. n은 어차피 가장 크므로 나머지 경우의수는 solution(n-1, c-1)이 될 것이다. 만약 n의 건물 사이에 아래처럼 다른건물이 들어오거나 앞서있다면? (n, n-1)의 이 한쌍.. 2022. 12. 10.
파이썬 알고리즘 팁 및 필수 지식 1. input 빠르게 받기 import sys n, m = map(int, sys.readline().split()) 2. 문자 숫자 변환 chr 함수와 ord 함수를 이용한다 chr(65) # A ord('A') # 65 3. List Comprehension 응용 keys = [ key for key, value in dict ] values = [ value for key, value in dict ] keysValues = [ (key,value) for key, value in dict] map = [ [] for _ in range(n)] # 텅빈 2차원 배열 zeros = [0] * 10 >>> [ [i,i+1] for i in range(10)] [[0, 1], [1, 2], [2, 3].. 2022. 12. 8.
반응형

티스토리툴바