sweetdev

정의 phi(N) - N보다 작고 N과 서로소들인 수의 갯수. ex) phi(10) = 10보다 작고 10과 서로소인 수 = {1, 3, 7, 9} * pi(N)과는 다름. pi(N)은 N보다 작은 소수의 갯수!! * 곱셈역을 배웠다면...Zn*의 크기와 phi(N)은 같다 피함수의 성질 1. phi(1) = 0 2. phi(P) = p-1 3. m,n이 서로소이면 phi(m * n) = phi(m) * phi(n) 4. phi(p^e) = p^e - p^(e-1) (p가 소수이면, e가 양의 정수이면) m,n이 서로소이면 phi(m * n) = phi(m) * phi(n) 증명하기 원래 성질은 서로소이면 다 되는데 여기서 증명은 간단하게 m, n 모두 소수일 때만 한다. phi(m * n)은 m*n보다..

어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 된다. 시간복잡도: O(N^1/2) 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다. 배열을 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.) 2부터 시작하여 남아있는 수를 모두 출력한다. [참고] velog.io/@max9106/Algorithm-에라토스테네스의-체 [코드] import sys import math import itertools N_input = int(sys.stdin.readline()) line = li..

input: 두 문자열 output: 겹치는 최장 길이 문자열 LCS: Longest Common Subsequence 백준에서 LCS문제를 풀게 되었는데 이것 자체가 하나의 알고리즘이라고 해서 정리하게 되었다. LCS는 DP기반의 알고리즘이고, Subsequence이므로 꼭 연속은 아니어도 된다. 부분부분 잘라서 존재하기만 해도 ㄱㅊ 백준에서 들은 예는 다음과 같다. ACAYKP CAPCAK 에서 LCS는 ACAK이다. 이렇게 세팅해놓고 시작한다. 글자가 같을때는 그 전줄전의값 + 1 해서 넣어주면 되는데, 다를때는 윗줄과 옆칸을 비교해서 더 큰값을 넣어준다. 코드 !! import sys str1 = sys.stdin.readline().rstrip('\n') str2 = sys.stdin.readl..

# 9663번 N-Queen import sys N = int(sys.stdin.readline()) data = [[0]*N for _ in range(N)] count = 0 check_col = [0]*N check_diag = [0]*(2*N-1) check_diag2 = [0]*(2*N-1) def check(row, col): if check_col[col] == 1: return False elif check_diag[row+col]==1: return False elif check_diag2[row-col + (N-1)] == 1: return False else: return True def dfs(row): global count if row == N: count += 1 return ..

모든 점을 다 방문해보아야 하는 DFS와 달리, BFS로 찾은 경로는 도착점이 나오는 즉시 최단거리임을 알 수 있어서 바로 종료할 수 있는 장점이 있다. 따라서 최단거리를 구하는 문제에서는 BFS를 쓰는것이 좋다. 코드를 어떻게 짤까 복잡하게 생각했었는데 bfs()를 콜 하고 제일 먼저 도착점과 같아질 때 끝인것이었다..! 백준 2178번을 풀이하면서 작성한 코드는 다음과 같다. # 2178번 미로 탐색 # bfs로 탐색해서 제일 먼저 끝점이랑 같아질 때 리턴. import sys N, M = map(int, sys.stdin.readline().split()) data = [] for _ in range(N): data.append([int(d) for d in str(sys.stdin.readline..

# 1012번 유기농배추 import sys def bfs(row, col): queue.insert(0, [row, col]) while queue: current = queue.pop() newRow = current[0] newCol = current[1] # 이웃 찾기 for a in [-1, 1]: if 0

in Pypy # 2667번 단지번호붙이기 # BFS로 풀기 import sys N = int(sys.stdin.readline()) data = [] for _ in range(N): data.append([int(d) for d in str(sys.stdin.readline().rstrip())]) # print(data) queue = [] groupList = [] def bfs(row, col): queue.insert(0, [row, col]) while queue: current = queue.pop() newRow = current[0] newCol = current[1] # 이웃 찾기 for a in [-1, 1]: if 0

