📌문제 출처 프로그래머스 LV 3 https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❓ 문제 📗 풀이 코드 ''' 빈 heap 자료구조를 두개 만든다. 삽입 연산은 heappush, 최소값 삭제 연산은 heappop을 사용한다. 최대값 삭제 연산은 원소가 하나 남을 때까지 최소값 삭제 연산을 함과 동시에 다른 빈 heap에 삽입 연산을 진행한 후 heap 두개의 이름을 변경해준다. ''' from heapq import heapify, heapp..
📌문제 출처 프로그래머스 LV 2 https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❓ 문제 📗 풀이 코드 ''' numbers를 for 반복문으로 하나씩 확인 stack이 비었거나, 이번 num이 stack[0]보다 작으면 해당 num의 인덱스도 stack appendleft. (제일 오른편 수의 뒷 큰수부터 찾아야하므로) 이번 num이 stack[0]보다 크면 : stack이 비거나 stack[0]이 num보다 클 때까지 ans[stack...
📌문제 출처 프로그래머스 LV 2 https://school.programmers.co.kr/learn/courses/30/lessons/12949 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❓ 문제 📗 풀이 코드 def solution(arr1, arr2): ans = [[0]*len(arr2[1]) for _ in range(len(arr1))] for i in range(len(arr1)): for j in range(len(arr2[1])): row = arr1[i] col = [row2[j] for row2 in arr2] tmp = 0 fo..
📌문제 출처 프로그래머스 LV 3 https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❓ 문제 📗 풀이 코드 ''' i행 j열 도달경로의 최대값은 i-1 행의 j-1,j번째까지 도달 경로의 최대값 + i행 j열 값 위 점화식을 가지고 dp 알고리즘으로 문제 해결 ''' def solution(triangle): dp = [0]*len(triangle) # dp[i]는 확인하는 행의 각 열까지 도달하는 최대값 dp[0] = triangle[0][0]..
📌문제 출처 백준 단계별 문제풀이 : 동적계획법 3 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 동일한 문제 조건에서 일렬로 집을 칠하는 RGB거리 1 문제에서 원형으로 된 집을 칠하는 문제이다. 첫번째 집을 칠했을 때의 색상에 따른 경우를 먼저 나누고 RGB거리 1과 동일한 방식으로 진행하자. ''' input = open(0).readline def solution(): n = ..
📌문제 출처 백준 단계별 문제풀이 : 동적계획법 1 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net ❓ 문제 📗 풀이 코드 input = open(0).readline R=G=B=0 # 아무 집도 칠하지 않았을 때 이전 집을 R,G,B로 칠했을 때를 가정한 비용 for _ in range(int(input())): r,g,b = map(int,input().split()) # 이번 집을 칠하는 비용 R,G,B = r+min..
📌문제 출처 백준 단계별 문제풀이 : 동적계획법 3 https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net ❓ 문제 📗 풀이 코드 * pypy3로 제출 시 성공(python 3는 시간 초과) ''' 기본적으로 dfs+dp 문제이나, 방문확인을 하는 방법이 복잡하기에 비트마스크를 활용하는 방법이다. dfs를 통해 일의 개수와 일하는 사람 수를 늘려가면서 해당 일까지 일을 참여한 사람이 모두 일할 수 있는 조합 중 최소값을 찾아서 dp에 저..
📌문제 출처 백준 단계별 문제풀이 : 동적계획법3 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net ❓ 문제 📗 풀이 코드 - list 자료 구조 활용 input = open(0).readline def solution(): s = [0]*21 # 1부터 20까지의 정수를 연산하기 위함 for _ in range(int(input())): ord = input().split() if len(ord)==2 : x = int(ord[1]) ord = ord[0] if ord == 'a..
