본문 바로가기
반응형

전체 글287

[Algorithm][Python]최장 증가 부분 수열(LIS) 알고리즘 + 코드 이번에 알아 볼 알고리즘은 최장 증가 부분 수열, 통칭 LIS(Longest Increasing Subsequence)입니다. 어떤 수열이 입력으로 주어질 때 해당 수열에서 증가하는 부분 수열의 최대 길이를 구하는 문제에서 볼 수 있습니다. 약간 변형을 해서 사용하면 LCS 알고리즘과도 비슷합니다. 사실 구현만 한다고 했을 때는 굳이 따로 포스팅을 해야할 만큼 거창한 풀이 방법이 있는 것은 아닙니다. 동적 계획법이 익숙하신 분들에게는 그냥 우리가 머리로 생각하듯이 처음부터 원소를 하나씩 순차적으로 탐색하면서 부분 수열의 길이를 세면 되는 거라 코드 작성도 쉬운 편이라고 생각하지만, 제 개인적인 경험으로는 그냥 이런 걸 처음봐서 증가 부분 수열이 무슨 소린지 이해하는 것이 시간이 더 걸렸던 것 같습니다. .. 2023. 10. 5.
[BOJ][Python]11054 풀이 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net def f(n, arr): dp = [1 for _ in range(n)] for i in range(n): for j in range(i): if arr[i] > arr[j]: # 현재 원소가 처음부터 비교해오는 원소보다 크면 if dp[i] < dp[j]+1: dp[i] = dp[j]+1 return dp n = int(input()) a = list(map(int, input().split())) dp = f(.. 2023. 10. 4.
[BOJ][Python]10830 풀이 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net def matmul(mat1, mat2): result = [[0 for _ in range(n)] for _ in range(n)] for i in range(n): for j in range(n): for k in range(n): result[i][j] += mat1[i][k] * mat2[k][j] result[i][j] %= 1000 return result n, b = map(int, input()... 2023. 8. 28.
[BOJ][Python]9935 풀이 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net s = input() e = input() stack = [] for char in s: stack.append(char) if char == e[-1]: if ''.join(stack[-len(e):]) == e: for _ in range(len(e)): stack.pop() ans = ''.join(stack) print(ans if ans != '' else 'FRULA') .. 2023. 8. 27.
[BOJ][Python]5639 풀이 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net import sys ssr = sys.stdin.readline sys.setrecursionlimit(100000) def make_tree(): first_key = int(ssr()) tree = {first_key:[0, 0]} while True: try: cur_key = int(ssr()) tree[cur_key] = [0, 0] parent_key = first_key .. 2023. 8. 26.
[BOJ][Python]2638 풀이 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline def outer_air(): nomis = [] while q: r, c = q.popleft() for dr, dc in dpos: if 0 1: nomis.append((r, c)) q.append((r, c)) for r, c in nomis: board[r][.. 2023. 8. 24.
[BOJ][Python]2448 풀이 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net def recur(n): if n == 3: return [' * ', ' * * ', '*****'] else: half = n//2 before = recur(half) result = ['' for _ in range(n)] for i in range(half): result[i] = ' '*(half) + before[i] + ' '*(half) for i in range(half, n): result[i] = before[i-half] + .. 2023. 8. 23.
[BOJ][Python]2096 풀이 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net import sys ssr = sys.stdin.readline def max_dp(): scores = [board[0][0], board[0][1], board[0][2]] dpos = (-1, 0, 1) for r in range(n): if r == n-1: break tmps = [i for i in scores] scores = [tmps[i]+board[r+1][i] for i in range(3).. 2023. 8. 22.
[BOJ][Python]1987 풀이 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net import sys ssr = sys.stdin.readline def dfs_stack(): global ans s = [(0, 0, board[0][0])] while s: r, c, path = s.pop() if len(path) > ans: ans = len(path) if len(path) == 26: break for dr, dc, in dpos: if 0 2023. 8. 21.
[BOJ][Python]11444 풀이 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net def matrix_multiplication(matrix1, matrix2): result = [[0, 0], [0, 0]] for i in range(2): for j in range(2): for k in range(2): result[i][j] += matrix1[i][k]*matrix2[k][j] result[i][j] %= 1000000007 return result n = int(input()) ans = [[1, 0], [0, 1]] fib_mat = [[1,.. 2023. 8. 19.
반응형

티스토리툴바