one Book a Day

단방향 그래프 dfs 탐색 def find_path(s,g): global answer if s==g: answer = 1 return for next_node in graph[s]: if not visited[next_node]: visited[next_node] = True find_path(next_node,g) for test in range(1,int(input())+1): V, E = map(int,input().split()) graph = {i:[] for i in range(1,V+1)} answer = 0 visited = {i:False for i in range(1,V+1)} for _ in range(E): a, b = map(int,input().split()) graph[a] ..

stack써서 푸는 문제. stack하나로도 가능한데.. def bracket_inspection(s): dic = {')':0, '}':0,']':0, '(':0, '{':0,'[':0} stack1 = [] stack2 = [] for chr in s: if chr in dic: dic[chr] += 1 stack1.append(chr) if dic[')'] != dic['('] or dic['}'] != dic['{'] or dic[']'] != dic['[']: return 0 while stack1: check = stack1.pop() if check == ')' or check == '}' or check==']': stack2.append(check) else: if check =='(':..

KMP연습할 겸 풀었다. 하나만 찾으면 되는 문제 import sys input = sys.stdin.readline def make_pattern(s): counter = 0 for idx in range(1, len(s)): while counter > 0 and s[counter] != s[idx]: counter = lose_funtion[counter-1] if s[counter] == s[idx]: counter += 1 lose_funtion[idx] = counter def KMP_pattern_matching(p, s): counter = 0 p_size = len(p) for idx in range(len(s)): while counter > 0 and p[counter] != s[id..

펠린드롬 찾는 문제. 처음에 회문 1개인줄 모르고 다찾는 구조로 짰다가 급하게 수정.. import sys input = sys.stdin.readline def find_palindrome(N,M,sentences): for i in range(N): for j in range(N-M+1): if sentences[i][j] == sentences[i][j+M-1]: left = j right = j+M-1 while sentences[i][left] == sentences[i][right] and left

그냥 counting import sys input = sys.stdin.readline from collections import defaultdict def count_chrs(s1, s2): char_set = defaultdict(int) for chr in s2: char_set[chr] += 1 max_cnt = 0 for char in s1: max_cnt = max(max_cnt,char_set[char]) return max_cnt for test in range(1,int(input())+1): str1 = input().rstrip() str2 = input().rstrip() print(f'#{test} {count_chrs(str1, str2)}')

5가지 정렬 방법. 1. 선택정렬 2. 버블정렬 3. 삽입정렬 4. 퀵정렬 5. 병합정렬 import sys sys.stdin = open('input.txt') # 선택정렬. 앞에서부터 최솟값을 찾아 swap 시킨다. def sort_arr(arr): for i in range(N-1): min_value = float('inf') min_idx = 0 for j in range(i,N): if arr[j] < min_value: min_value = arr[j] min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr for test in range(1, int(input())+1): N = int(input()) init_arr = li..

다 세줬다. 뭔가 개선 가능할 것 같기도 하다.? 근데 모르겠다 import sys sys.stdin = open('input.txt') # 각 행에 몇칸짜리 자리가 있는지 count 해 cells 에 저장합니다. def count_row(n, target, puzzle): sum_seat = 0 for row in range(n): cnt = 0 cells = [] for column in range(n): if puzzle[row][column]: cnt += 1 else: if cnt: cells.append(cnt) cnt = 0 cells.append(cnt) sum_seat += cells.count(target) # 원하는 자리가 있다면 세줍니다. return sum_seat # 글자가 들어..

구현문제 풀듯 정석으로 다 세줬다. 더 좋은 방법이 있으려나? import sys sys.stdin = open('input.txt') # 파리채로 쳐 죽입니다. def count_kill_flies(x,y, fly_killer_size, matrix): kill = 0 for i in range(x, x+fly_killer_size): kill += sum(matrix[i][y:y+fly_killer_size]) return kill def kill_flies(matrix_size, fly_killer_size): matrix = [list(map(int, input().split())) for _ in range(matrix_size)] # 파리채로 칠 범위를 지정합니다.(왼쪽 위 idx) kill_..

1. 투포인터 2. 덱 3. 힙 import sys sys.stdin = open('input.txt') def special_sort(length, arr): arr.sort() max_idx = length-1 min_idx = 0 special_arr = [] # 정렬한 배열의 양끝에서부터 하나씩 특별한 배열로 삽입합니다. # 양끝이 만나면 종료합니다. while min_idx

색깔 2개 말고 더 늘어나도 대응가능. 근데 메모리는..? 모르겠다ㅎㅎ import sys sys.stdin = open('input.txt') def color_areas(color_cnt): # 색을 칠할 칠판입니다. matrix = [[[] for _ in range(10)] for _ in range(10)] for _ in range(color_cnt): r1, c1, r2, c2, color = map(int, input().split()) # 내 색깔이 칸에 안칠해져있다면 칠합니다. for i in range(r1, r2+1): for j in range(c1, c2+1): if not color in matrix[i][j]: matrix[i][j].append(color) # 원하는 색이 ..