분류 전체보기
-
[프로그래머스] 기능 개발 (python)개발/알고리즘 2022. 9. 20. 21:28
https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 맨 앞기능이 완성될 때까지 기다리다가, 완성되면, 배포할 수 있는 것들을 찾아서, 배포하는 방식으로 코딩. 처음에 문제를 잘 못읽어서, 비효율적인 방법으로 코드 작성 def solution(progresses, speeds): # 가장 앞 기능을 항상 가리키고 있다가, 앞 기능이 다 완성되면 배포를 시작 # 100%가 된 것들은 list에서 제외하고, 개수는 따로 세고 있기 -> 배포할 때 초기화..
-
[프로그래머스] 올바른 괄호 (python)개발/알고리즘 2022. 9. 13. 21:28
https://school.programmers.co.kr/learn/courses/30/lessons/12909 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 전형적인 stack을 사용하는 괄호판별문제이다. def solution(s): answer = True stack = [] i = 0 while i < len(s): cur = s[i] # 현재가 ) 라면, 이전에 (가 나왔어야 짝이 맞는 것이다. if cur == ')': if not stack: answer = False break else: judge = stack.pop() if judge..
-
[백준] 2302 극장좌석 (python)개발/알고리즘 2022. 9. 2. 23:48
https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 문제설명 극장 좌석과 입장권이 있을 때, 입장권에 적힌 좌석 숫자 -1, +0, +1 인 좌석에 앉을 수 있을 때, 가능한 경우의 수는? 접근1 완전탐색 dfs로 처음에 접근했는데, pypy3으로 해도 시간초과 N = int(input()) M = int(input()) # 고정석 개수 arr = [0]*(N+1) fix_set = set() for _ in range(M): fixed = int(input(..
-
[백준] 16194 카드구매하기2 (python)개발/알고리즘 2022. 8. 31. 21:29
https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net ✋ 접근방법 dp를 이용해서 풀이 중복해서 사용가능하므로 knapsack과는 다르게, 앞에서부터 각 무게의 최소값을 찾아나가면 됨 👏 코드 # knapsack 알고리즘 이용 -> 중복허용 가능하므로 dp 갱신부분의 j루프를 앞에서부터 진행! N = int(input()) arr = [0]+ list(map(int,input().split())) # index : 카드개수, value : 최소가격 dp..
-
[프로그래머스] 124나라의숫자 (python)개발/알고리즘 2022. 8. 30. 21:42
https://school.programmers.co.kr/learn/courses/30/lessons/12899 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 십진법 숫자를 1, 2, 4 를 이용해서 1 => 1 2 => 2 3 => 4 4 => 11 5 => 12 6 => 14 7 => 21 와 같이 변형시키는 문제이다. 3진법과 비교시 아래와 같다. 3진법 : 01 02 10 124 나라 : 1 2 4 3진법 : 11 12 20 124 나라 : 11 12 14 매 자리수를 구하는 방식은 주어진 수 n을 3으로 나눈 나머지가 0이면 4, 1이면 1, ..
-
[백준] 1406 에디터 (python)개발/알고리즘 2022. 8. 29. 23:41
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제 설명 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입..
-
[백준] 1850 최대공약수 (python)개발/알고리즘 2022. 8. 24. 20:54
https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net # 예를들어 1이 10개 있다면, 1이 2개 5개 인 경우 는 모두 1이 10개인 경우의 약수가 되므로, 아래처럼 시도해봤는데,,, # 필요충분조건이 왜 되는지 잘 모르겟음 A, B = map(int,input().split()) import math gcd = math.gcd(A,B) print('1'*gcd)
-
[백준] 1182 부분수열의 합 (python)개발/알고리즘 2022. 8. 22. 10:53
N, S = map(int,input().split()) arr = list(map(int,input().split())) count = 0 def nCr(n, r, start, rest, comb): # n개 중 r개 뽑는데, 현재 뽑아야하는 index 시작이 start, 남은 뽑을 것 개수가 rest # start에서 n - rest index까지 뽑을 수 있음 global count if rest == 0: if sum(comb) == S: count += 1 # print(comb) else: for i in range(start, n-rest+1): comb[rest-1] = arr[i] nCr(n, r, i+1, rest-1, comb) return for r in range(1,N+1): c..