📌문제 출처 백준 단계별 문제풀이 - 스택 2 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net ❓ 문제 ❗ 풀이 스택과 인덱스 활용 📗 풀이 코드 import sys input = sys.stdin.readline n = int(input()) nums = list(map(int,input().split())) ans = [-1]*n stack = [] # 오큰수를 찾아야하는 nums의 인덱스를 담아준다. for i in range(n): # stack이..
📌문제 출처 백준 단계별 문제풀이 - 동적 계획법 2 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net ❓ 문제 ❗ 풀이 dp : 냅색 문제 응용 📗 풀이 코드 import sys input = sys.stdin.readline n,m = map(int,input().split()) memories = list(map(int,input().split())) costs = list(map(int,input().split())) dp = [[0]*(sum(..
📌문제 출처 백준 단계별 문제풀이 - 동적 계획법 2 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net ❓ 문제 ❗ 풀이 dp 활용 📗 풀이 코드 import sys input = sys.stdin.readline n,k = map(int,input().split()) coins = [int(input()) for _ in range(n)] dp = [0]*(k+1) dp[0] = 1 # 0으로 0을 만드는 방법 1가지 추가, 이걸 지정해줘야 첫번..
📌문제 출처 백준 단계별 문제풀이 - 동적 계획법 2 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net ❓ 문제 ❗ 풀이 dp + dfs 📗 풀이 코드 import sys from collections import deque input = sys.stdin.readline # dfs 함수 생성 def dfs(row,col): if (row==m-1) and (col==n-1) : # 도착했을 경우 return 1 if dp[row][col] != -1..
📌문제 출처 백준 단계별 문제풀이 - 동적 계획법 2 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net ❓ 문제 ❗ 풀이 누적합, 동적계획법 📗 풀이 코드 --- python 3는 시간 초과 / pypy3는 통과 import sys input = sys.stdin.readline # 누적합 구하는 함수 def prefix(chaps): sum_prefix = [0] tmp_sum = 0 for chap in chaps: tmp_sum +..
📌문제 출처 백준 단계별 문제풀이 - 그래프와 순회 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ❓ 문제 ❗ 풀이 bfs 활용 📗 풀이 코드 import sys from collections import deque input = sys.stdin.readline n,k = map(int,input().split()) arrival = {i:0 for i in range(0,100001)} # 해당 지점 방문 여부 ..
📌문제 출처 백준 단계별 문제풀이 - 그래프와 순회 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ❓ 문제 ❗ 풀이 bfs 활용 📗 풀이 코드 from collections import deque input = sys.stdin.readline n,m = map(int,input().split()) maze = [list(map(int,input().strip())) for _ in range(n)] # 해당 칸으로 진행 가능한지, 진행하면 최소로 진행한 거리인지 확인하는 ..
📌문제 출처 백준 단계별 문제풀이 - 우선순위 큐 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net ❓ 문제 ❗ 풀이 heap 자료구조 활용 📗 풀이 코드 import sys from heapq import heappush, heappop input = sys.stdin.readline nums = [] for _ in range(int(input())): i = int(input()) if i : p_m = -1 if i
