흰 스타렉스에서 내가 내리지

import requests from bs4 import BeautifulSoup request = requests.get('https://www.google.com') raw = request.text html = BeautifulSoup(raw, 'html.parser') requests와 BeautifulSoup라는 클래스가 있다. requests는 웹 페이지에 요청할 수 있는 기능들을 모아놓은 클래스이다. get() 함수에 매개변수로 어느 웹 사이트의 주소를 넣으면, 해당 웹사이트에 대한 정보가 담겨있는 requests객체가 반환된다. raw변수는 사실 html문서가 아닌 String 타입의 그녕 문자열일 뿐이다. BeautifulSoup는 String 타입의 값을 살아있는 HTML문서로 바꿔준다..

다이나믹 프로그래밍을 구현하는데, dp배열은 꼭 1차원배열이 아니라 2차원 배열도 가능하다는 점을 염두해두면 좋겠다. n = int(input()) cost = [] for _ in range(n): cost.append(list(map(int, input().split()))) dp = [[0]*3 for _ in range(n)] dp[0] = cost[0] for i in range(1, n): dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0] dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1] dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2] print(min(dp[n-1..

LIS 알고리즘을 이용. LIS배열 자체가 아닌 LIS의 길이를 구하는 알고리즘에서 응용을 해야한다. LIS에 관한 내용은 알고리즘 카테고리에 다음에 포스트할 예정. from bisect import bisect_left n = int(input()) arr = list(map(int, input().split())) lis = [] insert_pos = [] for i in range(n): if i==0: lis.append(arr[i]) insert_pos.append(i) continue if lis[-1] < arr[i]: insert_pos.append(len(lis)) lis.append(arr[i]) else: idx = bisect_left(lis, arr[i]) insert_pos.a..

일단 배열을 어떻게 저렇게 가로 세로로 칸을 나누는지 감을 못잡았다 2차원 배열을 1차원 배열로 풀어서, 각 요소마다 인덱스를 부여. 가로방향을 1, 세로방향을 0이라고 생각하면, 총 경우의 수는 2의n*m제곱. 1과0으로 표현할 거니까 비트마스킹을 이용하여 저장. 인덱스 k = i*m + j이고, 이 k번째 요소가 0인지 1인지 확인하려면 b&(1

다이나믹 프로그래밍으로 풀어야 하는 건 알겠었는데, 어떻게 해야될지 좀 헤맸던 문제. 검사할 배열을 1부터 하나하나 늘려가면서, 이케이케 n = int(input()) arr = list(map(int, input().split())) dp = [1 for _ in range(n)] for i in range(n): for j in range(i): if arr[j] < arr[i]: dp[i] = max(dp[i], dp[j]+1) print(max(dp)) https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 3..

보호되어 있는 글입니다.

백트래킹과 dfs로 푸는 문제다. 처음에 귀찮아서 permutation으로 풀었는데, 역시나 시관초과가 나왔다. import sys n = int(input()) data = list(input()) arr = [[None]*n for _ in range(n)] k = 0 for i in range(n): for j in range(i, n): arr[i][j] = data[k] k+=1 sol = [] def solve(i): if i == n: print(*sol) sys.exit() return if arr[i][i] == '-': cand = [j for j in range(-10, 0)] elif arr[i][i] == '+': cand = [j for j in range(1, 11)] elif..

보호되어 있는 글입니다.

별다른 해법이 떠오르지 않아 처음부터 브루트포스로 접근했다. 그런데 시간초과가 났다. 아래는 시간초과가 난 코드이다. from itertools import combinations n = int(input()) data = list(map(int, input().split())) arr = [] for i in range(1, n+1): for c in combinations(data, i): _sum = sum(c) arr.append(_sum) i = 1 while True: if i not in arr: break i += 1 print(i) 여기서 쓸데없이 시간을 지체했던 부분은, 마지막 while 문에, if i not in arr: 를 실행할때마다 O(n)의 시간복잡도를 가진다는 것. 코드를 ..

보호되어 있는 글입니다.