IT_공부하자

https://www.acmicpc.net/problem/13909 13909번: 창문 닫기 서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째 www.acmicpc.net - 접근 : 1 인 경우: 모든 창문의 열림 res= 1 2 인 경우: 2 번째 창문이 닫힘 res= 1 3 인 경우: 3 번째 창문이 닫힘 res= 1 4 인 경우: 4 번째 창문이 열림 ( 2가 창문을 닫기 때문 ) res= 2 5 인 경우: 5 번째 창문이 닫힘 res= 1 n 인 경우: 1 부터 n 까지 중 특정 수의 제곱이 되는 경우에만 1 그러므로 res = n^(1/2)의 정..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 접근 : - 정수론을 이용하여 특정 범위 내 소수의 갯수를 구한다 - 누적합을 이용하여 시간을 줄인다 ( 누적합을 이용하지 않는 경우 : 메모리 35688 KB , 소요 시간 4756 ms / 사용한 경우 : 메모리 33124 KB , 소요 시간 540 ms ) * 사전 범위를 파악하여 가능하면 누적 합을 이용하는 것을 판단해보는 것이 중요 코드 구현 :

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 접근 : - 에라토스테네스의 체 활용 코드 구현 :

https://www.acmicpc.net/problem/4134 4134번: 다음 소수 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. www.acmicpc.net - 접근 : 정수론에서 " n 의 제곱근 이하의 수에서 1을 제외한 약수가 없으면 소수 "를 이용한다. - 코드 구현 :

https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net - 접근 : 거리의 최소 공배수를 이용하여 추가할 나무의 갯수를 계산 - 코드 구현 :

https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net - 접근 : 최대 공약수를 사용 - 코드 구현 :

https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net - 접근 : 유클리드 호제법을 사용한다 - 코드 구현 :

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 접근 : - 기본적인 DFS 와 BFS 관련 문제 - DFS - BFS - 코드 구현 : from collections import deque import sys def answer(): N, M, V = map(int, sys.stdin.readline().rstrip().split(' ')) graph = [[] for _ in range(N+1)] d_v..