본문 바로가기
반응형

Python/알고리즘문제38

[백준 2592] 부등호 https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 문제 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A ⇒ 2023. 4. 6.
[프로그래머스] 연속 펄스 부분 수열의 합 https://school.programmers.co.kr/learn/courses/30/lessons/161988 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 참 알고리즘 공부하는데 아직도 부족하다고 느껴지는 문제였다. 이 문제의 알고리즘 분류는 누적합 이다 기억하자.. 특정구간의 합을 구한다 => 누적합을 쓰자 1. 아이디어 각 펄스 수열의 누적합을 구한다. 특정 구간의 합이 가장 큰 부분의 합은 누적합의 최소값과 최대값의 차이이다 def solution(sequence): prefixSum = [[0 for _ in range(len(sequenc.. 2023. 3. 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.
[프로그래머스] 사칙연산 https://school.programmers.co.kr/learn/courses/30/lessons/1843 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 연산 기호를 기준우로 좌우로 놔누면서 재귀를 호출한다 연산을 하면서 Max값과 Min값을 계속해서 기록한다 연산 기호를 기준으로 max값과 min값을 계산한다 MAX_DP = [[-987654321 for _ in range(201+1)] for _ in range(201+1)] MIN_DP = [[987654321 for _ in range(201+1)] for _ in range(201+1.. 2022. 12. 28.
[백준 2042] 구간 합 구하기 풀이 세그먼트 트리를 이용한다 구글에서 검색해서 나오는 세그먼트 트리 방법들은 arr에 index를 이용하여 구현하는데 나는 그게 싫어서 class안에다가 range를 넣었다. 그러고 나니 생각보다 코드가 깔끔하게 나왔다. import sys class Tree: def __init__(self, sum, range): self.sum = sum self.range = range self.left = None self.right = None def makeTree(node, arr): if node.range[0] > node.range[1]: return 0 if node.range[0] == node.range[1]: node.sum = arr[node.range[0]] return node.sum .. 2022. 12. 27.
[프로그래머스] 등대 해설 노드가 N개인데 N-1개로 모두 연결되어있다 => 트리구조 트리를 만든다. 트리에서 가장 끝의 리프는 불을 키지 않는다. 자식노드가 모두 불이 꺼져있으면 불을킨다 자식노드가 하나라도 불이꺼져있으면 불을 킨다 처음에 루트노드를 무조건 자식이 2개 이상인걸로 잡았다. 그런데 다시 문제를 풀어보니 루트노드는 아무거나 잡아도 상관없어서 1로 맘편하게 했다 from collections import deque import sys sys.setrecursionlimit(10**9) class Tree: def __init__(self,num): self.num = num self.childs = [] self.parentNode = None def printChilds(self): result = "" for.. 2022. 12. 26.
[알고스팟] 소풍 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.
[프로그래머스] 숫자 타자 대회 https://school.programmers.co.kr/learn/courses/30/lessons/136797 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 해설 너무 어려웠던 문제 ㅠㅠ.. 처음에는 그리디로 풀다가 며칠을 헤메었다. 그리디는 보통 input을 0부터 끝까지 훑는데 하다보니 그리디로는 풀리지 않고, 답을 numbers인덱스의 가장 마지막부터 훑어야 한다는걸 알았다. 즉 dp를 써야된다는 것 파이썬에서 재귀를 돌리다 런타임에러가 난다면 setrecursionlimit을 항상 설정해주자! 아이디어는 다음과 같다. 인풋이 두손가락에 .. 2022. 12. 16.
[프로그래머스] 억억단을 외우자 https://school.programmers.co.kr/learn/courses/30/lessons/138475 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 일단 억억단에서 등장하는 횟수는 약수의 개수와 같다. 고로 약수를 빠르게 얻는법을 알아야 한다. 약수를 얻은 다음에 (숫자,약수) 를 조건에 맞게 sort해준뒤 값을 구한다. 약수 빠르게 구하는법은 추후 정리. 10번문제가 채점 서버의 상태에따라 통과되기도 하고 안하기도 한다. 다른사람 풀이를 돌려봐도 마찬가지... divisor = [0] * 5000001 def solution(e, s.. 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.
[프로그래머스][완전탐색] 카펫 https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 brown+yellow = w*h yellow = (w-2)*(h-2) 위 방정식을 풀면 w, h를 구할 수 있다. 허나 이렇게 풀면 완전 수학문제다 나는 완전탐색 느낌이 나도록 문제룰 풀어보았다. total 셀의 개수는 brown + yellow 이다. yellow = (w-2)*(h-2) 이다. h를 3부터 시작해서 차례로 오름차순으로 증가해 나간다 total이 h로 나눠지는지 확인한다... 2021. 4. 15.
[프로그래머스][완전탐색] 소수 찾기 programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 해설 내가 본래 c++이 주 언어여서 그런지 완전 c++ 스타일로 풀었다. 문제 해결은 간단하다 permutation로직으로 모든 케이스를 생성하고 해당 케이스가 소수인지 아닌지 판별한다 여기서 permutation은 파이썬 내장 함수를 사용해도 되지만 기본적으로 어떻게 하는지 적어보면 for i in range(len(numbers)): if visit[i]:.. 2021. 4. 15.
[프로그래머스][동적계획법] 도둑질 https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 아이디어 어차피 돈은 양수이기에 두칸씩 띄어서 선택하면 장땡이다 첫번째 집과 마지막집은 붙어있기에 동시에 선택을 못한다 둘중하나 선택을 안하면 직선처럼 문제를 생각할 수 있다 두케이스중 큰값을 골라준다 def solution(money): answer = 0 # 마지막집을 선택하지 않은경우 dp = [0] * len(money) dp[0] = money[0] dp[1] = max(mon.. 2021. 4. 14.
[프로그래머스][동적계획법] 등굣길 programmers.co.kr/learn/courses/30/lessons/42898?language=python3 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문재해결 방법 dp[0][0] = 1로 둔다 한 지점에서 위쪽과 왼쪽의 dp값을 더한다. set을 이용해서 웅덩이는 무시한다. 문제에서 1,000,000,007 로 나눠주라는거 주의하자 def solution(m, n, puddles): answer = 0 dp = [[0 for _ in range(m)] for _ in range(n.. 2021. 4. 13.
[프로그래머스][동적계획법] 정수 삼각형 programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 간단한 dp문제. 숫자 하나 기준으로 윗줄의 left right 숫자를 더하며 가장 큰것을 선택해 나가면 된다. 다른사람 풀이보니 한줄에 풀었던데 그런건 어케하는건지.. def solution(triangle): answer = 0 length = len(triangle) dp = [ [0] * i for i in range(1, length + 1)] dp[0][0] = triangle[0][0] for i in range(1, length): fo.. 2021. 4. 13.
[프로그래머스][탐욕법] 큰 수 만들기 programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 그리디 + 스택문제이다. 문제해결 아이디어 : 앞자리에서부터 세어나가며 내림차순이 되도록 만든다 숫자를 스택에 하나씩 쌓아 올려가되 내림차순으로 만든다. 즉 스택을 쌓다가 스택 가장 윗자리 숫자보다 큰 숫자가 나오면 스택을 내림차순이 될 때 까지 pop 해준다. k개를 pop해주었으면 나머지 숫자는 그대로 내비둔다. pop한 갯수가 k보다 부족하면 부족한 수 만큼 뒤에서 덜어준다.(내림차순이므로 뒤에 숫자를 빼는게 유리) def solution(number, k): answer = '' q = [] popcnt = 0 for num in number: .. 2021. 4. 2.
[프로그래머스][탐욕법] 조이스틱 programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 해결방법 글자를 바꿔야할 문자중 현재커서에 가장 가까운 곳을 선택하며 글자를 바꿔나가면 된다. 가장 가까운곳을 구하는 방법은 heapq를 이용하였다. import heapq def solution(name): length = len(name) cursor = 0 answer = 0 currentName = ['A'] * length while current.. 2021. 4. 2.
반응형

티스토리툴바