목록전체 글 (271)

흙금이네 블로그

[BOJ] 1327 - 소트 게임 (Python)

아이디어 BFS와 딕셔너리를 이용해 각 순열을 만드는 데 뒤집는 횟수를 구한다. 풀이 import sys input = sys.stdin.readline def solution(): N, K = map(int, input().split()) number = list(map(int, input().split())) sorted_num = tuple(sorted(number)) memo = dict() memo[tuple(number)] = 1 queue = [number] while queue: _queue = [] for num in queue: for i in range(N-K+1): temp = num[:] temp[i:i+K] = temp[i:i+K][::-1] if not memo.get(tupl..
알고리즘 2023. 5. 2. 18:42
[BOJ] 3078 - 좋은 친구 (Python)

아이디어 슬라이딩 윈도우로 좋은 친구 쌍을 찾아 더해 나간다. 풀이 import sys input = sys.stdin.readline def solution(): N, K = map(int, input().split()) lengths = [] for i in range(N): name = input().rstrip() lengths.append(len(name)) lengths.append(0) cnt_list = [0]*21 for i in range(K+1): cnt_list[lengths[i]] += 1 e = K res = 0 for s in range(N-1): cnt_list[lengths[s]] -= 1 res += cnt_list[lengths[s]] if e < N-1: e += 1 ..
알고리즘 2023. 5. 1. 18:03
[BOJ] 2306 - 유전자 (Python)

아이디어 동적 계획법으로 부분 서열들 중 KOI 유전자의 최대 길이를 저장해 나간다. 풀이 dp[i][j]는 인덱스 i부터 j까지의 DNA 서열에서 가장 긴 KOI 유전자 길이를 저장한다. def solution(): DNA = input() N = len(DNA) dp = [[0]*N for _ in range(N)] for j in range(1, N): for i in range(j-1, -1, -1): if (DNA[i] == 'a' and DNA[j] == 't') or (DNA[i] == 'g' and DNA[j] == 'c'): dp[i][j] = dp[i+1][j-1]+2 for k in range(i, j): if dp[i][k]+dp[k+1][j] > dp[i][j]: dp[i][j] ..
알고리즘 2023. 5. 1. 18:01
이전 Prev 1 ··· 13 14 15 16 17 18 19 ··· 91 Next 다음