AndroidTeacher

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 설명 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 풀이 과정 먼저, 좌표 압축..

문제 설명 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌..

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 설명 계수정렬(Counting Sort)을 이용해 정렬을 하는 문제이다. 풀이 과정 내장된 sort함수를 이용하면 메모리초과 오류가 난다. 계수 정렬을 이용해 정렬을 해야한다. 다만, 배열이 1칸이라도 더 많다거나 배열 두개를 사용하는 등 사소한 부분에서 메모리초과 오류가 발생하니 이부분을 유의해야 한다. 그리고 PyPy3로 돌렸을 때 메모리초과 오류가 난다면 Python3로 재채점을 해보길 권장한다. impo..

https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 문제 설명 666, 1666, 2666, 3666 ... 으로 수 들이 나열될 때 N번째 수는 어떤 수인지를 맞추는 문제이다. 풀이 과정 문제에서 주의해야 할 점은 6이 3번 나타나기 때문에 7번째 수는 6666이 아니라 6660이 되어야 한다. 그리고 작은 수들부터 나열을 하기 때문에 8번째 수는 7666이 아니라 6661이 될 것이다. 이러한 조건들을 위해 조건문을 나열하기에는 너무 까다롭기..

https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 문제 설명 두 좌표 (x1, y1)와 (x2, y2)가 주어지고, 목표점과의 거리 r1, r2가 주어질 때 목표점이 존재할 수 있는 좌표의 수를 구하는 문제이다. 풀이 과정 이 문제는 고등학교 교과과정에서 배웠던 원의 방정식 중 두 원의 교점을 활용하는 문제이다. 먼저, 원이라는 것은 하나의 정점으로부터 같은 거리를 가지는 점들의 집합이므로 정점(x1, y1)로 부터 거리 r1을 가진 점들은 원으로 존재할 것이고 정점(x2, y2)로 부터 거리 r2..

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 설명 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. ..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제 설명 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 설명 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 풀이 과정 소수란, 1과 자기자신을 제외한 나머지 수로 나누어 떨어지지 않는 수이다. 그래서 소수를 판별하는 가장 간단한 방법은 2부터 자기자신 - 1 까지 for문을 돌면서 나누어 떨어지는지 확인하는 것이다. 하지만, 모두 확인할 필요 없이 제곱근까지만 확인을 하면 된다. 그 이유는 약수들의 곱이 서로 대칭을 이루기 때문인데 예를 들어, 16이라는 수가 있..

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 설명 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 풀이 과정 소수란, 1과 자기자신을 제외한 나머지 수로 나누어 떨어지지 않는 수이다. 그래서 소수를 판별하는 가장 간단한 방법은 2부터 자기자신 - 1 까지 for문을 돌면서 나누어 떨어지는지 확인하는 것이다. 하지만, 모두 확인할 필요 없이 제곱근까지만 확인을 하면 된다. 그 이유는 약수들의 곱이 서로 대칭을 이루기 때문인데 예를 들어, 16이라는 수가 있을 때 16의 약수..

문제 설명 https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 위 링크에서 주어진 설명처럼, 시작점과 끝점이 주어질 때 공간이동 장치의 작동횟수를 구하는 문제이다. 풀이 과정 먼저, 이 문제는 규칙을 찾아 해결하는 문제이다. 규칙을 찾는 과정이 굉장히 까다로웠는데, 규칙을 찾기 위해 직접 거리 1부터 직접 테이블을 작성해보았다. 먼저 거리가 제곱수일 때를 보면 (노란 배경색), 이동 단계에 새로운 숫자가..