# 2606 바이러스 import sys nodes = int(sys.stdin.readline()) pairs = int(sys.stdin.readline()) node_set = set() adjacencyList = [[] for _ in range(nodes+1)] visitedList = [] for _ in range(pairs): a, b = map(int, sys.stdin.readline().split()) if a not in node_set: node_set.add(a) if b not in node_set: node_set.add(b) if a not in adjacencyList[b]: adjacencyList[b].append(a) if b not in adjacencyList[..

# 2875번 대회 or 인턴 import sys N, M, K = map(int, sys.stdin.readline().split()) # K를 구하는 과정 while K > 0: if N // 2 > M: N = N - 2 K = K - 2 elif N // 2 0: print(min(N // 2, M)) else: print(0)

# 11047번 동전0 import sys N, K = map(int, sys.stdin.readline().split()) coins = [] count = 0 for i in range(N): coins.append(int(sys.stdin.readline())) coins.reverse() while K != 0: for coin in coins: if coin

# 1780 종이의 갯수 import sys N = int(sys.stdin.readline()) data = [] for _ in range(N): data.append(list(map(int, sys.stdin.readline().split()))) # print(data) ans = {"-1": 0, "0": 0, "1": 0} def addOrDivide(row, col, N): value = data[row][col] for i in range(N): for j in range(N): if value != data[row + i][col + j]: # 하나라도 다른값이 나왔으면 쪼개준다 addOrDivide(row, col, N // 3) addOrDivide(row, col + N // 3, ..

# 11728 배열 합치기 import sys N, M = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) B = list(map(int, sys.stdin.readline().split())) appended = A + B appended.sort() print(*appended, sep= ' ') 이렇게 해서 풀긴 했는데 A, B는 이미 sort가 되어 있는 array라서 더 나은 방법이 있을 것 같았다. A, B 하나씩 가져와서 크기 비교하고 append해주면 될듯??

# 10816 숫자카드 2 import sys N = int(sys.stdin.readline()) cards = map(int, sys.stdin.readline().split()) dic = {} M = int(sys.stdin.readline()) data = map(int, sys.stdin.readline().split()) for i in cards: try: dic[i] += 1 except: dic[i] = 1 for j in data: try: print(dic[j], end = " ") except: print(0, end= " ")

# 10825 국영수 import sys N = int(sys.stdin.readline()) data = [] for i in range(N): name, 국어, 영어, 수학 = map(str, sys.stdin.readline().split()) 국어 = int(국어) 영어 = int(영어) 수학 = int(수학) data.append((name, 국어, 영어, 수학)) a = sorted(data, key=lambda x: (-x[1], x[2], -x[3], x[0])) for j in a: print(j[0])

import sys N, M = map(int, sys.stdin.readline().split()) # N: 나무의 수 # M: 집에 가져가려고 하는 나무 길이 data = list(map(int, sys.stdin.readline().split())) left = 1 right = max(data) while left = mid: count += i - mid else: count += 0 if count >= M: left = mid + 1 else: right = mid - 1 print(right) Binary Search로 풀면 된다.

알고리즘 시간에 다 배운건데 하나도 못짜겠어서 인터넷 보고 공부했다... 참고한 사이트 : velog.io/@i-zro/파이썬Python-코테-대비-DFSBFS-백준-1260번-DFS와-BFS 코드도 여기서가져옴!@!!!!! N,M,V=map(int,input().split()) matrix=[[0]*(N+1) for i in range(N+1)] for i in range(M): a,b = map(int,input().split()) matrix[a][b]=matrix[b][a]=1 visit_list=[0]*(N+1) def dfs(V): visit_list[V]=1 #방문한 점 1로 표시 print(V, end=' ') for i in range(1,N+1): if(visit_list[i]==0 a..

www.acmicpc.net/blog/view/70

# 11650 좌표 정렬하기 import sys N = int(sys.stdin.readline()) arr = [] for i in range(N): m = sys.stdin.readline().split() m.reverse() arr.append(list(map(int, m))) arr.sort() for i in range(N): arr[i].reverse() print(f"{arr[i][0]} {arr[i][1]}")

timeout 당연히 날 줄 알았는데 안나네 ㄱㅇㄷ sort()최고!! # 11650 좌표 정렬하기 import sys N = int(sys.stdin.readline()) arr = [] for i in range(N): arr.append(list(map(int, sys.stdin.readline().split()))) arr.sort() for i in range(N): print(f"{arr[i][0]} {arr[i][1]}")

