WoohyunKing의 개발 성장일지

[프로그래머스 Lv.3] N으로 표현

def solution(N, number): answer = -1 if N == number: return 1 # N을 i+1번 사용했을 때 만들 수 있는 값들 dp = [set() for i in range(9)] for i in range(1,9): dp[i].add(int(str(N)*i)) for i in range(2,9): for j in range(1,i): for term1 in dp[j]: for term2 in dp[i-j]: dp[i].add(term1 + term2) dp[..

[백준 24444번] 알고리즘 수업 - 너비 우선 탐색 1

https://www.acmicpc.net/problem/24444import sysinput = sys.stdin.readlinefrom collections import deque# N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다# 정점 번호는 1번부터 N번, 모든 간선의 가중치는 1# 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력n, m, r = map(int,input().split())graph = [[] for _ in range(n+1)]visited = [0]*(n+1)for _ in range(m): u, v = map(int,input().split()) graph[u].append(v) ..

https://www.acmicpc.net/problem/11559import sysfrom collections import dequeinput = sys.stdin.readline# 필드에 여러 가지 색깔의 뿌요를 놓는다# 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.# 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다# 이때 1연쇄가 시작된다.# 뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.# 아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마..

https://www.acmicpc.net/problem/1978import sysinput = sys.stdin.readlinen = int(input())numbers = list(map(int,input().split()))# '1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수count = 0def checkPrime(N): prime_set = set(range(2,N+1)) for i in range(2,N+1): if i in prime_set: prime_set -= set(range(2*i,N+1,i)) if N in prime_set: return True else: return Falsefor num..

https://www.acmicpc.net/problem/12891import sysinput = sys.stdin.readline# DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열# 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용# 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용할 수 있다# 단, 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.s_length, p_length = map(int,input().split())string = input().rstrip()a, c, g, t = map(int,input().split())dictionary =..

https://www.acmicpc.net/problem/2096import sysinput = sys.stdin.readlinen = int(input())dp_max = [0]*3dp_min = [0]*3for _ in range(n): a, b, c = map(int,input().split()) temp_max = dp_max[:] temp_min = dp_min[:] for i in range(3): if i == 0: dp_max[i] = a + max(temp_max[0],temp_max[1]) dp_min[i] = a + min(temp_min[0],temp_min[1]) elif i == 1: ..

https://www.acmicpc.net/problem/2531import sysfrom collections import deque# 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다# 1. 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공# 2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공# (만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공)input = sys.stdin.readlinen, d, k, c = map(int,input().split()..

https://www.acmicpc.net/problem/21921import sys # X일 동안 가장 많이 들어온 방문자 수와 기간 # 첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력 # 만약 최대 방문자 수가 0명이라면 SAD를 출력 # 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력 n, x = map(int,input().split()) input = sys.stdin.readline visit_counts = list(map(int,input().split())) # 1. 시간복잡도 O(N^2) 풀이 # answer = 0 # count = 0 # for i, value in enumerate(visit_counts): # if 0 max_value: m..

https://www.acmicpc.net/problem/2559import sys input = sys.stdin.readline n, k = map(int,input().split()) temp_list = list(map(int,input().split())) value = sum(temp_list[:k]) answer = value for i in range(k,n): value -= temp_list[i-k] value += temp_list[i] answer = max(answer,value) print(answer)이번 문제는 N일 동안 측정된 온도에서 연속 K일간 측정했을 때의 최댓값을 구하는 문제이다. 해당 문제는 단순히 완전탐색으로 풀게되면 O(N*K)의 시간복잡도가 나오게 되는데, N..

1) 슬라이딩 윈도우 알고리즘 개념고정된 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 활용해 문제를 풀이하는 알고리즘을 말합니다. 즉, 이미 한번 구했던 값을 재사용하는 것이 핵심입니다.  배열이나 리스트의 요소의 일정 범위의 값을 비교하거나 연산할 때 사용하면 매우 유용합니다.  문제풀이시 주로 사용되는 경우에는 배열과 그 부분배열을 어떤 조건하에서 계산하는 경우에 주로 사용됩니다. 예를 들어 구간 합 구하기, 부분 문자열 구하기등에 활용될 수 있습니다. 2) 슬라이딩 윈도우 동작원리슬라이딩 윈도우 알고리즘은 연속되는 투 포인터와 유사하게 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘이지만, 부분 배열의 길이(크기)가 고정적 입니다.선형 공간(1차원 배열)을 2회 이상 반복적으로 탐..