RUBY

출처:: www.acmicpc.net/problem/2529 분류:: dfs 1. 문제 이해 및 해결과정 2. 풀이방법 1. python #부등호 #https://www.acmicpc.net/problem/2529 import sys sys.stdin = open("input.txt","r") n=int(input()) op=input().split() #부등호 num=[False]*10 maxv,minv="","" #최대 최소 def check(i,j,op): if op=='': return i>j return True #같은 경우, 있을 수 없음 def dfs(cnt,s): global maxv,minv if cnt==n+1: if not len(minv): #최솟값이 없으면, 순서대로 하므로 최솟값..

출처:: www.acmicpc.net/problem/1644 분류:: 에라토스테네스의 체, 투포인터 1. 문제 이해 및 해결과정 - n이 400만으로 일반적인 소수찾는 알고리즘으로 탐색이 안된다 -> 에라토스테네스의 체 이용해야한다. - 1. 에라토스테네스의 체로 가능한 소수를 찾고 - 2. 투포인터로 연속된 소수의 합 가능한 경우를 센다 cf) 에라토스테네스의 체 hiruby.tistory.com/463 투포인터 hiruby.tistory.com/416 2. 풀이방법 #소수의 연속합 #https://www.acmicpc.net/problem/1644 import sys import math sys.stdin = open("input.txt","r") n=int(input()) arr=[True for ..

이진탐색 - 반으로 쪼개면서 탐색하기 : 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 과정 - 시간복잡도 O(logn) - 처리해야할 데이터의 개수나 값이 1000만 이상이면 이진탐색 떠올리자 - 구현 #10개의 수입력했을 때, 7이 몇번째 있는지 찾기 10 7 1 3 5 7 9 11 13 15 17 19 1) 재귀함수 #재귀함수로 구현한 이진 탐색 소스코드 # import sys sys.stdin = open("input.txt","r") def binary_search(arr,target,start,end): if start>end: return None mid=(start+end)//2 #목표값을 찾은 경우 if arr[mid] == target: retu..

출처:: https://www.acmicpc.net/problem/1654 분류:: 이분탐색, 파라메트릭서치 1. 문제 이해 및 해결과정 2. 풀이방법 1. python #랜선자르기 #https://www.acmicpc.net/problem/1654 import sys sys.stdin = open("input.txt","r") k,n=map(int,input().split()) lan=[] for i in range(k): lan.append(int(input())) start,end=1,max(lan) while start

출처:: www.acmicpc.net/problem/2623 분류:: 위상정렬 1. 문제 이해 및 해결과정 2. 풀이방법 1. python #음악프로그램 #https://www.acmicpc.net/problem/2623 import sys from collections import deque sys.stdin = open("input.txt","r") n,m=map(int,input().split()) #노드 수, 정렬 수 graph=[[] for _ in range(n+1)] indegree=[0]*(n+1) for i in range(m): #그래프 그리기 data=list(map(int,input().split())) sub=data[0] #보조pd가 담당한 가수의 수 for j in range(..

출처:: www.acmicpc.net/problem/2003 분류:: 투포인터 1. 문제 이해 및 해결과정 2. 풀이방법 1. python #수들의 합 2 #https://www.acmicpc.net/problem/2003 import sys sys.stdin = open("input.txt","r") n,m=map(int,input().split()) arr=list(map(int,input().split())) s,e=0,0 cnt=0 sum=0 for s in range(n): while sum

출처:: programmers.co.kr/learn/courses/30/lessons/12921?language=python3 분류:: 에라토스테네스의 체 1. 문제 이해 및 해결과정 2. 풀이방법 1.에라토스테네스의 체 import math def solution(n): answer = 0 arr=[ True for _ in range(n+1)] for i in range(2,int(math.sqrt(n))+1): if arr[i]: #소수인 경우 j=2 while i*j

출처:: https://www.acmicpc.net/problem/2805 1. 문제 이해 및 해결과정 - 나무의 최대 높이는 10억 , 이진탐색으로 탐색하면 log2(10^9) 약 31번 - 나무의 수가 최대 백만이므로 나무의 높이를 바꾸면서, 바꿀때마다 모든 나무를 체크 하는 경우 31*백만 = 3000만번의 연산이 필요하다 2. 풀이방법 1. 이분탐색 [python] #나무 자르기 #https://www.acmicpc.net/problem/2805 import sys sys.stdin = open("input.txt","r") n,m=map(int,input().split()) tree=list(map(int,input().split())) lt=0 rt=max(tree) res=0 def coun..