AndroidTeacher

https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 문제 설명 격자 맵과 한 지점이 주어졌을 때, 시작점 부터 그 지점을 거쳐 종료점까지 만들 수 있는 경로의 개수를 구하는 문제이다. 풀이 과정 경우의 수와 DP를 활용하는 문제이다. 초등학교 때 길 찾기 경우의 수를 배울 때 이러한 방법을 사용했을 것이다. 1 1 1 1 1 2 3 4 1 3 6 10 위 표처럼 가장 첫 칸과 첫 행을 1로 채우고 다음칸부터 왼..

문제 설명 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사..

https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 문제 설명 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 설명 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 풀이 과정 1부터 n까지의 수 중, 중복없이 m개의 수를 나열하는 문제이다. 즉, 1부터 n까지의 수 중 m개의 수를 나열하는 중복을 허락하지 않는 순열이다. 단, 수열은 오름차순으로 정..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 설명 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 풀이 과정 1부터 n까지의 수 중, 중복없이 m개의 수를 나열하는 문제이다. 즉, 1부터 n까지의 수 중 m개의 수를 나열하는 중복을 허락하지 않는 순열이다. 예를 들어, n = 4, m = 2일 경우 1부터 4까지의 수..

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..