생각 생각

https://acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net import sys input=sys.stdin.readline N=int(input()) lis_p,lis_z,lis_n=[],[],[] # 양수, 0, 음수로 나누기 ans=0 for _ in range(N): t=int(input()) if t>0: lis_p.append(t) elif t==0: lis_z.append(t) else: lis_n.append(t) lis_p.sort() lis_n..

https://acmicpc.net/problem/3425 3425번: 고스택 각각의 입력값에 대해서, 해당하는 프로그램을 수행한 뒤, 출력값을 출력하면 된다. 출력값이란 스택에 저장되어 있는 숫자이다. 만약, 프로그램 에러가 발생하거나, 모든 수행이 종료됐을 때 www.acmicpc.net 그냥 꼼꼼해야 하는 구현. 스택으로 연습하기에는 그냥저냥… import sys input=sys.stdin.readline commands=[] def program(c): for command in c: try: if command=="POP": stack.pop() elif command=="INV": stack[-1]=-stack[-1] elif command == "DUP": stack.append(stack..

https://acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 백트래킹과 브루트포스인 건 바로 알아봤는데, 어디서부터 탐색을 이어가야 할 지를 헷갈렸다. 단순하게 색종이를 붙이고 x축으로 이동하면 될 것인데 엄한 곳에서 헤멨다. # 색종이 붙이기 # 백트래킹, 브루트포스. import sys input=sys.stdin.readline paper=[list(map(int, input().split())) for _ in range(10)] answer=26..

https://acmicpc.net/problem/1112 1112번: 진법 변환 우리는 10진수를 사용한다. 10진수는 0부터 9까지 숫자를 사용한다. 12345가 10진수라면, 이 값은 1×104 + 2×103 + 3×102 + 4×101 + 5×100이다. 자 이제 -10진법을 보자. 이 수도 0부터 9까지 숫자를 사용하고, www.acmicpc.net 수학 문제라 막상 구현은 크게 어렵지 않았다. #진법 변환 x,b=map(int,input().split()) neg=False if b >=2 and x

https://acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 유니온 파인드를 통해 분리 집합을 찾는 문제. 항상 MST를 위해 유니온 파인드를 쓰다가 막상 원래 의도대로 분리 집합을 찾으려니 헷갈렸다. 답을 참고하지 않고 직접 구현했는데, 막상 풀고 보니 비효율적인 면이 있었다 # 친구 네트워크 # 기존과 달리 groups라는 분리 집합을 두고 문제를 풀 것이다. import sys input=sys.stdin.readline def find(x): #..

https://acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 날먹문제. 이게 왜 골 1…? a,b=map(int,input().split()) nums=[False]*(b-a+1) ans=b-a+1 for i in range(2,int(b**0.5)+1): for j in range(((a-1)//i**2+1)*i**2, b+1,i**2): if not nums[j-a]: nums[j-a] = True ans-=1 print(ans)

https://acmicpc.net/problem/14289 14289번: 본대 산책 3 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 본대 산책 2와 동일하지만, 인접 행렬을 직접 만들면 된다. import sys input = sys.stdin.readline MOD = 1000000007 n,m=map(int,input().split()) def multiply(matrix1, matrix2): return [[sum(matrix1[i][k]*matrix2[k][j] % MOD for k in range(n)) % MOD for j in range(n)] for i in range(n)] dp = [[0]*n for _ in range(n)] f..

https://acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 진짜 이상한 사람들 많다. 이딴 생각은 왜 어떻게 하는거지 도대체? 페르마의 소정리에 대한 이야기는 많이 들었었고, 문제도 풀어본 적이 있었다. https://www.acmicpc.net/problem/13172 페르마의 소정리는 다음과 같다. ”p가 소수이면, 모든 정수 a에 대해 ap≡a(mod p)이다.” 혹은, ”p가 소수이고 , a가 p의 배수가 아니면 a(p-1)≡1 (mod p)이다.” 암호화에 특히 유용하게 이용하는 굉장히 강력한 ..