kwan's note

itertools를 사용하지 않고 순열과 조합을 작성해 보았습니다. 다만 여기선 input을 튜플로 받아 중복을 해소하였습니다. 함수안에서 중복을 해소하는 방법도 있겠지만 최대한 간단하게 해결해보려고 했습니다. def permutation(arr, r): used = [0]*len(arr) per2return=[] def generate(item, used): if len(item) == r: per2return.append(item.copy()) return # 3. for i in range(len(arr)): if not used[i]: item.append(arr[i]) used[i] = 1 generate(item, used) used[i] = 0 item.pop() generate([], us..

www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 간단한 구현문제이다. 시간이 좀 걸리긴했는데 문제만 잘 읽고 따라푼다면 충분히 풀만한 문제인듯하다. 고려할것은 1.뱀의 머리방향을 어떻게 돌릴지 2.break 타이밍 정도가 될것같다. 뱀의 머리방향을 동, 북, 서, 남 순서로 놓고 왼쪽을 보려면 +1 오른쪽을 보려면 -1하였다. 그리고 뱀은 자라는게 먼저이므로 자라자 마자 break를 해야한다. N = int(input()) K = int(input()) appl =..

www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 단계: 실버2 cpp 을 이용해 소수의 갯수를 파악하는 문제를 풀어보고자 했습니다. 처음에는 2부터 늘려가며 나누어지는지를 판단하는 방식으로 계산하였는데 시간초과로 인해 이러한 sequential한 방식이 아닌 다른 방식으로 해결하고자 했습니다. #include using namespace std; int main() { int n = NULL; while (true) { cin >> n; if (n =..

문제번호 2217 난이도 실버4 www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 로프를 여러개 쓰면 가장 장력이 낮은 줄로 하향평준화된다. 따라서 모든 로프를 쓸 때 즉 N개를 쓰면 가장 낮은 로프의 장력*N이되고 N-1개의 로프를 쓴다고 하면 두번째로 낮은 로프의 장력*N-1이 된다. 이중 max값을 구하는것이므로 i=0부터 N-1까지 모든 로프에 대해 작은것부터 max값을 구하면 된다. import sys N = int(sys.stdin.read..

문제번호: 11758 난이도 : 골드5 시계, 반시계를 판단하는 문제이다. 벡터에 대한 기본개념이 있으면 코딩을 잘 못해도 풀 수 있는문제이다. 두 벡터의 외적을 통해 양수, 음수, 0을 판별하여 계산하였다. 알고리즘 수업의 과제였던 convex hull에서 유사한 방식을 사용한 경험이 있어 비교적 쉽게 풀었다. www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 각 좌표를 받은뒤 outer p..

1010번 실버5 www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 조합문제이다. 그냥 C(M,N)로 풀면된다. 풀이1(comb 사용) import math T= int(input()) for i in range(T): N,M=map(int,input().split()) print(math.comb(M,N)) 풀이2(comb사용 x) import math T= int(input()) for i in range(T): N,M=map(int,input().spli..

2981번 실버5 www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 처음에는 for문을 최소화해서 for j in range(2,min(num[0]*2,num[1])-1): for i in range(N): 의 이중 for문으로 풀었는데 log n정도의 시간복잡도임에도 시간초과로 풀리지가 않아 수학적으로 접근했다. A=P1*Q+R B=P2*Q+R C=P3*Q+R 등의 형태로 나타나는 수를 구하는데 R을 없애기 위해서 abs(A-B), abs(B-C)등의 표현을 사용했고 이 식..

2609번 실버5 www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 최대공약수 최소공배수를 구하는 간단한 문제다. 유클리드호제법으로 gcd를 구하고 이를이용해 lcm을 구했다. 코드는 시간이 남을것같아서 시간에 관계없이 짧고 간결하게 작성해보았다. num1 , num2= map(int,input().split()) def gcd(a,b): return b if a%b==0 else gcd(b,a%b) print(gcd(num1,num2)) print(num1*num2//gcd(num1,num2))