[백준] 11053번 가장 긴 증가하는 부분 수열 [Python] - 다이나믹, LIS
어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열$($LIS: Longest Increasing Subsequence$)$이라 한다. LIS의 길이를 구하는 문제 더보기 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N $(1 ≤ N ≤ 1,000)$이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 $A_i$가 주어진..
[백준] 15663~15666번 N과 M[9~12] [Python] - 순열, 조합, 중복
백준 문제 사이트 N과 M[9], N과 M[10], N과 M[11], N과 M[12] 중복된 원소가 포함되기도 한 N개의 자연수가 주어졌을 때, M개의 순열, 조합, 중복 순열, 중복 조합을 구하는 문제 N과 M[7, 8]리뷰 https://savvy0402.tistory.com/192 dict.fromkeys$($딕셔너리의 키 값들, 현재 생성할 딕셔너리의 일괄적으로 들어가게 될 값$)$ 값을 안 넣으면 모든 key의 값이 None으로 저장됨 N과 M[9] from sys import stdin from itertools import permutations input = stdin.readline N, M = map(int, input().split()) s = sorted(input().rstrip(..
[백준] 7569번 토마토 [Python] - BFS
익은 토마토는 하루가 걸려서 상,하,좌,우,앞,뒤로 1칸 떨어진 안익은 토마토를 익게 만든다. H, N, M과 토마토의 상태가 M개씩 N개의 줄로 H번 주어질 때, 모든 토마토가 익는 최소 일수를 구하는 문제 1: 익은 토마토 0: 안익은 토마토 -1: 빈 칸 익지 않는 토마토가 있을 경우$($토마토는 자동으로 익지 않고, 위의 규칙에 의해서만 익는다고 하자.$)$ >>> -1 출력 더보기 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은..
[백준] 10973번 이진 순열 [Python]
더보기 문제 1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오. 사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다. N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다. 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 입력 첫째 줄에 N$(1 ≤ N ≤ 10,000)$이 주어진다. 둘째 줄에 순열이 주어진다. 출력 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. https://www.acmicpc.net/problem/10973 시간 초과 ..
[백준] 11403번 경로 찾기 [Python] - DFS, BFS, 플로이드–워셜
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 $(i, j)$에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 문제 플로이드–워셜, dfs, bfs를 사용한 코드들을 작성해봤습니다. 더보기 문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 $(i, j)$에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N $(1 ≤ N ≤ 100)$이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 총 N개의 줄에 걸쳐서 문제..
[백준] 15656, 15657번 N과 M[7, 8] [Python] - 중복 순열, 중복 조합
백준 문제 사이트 N과 M[7] N과 M[8] N과 M[3], N과 M[4]에서는 1~N까지 자연수로 이루어진 길이가 M인 수열을 출력했다면, N과 M[7], N과 M[8]은 주어진 N개의 자연수로 이주어진 길이가 M인 수열을 출력하는 문제입니다. 주어진 자연수를 정렬하고, 속도를 높이기 위해 문자로 변환 후, 중복 순열, 중복 조합의 경우를 구하고 출력하는 코드입니다. product, combinations_with_replacement의 반환 값은 튜플 형태의 원소를 지니고 있어서, 튜블 내 원소를 ' '$($공백$)$으로 이어 붙인 후 join 매소드로 줄바꿈으로 문자를 이어 붙였습니다. N과 M[3], N과 M[4] 리뷰 https://savvy0402.tistory.com/6 https://sa..
