one Book a Day

뭔가 의도한대로 안풀고 이상하게 품.. 강의실 배정마냥 배열의 크기안에서 대응안되면 배열 크기 늘리는 방식으로 풀었는데 솔직히 탐색 연산 효율이 완전 에러라 통과된게 이상.. 아래쪽 보면 존재여부 연산에서 visited배열 사용해서 푸는 느낌으로 푸는게 의도였다고 생각함. 다음부터는 저방법을 꼭 생각해낼 수 있었으면 좋겠다. import sys input = sys.stdin.readline N = int(input()) H = list(map(int,input().split())) arrows = [] for i in range(N): if H[i]+1 in arrows: arrows[arrows.index(H[i]+1)] -=1 else: arrows.append(H[i]) print(len(arro..

이분탐색. import sys input = sys.stdin.readline def isPossible(target_time): balloon=0 for staff in make_balloon: balloon += target_time//staff if balloon>=M: return True return False N,M = map(int,input().split()) make_balloon = list(map(int,input().split())) start = 0 end = 1e12 answer = 0 while start

배열 회전 알고리즘. 노가다 회전 def rotate(key, N): def getNewValue(i, j, x, y): key[j , N-i-1] = key[i ,j] if (i == x and j == y): return getNewValue(N-j-1, i, x, y) for i in range(0, int(N/2)): for j in range(i, N-i-1): print(i,j ) tmp = key[i,j] getNewValue(N-1-j, i, i, j) key[j, N-1-i] = tmp ZIP을 사용한 깔끔한 회전 def zip_rotate(original): rotated = np.array(list(zip(*original[::-1]))) return rotated numpy를 이용해..

펜윅 트리(바이너리 인덱스 트리) 시간복잡도 O(MlogN) 구간합, 값 업데이트O(logN) 그림1. 세그먼트 트리 그림2. 펜윅 트리 Fenwick Tree를 구현하려면 어떤 수 X를 이진수로 나타냈을 때 마지막 1의 위치를 알아야 합니다. 마지막 1이 나타내는 값을 L[i]라고 표기하면 L[3]은 11(2)로 1, L(10)은 1010(2)로 2 가 됩니다. 수 N개를 A[1] ~ A[N] 이라고 했을 때, Tree[i]는 A[i] 부터 앞으로 L[i] 개의 합이 저장되어 있습니다. 아래 그림은 각각의 i에 대해서, L[i]를 나타낸 표입니다. 아래 초록 네모는 i부터 앞으로 L[i]개가 나타내는 구간입니다. L[i] = i & -i가 됩니다. 그 이유는 아래와 같습니다. -num = ~num + ..

import sys input = sys.stdin.readline s = input().rstrip() + '.' answer='' cnt=0 for chr in s: if chr=='X': cnt+=1 if cnt==4: answer+='AAAA' cnt=0 else: if cnt==2: answer+='BB.' cnt=0 elif cnt==0: answer+='.' else: print(-1) exit() print(answer[:-1])

구현문제는 난이도와 수고에 비해 그냥 적용 알고리즘이 접하기 쉽다는 이유로 책정난이도가 너무 낮은 것 같다. BFS로 풀었다. import sys input = sys.stdin.readline from collections import deque from copy import deepcopy def is_rotate(cur_gire,next_gire): if next_gire==cur_gire+1: if check_rotate[cur_gire][2]!=check_rotate[next_gire][6]: return True elif next_gire==cur_gire-1: if check_rotate[next_gire][2]!=check_rotate[cur_gire][6]: return True retu..

대표 분할정복이자 재귀문제. 재귀는 3가지가 중요하다. 1. 매개변수(n일때) 2. 최종 계산할 요소(n==0,n==1등 최소 분할 단위) 3. 재귀인자 주입(n-1일때, n+1일때. 각 매개변수의 변동 등.) import sys input = sys.stdin.readline # 핵심은 배열을 4등분하는 분할을 통해 # 배열의 크기가 1인 사각형들의 모임으로 만드는 것. def Z(n,r,c): # 배열의 크기가 1이 되면 0을 정복하여 반환한다. if n==0: return 0 # 배열의 크기를 반을 기준으로 4영역으로 분할한다. harf = 2**(n-1) if r =harf and c

떨어진 단어가 있나 없나 체크하는 문제. 단어 바뀌면 체크해주고 나중에 똑같은거 또나오면 멈춰주면 된다. 약간 구현스러운 문제 import sys input = sys.stdin.readline N = int(input()) cnt=0 for _ in range(N): chr_set = {i:0 for i in range(97,123)} word = input().rstrip() for i in range(len(word)): if chr_set[ord(word[i])]==1: break if i

처음엔 같은 레벨에 있으면 사촌인줄 알고 BFS돌렸었는데 그냥 할아버지 노드가 같으면 사촌인걸 알고 트리로 쉽게 품. import sys input = sys.stdin.readline from collections import defaultdict while 1: n,k = map(int,input().split()) if not n and not k: break arr = list(map(int,input().split())) parents = defaultdict(int) idx=0 for i in range(1,n): parents[arr[i]] = arr[idx] if i

먼가 리팩토링할 수 있을 것 같지만 이하생략.. 평범한 구현문제입니다. import sys input = sys.stdin.readline from collections import deque dx=[0,1,0,-1] dy=[1,0,-1,0] N = int(input()) K = int(input()) snake=deque() board = [[0 for _ in range(N)] for _ in range(N)] for _ in range(K): a,b = map(int,input().split()) board[a-1][b-1]=1 L = int(input()) # 최초 뱀 0,0 방향 오른쪽 snake.append([0,0]) dir=0 board[0][0]=2 t=0 commands=[] for _..