일지 & 개발

문제 요약 알고리즘 분류: 수학, 배열 난이도: Bronze2 문제내용: N 명 학생 점수중에서 가장 큰 값과 작은 값의 차이를 구해 사이트: https://www.acmicpc.net/problem/15969 15969번: 행복 모든 서브태스크에서 2 ≤ N ≤ 1,000이고 입력되는 학생들의 점수는 0 이상 1,000 이하의 정수이다. www.acmicpc.net 문제풀이 이번 문제에는 가장 큰 값과 작은 값을 구하는 문제라서 배열/리스트에서 max(), min() 함수를 알면 푸는데는 문제가 없다고 생각한다. Code Python import sys input = sys.stdin.readline N = int(input()) grade = list(map(int, input().split())) ..

문제 요약 알고리즘 분류: 수학, 분할정복, 재귀 호출 난이도: Gold2 문제내용: 피나치수 결과를 1,000,000,007로 나눈 나머지를 구해라 사이트 : https://www.acmicpc.net/problem/11444 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제풀이 이번 문제는 좀 수학적인 지식이 있어야 풀수가 있다. 그 이유는 데이터의 크기가 조단위이고 나머지 1억인점을 생각하면 일반적인 모듈러 연산을 이용해도 시간 초과가 나올것이다. 파이썬의 초당 처리속도는 2000만정도라고 생각하면 방법이 O(logN)방법 ..

문제 요약 알고리즘 분류: 수학, 조합, 재귀호출 난이도: Gold2 문제내용: 조합한 결과를 1,000,000,007로 나눈 나머지를 출력해라 사이트 : https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제풀이 이번 문제 내용은 간단한데 데이터의 범위가 4,000,000 이라서 O(N)으로 풀어도 데이터 저장할수 있는 숫자와 배열의 크기가 넘어 갈뿐만 아니라 메모리도 초과 되어서 다른 방법으로 접근 해야 한다. 문제 접근 방법 정상적인 DP 방법으로도 안되서 나머지..

문제 요약 알고리즘 분류: 구현 난이도: Silver5 문제내용: 두개의 행렬을 주어지면 행렬 곱셈 한 결과를 구해라. 사이트: https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 문제풀이 이번 문제는 고등학교 수학에 나오는 행렬 연산 문제이다. 행렬 곱셈 공식만 알면 문제 푸는데는 어려움이 없으니까 바로 밑에 코드보고 공부하면된다. 코드 보기전에 행렬 곱셈에 대한 원리를 알고 보면 될거 같다. Code Python N, M = ..

문제 요약 알고리즘 분류: 조합, 동적계획법 난이도: Silver3 문제내용: 이항 계수( N K)를 10007로 나눈 나머지를 결과를 출력해라 사이트 주소: https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제풀이 2가지 푸는 방법이 있다. 하나는 조합공식을 사용해서 푸는 방법과 동적계획법으로 푸는 방식이다. 조합 공식 사용 방법 위의 조합 공식으로 사용 하면 된다. 파이썬에서는 factorial 함수를 제공한다. DP로 접근하는 방법 위 사진은 파스칼 삼각형이다. 파스칼 삼각형의 공식은 아래와 같이 정의 할수 ..

문제 요약 알고리즘 분류: 정수론, 수학 난이도: Bronz1 문제내용: 첫째 줄 N과 N의 개수 만큼 약수가 있다. 사이트 주소: https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net 문제 풀이 최소 공배수로 접근 하면 안된다. → why? 최소 공배수는 밑의 수를 다 포함한 약수인데 2, 3, 5의 최소 공배수가 30인데. 30의 약수로는 2, 3, 5, 10, 15가 와야 하기 때문에 말이 안된다. 배열 또는 리스트로 선언한 다음 배열안의 최소 최대 곱하면 된다. CODE JAVA im..

문제 요약 알고리즘 분류: 기하학, 수학, 구현 문제난이도: Silver 3 문제 내용 1m × 1m 면적당 참외 K개 있음 동서남북 6번 이동한다 각 입력마다 동서남북 이동방향과 길이를 준다. 참외밭의 참외 개수를 구한다. 사이트 주소: https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 문제 풀이 각 가장진 가로, 세로 길이, 인덱스 저장할 변수를 선언한다. 가장긴 가로,세로 인덱스와 길이를 구한다. 가장긴 가로, 세로의 양쪽 인덱스 구한다 ..