본문 바로가기

파이썬 알고리즘 문제풀이27

BOJ 16139 인간-컴퓨터 상호작용 https://www.acmicpc.net/problem/16139 진짜로 푸는데 개오랜 시간이 걸렸다.. 일반적인 누적합 문제와 다른 점은 문자별로 다른 누적합 리스트를 가지고 있어야 한다는 것이다. 예를들어 그냥 단순 특정구간 덧셈 계산을 했을때는 일정구간 자연수에 대한 누적합 리스트가필요했지만 이건 문자 별로 필요한 문제이다. 이문제가 골치아팠다. 그럼 리스트 26개를 만들어야되는데, 동적으로 리스트명을 만들어 안에 append시킬 수 있을까? 라는 생각을 했다. 그런데 동적 변수 할당은 있어도 동적으로 리스트를 만드는 것은 존재하지 않았다. 이중리스트를 만들어 인덱스로 접근하는 발상을 생각해내는데 오랜 시간이 걸렸다.. 일단 for 문으로 26개의 0을 원소로하는 리스트를 요소로 가지는 이중 리스.. 2023. 4. 8.
BOJ 1028 체스판칠하기. 실버4밖에 되지 않는데 매우 어려웠기 때문에 풀이를 참조하여 해결하였다.. 생소한 유형이라 그런듯. from sys import stdin def main(): def input(): return stdin.readline().rstrip() N,M = map(int,input().split()) matrix = [input() for i in range(N)] w_board = [ "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", ] b_board = [ "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", .. 2023. 4. 8.
boj 2798번 - 블랙잭 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 브루트 포스라니 이름이 간지난다.. 조합 문제다. 파이썬에는 콤비네이션 내장 함수가 있다... from sys import stdin from itertools import combinations def main(): def input(): return stdin.readline().rstrip() N,M = map(int,input().split()) ls1= l.. 2023. 4. 7.
BOJ 2559 수열 - python 이런 문제.. 처음의 풀이. from sys import stdin def main(): def input(): return stdin.readline().rstrip() N,K = map(int,input().split()) ls1= list(map(int,input().split())) ls2 = [] sum1 = 0 for i in range(N-K+1): for j in range(K): sum1 += ls1[i+j] ls2.append(sum1) sum1 = 0 print(max(ls2)) if __name__ == "__main__": main() 하지만 시간 복잡도상 N*K 최악의 경우 N ^2 이기 때문에 입력값이 100000인 이상 시간 초과를 피할 수 없다.. 다음 풀이. from sy.. 2023. 4. 7.

티스토리툴바