# 11722 가장 긴 감소하는 부분수열 import sys N = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) nums = [1 for _ in range(N)] for i in range(N): v_max = 0 for j in range(0, i): if arr[j] > arr[i] and nums[j] > v_max: v_max = nums[j] nums[i] = v_max + 1 print(max(nums))

DP...점화식..고딩때 수학할때도 점화식이 너무 어려웠었다 DP의 핵심은 1. 점화식 세우기 2. 값이 아니라 여기까지 했을때 max(경우의 수)를 저장해두기 3. 그리고 그걸 갱신하기 인것 같다. 나는 맨날 값으로 접근해서 되게 어려워했는데 그 전의 max 그리고 그 다음 식의 점화식만 생각하면 훨씬 쉽다. 수학에서의 점화식은 어려운 계산을 잘 다루지 않는데 여기서는 복잡한 계산은 다 컴퓨터가 해주니까 식도 더 복잡해...계산도 더럽다 n=3넘어가면 계산도 못해본다 코드나 잘 짜야지ㅠ

import sys n = int(sys.stdin.readline()) arr = [0 for _ in range(n+1)] arr[1] = 1 if n > 1: arr[2] = 3 if n > 2: arr[3] = 5 if n > 3: for i in range(4, n+1): arr[i] = arr[i-1] + 2*arr[i-2] print(arr[n] % 10007)

# 11726 2xn 타일링 import sys # import time # start = time.time() n = int(sys.stdin.readline()) arr = [0 for i in range(n + 1)] arr[1] = 1 if n > 1: arr[2] = 2 if n > 2: arr[3] = 3 if n > 3: for j in range(4, n + 1): arr[j] = arr[j - 1] + arr[j - 2] print(arr[n] % 10007) # print("time :", time.time() - start)

# 9095 1, 2, 3 더하기 import sys # import time T = int(sys.stdin.readline()) # start = time.time() for t in range(T): n = int(sys.stdin.readline()) arr = [0 for i in range(n + 1)] arr[1] = 1 if n>1: arr[2] = 2 if n>2: arr[3] = 4 if n > 3: for j in range(4, n + 1): arr[j] = arr[j - 1] + arr[j - 2] + arr[j - 3] print(arr[n]) # print("time :", time.time() - start)

# 11057 오르막수 import sys N = int(sys.stdin.readline()) arr = [[0 for _ in range(N+1)] for _ in range(11)] for i in range(1, 11): arr[i][1] = 1 for i in range(1, N+1): arr[0][i] = 1 for column in range(2, N+1): for row in range(1, 10): arr[row][column] = arr[row-1][column] + arr[row][column-1] sumV = 0 for row in range(0, 10): sumV += arr[row][N] print(sumV % 10007)

# 9465 import sys T = int(sys.stdin.readline()) for _ in range(T): n = int(sys.stdin.readline()) top = list(map(int, sys.stdin.readline().split())) top.insert(0, 0) bottom = list(map(int, sys.stdin.readline().split())) bottom.insert(0, 0) arr = [top, bottom] for column in range(2, n + 1): for row in range(2): if row == 0: arr[row][column] += max(arr[row + 1][column - 1], arr[row + 1][column - 2]..

# ACM 호텔 import math T = int(input()) for i in range(T): H, W, N = map(int, input().split()) if N % H == 0: floor = H else: floor = N % H num = int(((N-1) // H) + 1) print(f"{floor*100 + num}") # print(f"{floor}0{num}") 주석처럼 표기해서 여러번 틀렸는데 XYY, XXYY꼴이라고 했으니까 틀린게 맞다...

이게 뭐라고..

진짜 쓸데없는데서 시간 날렸는데 소수점 한자리 표시하는법을 몰라서 한참 찾았다 😔 T = int(input()) for t in range(T): N = int(input()) get_sum = 0.0 C_sum = 0 for n in range(N): C, G = map(float, input().split()) get_sum += C * G C_sum += C GPA = get_sum / C_sum print("%s %.1f" % (int(C_sum), GPA))

print("%s %.1f" % (int(C_sum), GPA)) %.1f-> 소숫점 한자리까지 표시