해킹왕 양선규

문자열, 슬라이딩 윈도우 문제이다.슬라이딩 윈도우는 고정된 범위를 가지고 어떤 리스트나 문자열 등을 한칸씩 옆으로 옮겨가며 조건을 검사하는 알고리즘을 뜻한다. # 문자열, 슬라이딩 윈도우from collections import dequeimport sysinput = sys.stdin.readlineS, P = map(int, input().split()) # DNA 길이, 비번 길이DNA = input().strip()ACGT = list(map(int, input().split()))def slidingWindow():    # 결과 담을 변수    result = 0    # 큐에 초기값 집어넣기    queue = deque()    for i in range(P):        queue.ap..

# 구현, 수학, 정렬 import sys input = sys.stdin.readline N = int(input()) # 수의 개수, 홀수 number = [] for _ in range(N): number.append(int(input())) if N == 1: # 수가 1개일 경우 print(f'{number[0]}\n{number[0]}\n{number[0]}\n0') else: # 수가 3개 이상일 경우 number.sort() # 최빈값 구하기, 첫번째 숫자 넣어놓고 시작한다 result = [number[0]] curCnt = 1 maxCnt = 1 # 리스트를 한번 순회하며 최빈값을 찾는다 for i in range(1, N): if number[i] == number[i-1]: # 이전..

BFS, 백트래킹 문제이다. 거창한 백트래킹.. 이라기 보다, 그냥 모든 경우의 수를 찾기 위한 부분에서 백트래킹이 사용되었다. BFS가 메인이고 백트래킹은 거드는 느낌의 문제이다. # BFS, 백트래킹# 백트래킹으로 벽 3개를 세우는 경우의 수를 전부 구한 후, BFS로 바이러스를 전파시킨 후 안전 영역의 개수를 센다from collections import dequeimport sysimport copyinput = sys.stdin.readlineN, M = map(int, input().split()) # 행, 열graph = [] # 지도for _ in range(N):    graph.append(list(map(int, input().split())))dx = [-1, 1, 0, 0]dy =..

DFS 문제이다. 트리가 주어지며, 각 노드는 실외/실내의 특성을 갖는다.산책 루트는 반드시 실내로 시작해서 실내로 끝나야 한다. 그 사이에 실외가 몇개 있든 상관 없다. 이러한 산책 루트가 최대 몇개인지를 출력하면 되는 문제이다. 방향만 바꾼 것도 포함이다. 1->3 , 3->1 이 루트는 별개의 루트이다.  처음엔 문제 지문 그대로 코드로 옮겨 풀었었다.import sysinput = sys.stdin.readlineN = int(input()) # 노드 개수inout = input().strip()inout = [''] + [int(x) for x in inout] # 실내여부, 노드번호와 동기화를 위해 맨앞 빈값 추가graph = [[] for _ in range(N + 1)] # 노드 연결정보,..

import sysinput = sys.stdin.readlineN = int(input())numbers = list(map(int, input().split()))M = int(input())result = [0 for _ in range(N + 1)] # 입력값과 인덱스를 맞추기 위해 + 1result[1] = numbers[0]for i in range(2, N + 1):    result[i] = result[i-1] + numbers[i-1]for _ in range(M):    i, j = map(int, input().split())    if i == 1:        print(result[j])    else:        print(result[j] - result[i-1]) 누적 ..

import sysinput = sys.stdin.readlineINF = int(2e9)N, M = map(int, input().split())number = [int(input()) for _ in range(N)]number.sort()def twoPointer():    result = INF    start = 0    end = 1    while end N:        if number[end] - number[start] >= M:            result = min(result, number[end] - number[start])            start += 1            if start == end:                end += 1        e..

# 정사각형 한 변의 길이 : 2, 4, 8 ....import sysinput = sys.stdin.readline# 2의 N승 크기, R행 C열N, R, C = map(int, input().split())# 행/열이 길이 나누기 2이상이면 -> 행 : 아래쪽 사분면/ 열 : 오른쪽 사분면le = 2**N# 결과값 편하게 더하기 위해 만든 배열num = [[0,1], [2,3]]# 각사분면 0,0값, 변길이, 행, 열def divide(z, le, row, col):    if le == 2: # 2*2 정사각형 도달 시        print(z + num[row][col])        return    plus = (le * le) // 4 # 각 사분면 0,0 값의 차이    half = le..

import sysinput = sys.stdin.readline# 집, 공유기 개수N, C = map(int, input().split())house = [int(input()) for _ in range(N)]  # 집 좌표house.sort() # 집을 순서대로 정렬# 이분 탐색으로 인접 공유기 간의 최소 거리를 찾는다def binarySearch():    end = house[-1] - house[0] # 최대 거리    if C == 2:        return end    start = 1 # 최소 거리    result = 0 # 결과를 저장할 변수    # 최적의 거리를 찾을 때까지 반복한다    while start end:        cur = house[0] # 마지막으로 공유..

import sysinput = sys.stdin.readlineN = int(input())def plus(num):    if num == 1:        return 1    elif num == 2:        return 2    elif num == 3:        return 4    else:        return plus(num-1) + plus(num-2) + plus(num-3)for _ in range(N):    print(plus(int(input()))) 재귀 방식( 바람직하지 않음 ) DP문제다. 두가지 방식으로 풀어보았다. 하나는 재귀 방식, 하나는 DP테이블을 사용하는 방식.이해를 하긴 했으나 뭔가 와닿지가 않는다. 아 이런거구나~ 하고 이해해놓고 잠시 뒤에, 근..

import copyimport sysinput = sys.stdin.readlineN = int(input())numList = list(map(int, input().split()))dp = copy.deepcopy(numList)for i in range(1, N):    for j in range(i):        if numList[i] > numList[j]:            dp[i] = max(dp[i], dp[j] + numList[i])print(max(dp)) 가장 긴 증가하는 부분 수열(LIS)문제와 거의 흡사한 문제이다. 문제의 원리는 거의 같지만 요구하는 출력값이 다르다. LIS는 수열이 길이를 출력했다면, 이 문제는 수열을 모두 더한 값을 출력한다. dp테이블로 사용하기 ..