https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 이중 for 문을 사용해서 n^2의 시간 복잡도를 나타내지만, 문제를 푸는 것에는 문제가 없다고 생각했다. 시간제한 1초에 메모리 제한 512mb 이므로 약 데이터의 수가 10000000개여야 매모리 40mb이를 차지하기 때문이다. import sys s = sys.stdin.readline() a = [] for i in range(1,len(s)): for j in range(len(s)-i): a.append(s[j:j+i]) print(len(set(a)))..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 아마 append 의 시간 복잡도가 o(n)으로 알고 있다. import sys n = int(sys.stdin.readline()) stack = [] count = 0 answer = [] flag = True for i in range(0,n): x = int(sys.stdin.readline()) while ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 우선 이문제는 일반적인 for 문을 이용해서 풀으면 시간 초과의 문제가 나오게 된다. 아마 n^2의 시간 복잡도 때문이라고 생각한다. python이 1초에 몇 만번인지는 기억이 안나지만 그만큼 연산을 하기 때문에 import sys n, m = map(int, sys.stdin.readline().split()) num_list = [0]+list(map(int,sys.st..

https://programmers.co.kr/learn/courses/30/lessons/12981?language=python3 코딩테스트 연습 - 영어 끝말잇기 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] [0,0] programmers.co.kr def solution(n, words): answer..

LIS란 가장 긴 증가하는 부분 수열을 나타낸다. 주어진 수열 리스트를 가장 길게 만드는 것이다. LIS를 풀기위한 가장 일반적인 방법은 DP 이다. ex) n = int(input()) num = list(map(int, input().split())) num_len = [1 for i in range(n)] for k in range(1,n): for j in range(k): if num[j] < num[k]: num_len[k] = max( num_len[k],num_len[j]+1) print(max(num_len)) 위 알고리즘의 시간복잡도는 O(n^2)을 갖게 된다. 첫번째 요소부터 k 번째 요소까지 비교를 한 후 뒤에 있는 요소가 num[k] 가 더 크다면 k까지의 최장 값을 현재값과 j번..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net import sys import heapq n = int(sys.stdin.readline().rstrip()) num_list = [] for i in range(n): x = int(sys.stdin.readline().rstrip()) if x != 0 and x 0: heapq.heappush(num_list,(x,x)) 이지

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net https://www.daleseo.com/python-heapq/ [파이썬] heapq 모듈 사용법 Engineering Blog by Dale Seo www.daleseo.com import sys import heapq num_list = [] t = int(sys.stdin.readline().rstrip()) for i in range(t): num = int(sys...

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net https://www.daleseo.com/python-heapq/ [파이썬] heapq 모듈 사용법 Engineering Blog by Dale Seo www.daleseo.com 위의 방식만 사용하면 쉽다 힙 잘알아두자 import sys import heapq num = int(sys.stdin.readline().rstrip()) num_list = [] for i in..