해킹왕 양선규

그리디 문제이다. 문제는 간단한데 해결 방법이 도저히 떠오르질 않았다. 한번에 3개의 전구가 바뀌니까 엄청나게 많은 경우의 수가 있을 것이라 생각했고, 아무리 생각해도 답을 도출할 방법이 떠오르질 않아서 다른 코드를 참고했다. 근데 참고해도 이해가 잘 안된다. 이 코드가 어째서 정답을 도출하는지. 이론적으론 이해했지만 와닿지가 않는다.# 그리디import sysinput = sys.stdin.readlineN = int(input())origin = list(map(int, input().strip()))target = list(map(int, input().strip()))# 1번 인덱스 전구부터 하나씩 누를지 말지 결정하는 함수def solve(A, B):    press = 0    for i in..

문자열, 슬라이딩 윈도우 문제이다.슬라이딩 윈도우는 고정된 범위를 가지고 어떤 리스트나 문자열 등을 한칸씩 옆으로 옮겨가며 조건을 검사하는 알고리즘을 뜻한다. # 문자열, 슬라이딩 윈도우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테이블을 사용하는 방식.이해를 하긴 했으나 뭔가 와닿지가 않는다. 아 이런거구나~ 하고 이해해놓고 잠시 뒤에, 근..