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)}')

이분탐색입니다. import sys input = sys.stdin.readline def isPossible(length): cnt = 0 for pa in pas: cnt += pa//length if cnt >= C: return True return False S, C = map(int, input().split()) pas = [int(input()) for _ in range(S)] start = 1 end = max(pas) answer = (start+end)//2 while start

고지식한 매칭 text = 'ABABCA' for i in range(len(text)-len(target)): for j in range(len(target)): if text[i+j] == target[j]: j+=1 else: break print('Identified') break KMP 알고리즘.(시작위치 후보를 잡아놓자) 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행. 패턴을 전처리하여 배열 next[M]을 구해서 잘못된 시작을 최소화함. next[M]: 불일치가 발생했을 경우 이동할 다음 위치 패턴내에서 반복하는 구간이 있을것이라는 전제.. 하지만 없다면 무의미. 하지만 패턴이 길다는 전..

그래프 그리고 DFS~ import sys input = sys.stdin.readline def DFS(cur_node, target): if cur_node==target: return True for next_node in graph[cur_node]: if not visited[next_node]: visited[next_node] = True if DFS(next_node, target): return True n = int(input()) graph = {i:[] for i in range(26)} level = {i:0 for i in range(26)} for _ in range(n): first, arrow, end = input().split() first_num = ord(first)..

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 # 글자가 들어..