백준
[동적계획법] 가장 긴 바이토닉 부분 수열
가장 긴 증가하는 부분 수열의 응용버전이다. 이전 문제를 풀었다면 어렵지는 않은 문제일 것 같다. 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net from sys import stdin N, A = int(stdin.readline()), list(map(int, stdin.readline().split(" "))) T_L, T_R = [1] * N, [1] * N def get_table_left(ind: int): m = 0 for i in range(ind, -1, -1): if A[ind] > A[i] and m < T_L..
[동적 계획법] 1로 만들기
다른 사람들의 풀이를 보니, 메모이제이션으로 쉽게 풀 수 있는걸 너무 복잡하게 생각한 것 같다. 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net from sys import stdin N = int(stdin.readline()) m = {1: 0} def check(no): global m if no
[동적 계획법] 정수 삼각형
1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 저번 문제와 마찬가지로 DP 테이블을 이용해서 쉽게 풀 수 있었다. from sys import stdin N = int(stdin.readline()) L = [] while True: line = list(map(int, stdin.readline().split())) if len(L) == 0: L.append(line) else: prev = L[len(L) - 1] next_line = [] for i, v in enumerate(line): if i == 0: next_line.append(v + prev[0]) elif ..
[동적 계획법] RGB 거리
1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이번 문제를 풀면서 DP 테이블 개념을 알게 되어서 좋았다. 재귀 & 메모이제이션이 아니라 이런 식으로도 풀 수 있구나 하는... 역시 아직 배울게 많다 ㅠ from sys import stdin N = int(stdin.readline()) L = [] RESULT = [] while True: [R, G, B] = map(int, stdin.readline().split()) if len(L) == 0: L.append([R, G, B]..
[동적 계획법] 신나는 함수 실행
동적 계획법의 핵심은 return 값의 재사용. 재사용 할 값을 어떻게 효율적으로 저장 및 탐색할 수 있는지에 대한 고민과 그에 따른 자료구조 선택이 중요한 것 같다. 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net from sys import stdin w_dict = {} input_abc_arr = [] while True: [a, b, c] = map(int, stdin.readline().split()) if a == -1 and b == -1 and c == -1: break else: input_ab..
[동적 계획법] 피보나치 함수
백 트래킹이 마무리가 되고 동적 계획법으로 넘어왔다. 동적 계획법 자체는 거창한 내용은 없었고, 값을 재활용한다는 핵심 개념만 알고 가면 될 것 같다. 값을 저장하고 꺼내오는 과정에서의 최적화에 대한 고민이 중요할 것 같다. 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net from sys import stdin T = int(stdin.readline()) f_arr = [-1] * 41 f_arr[0] = [1, 0] f_arr[1] = [0, 1] def f(n: int): global f_arr if f_arr[n] != -1: return f_arr[n] else: [z1, o1] = f(n - 1..
[백트래킹] 스타트와 링크
오랜만에 백준 포스팅을 한다. 천천히 진행되던 백트래킹이 드디어 끝났다. 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net from sys import stdin from itertools import combinations as cb N = int(stdin.readline()) ARR = [] def get_team_status(team_list: list): total = 0 global ARR for x, y in cb(team_list, 2): total = total + ARR[x - 1][y - 1] + ARR[y - 1..
[백트래킹] N과M(4)
15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net n과m 시리즈를 전부 포스팅 할 필요는 없을 것 같아서 바로 4로 넘어왔다. 파이썬 문법이 간결해서 좋은데, 솔직히 삼항 연산자는 가독성도 그렇고 뭔가 마음에 안 든다... 자바나 자바스크립트처럼 cond ? a : b 하면 얼마나 좋아... 어차피 syntax sugar인데 짧게 하지.... 문제 자체는 별거 없었다. 재귀함수는 명료한 exit조건이 관건인데 항상 똑 부러지게 바로 결정을 못 하고 긴가민가 하다... N, M = map(int, (input()..
[백트래킹] N과M(1)
15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 = NpM 이니까 파이썬에 내장된 순열과 조합 구현 가능한 라이브러리가 있더라;; 너무 편해... from itertools import permutations as pm N, M = map(int, (input()).split()) for i in pm(list(map(lambda x: x + 1, range(N))), M): print(*i) ''' def get_result_recursive(pre:..
[정렬] 단어 정렬
1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 입력받은 단어들을 1. 짧은 순 2. 사전 순 으로 정렬하면 된다. 짧은순으로 정렬한 후 그 안에서 사전순으로 정렬하려고 하면 복잡해진다. 그냥 1. 사전 순 2. 짧은 순 으로 순서대로 정렬하면 조건에 만족하게 된다. from sys import stdin N = int(stdin.readline()) words: set = set() for i in range(N): word = str(stdin.readline()).replace('\n', ""..