일지 & 개발

문제 요약 알고리즘 분류: 수학 난이도: Bronze5 문제내용: N M 길이 준다 A , B 곱한 결과를 출력해라 사이트: https://www.acmicpc.net/problem/22193 22193번: Multiply Write a program that computes a product of two non-negative integers A and B. The integers are represented in decimal notation and have N and M digits, respectively. www.acmicpc.net Code Python input() print(int(input()) * int(input())) Java 정수의 길이의 제한이 없어서 BigInteger로 선언해..

문제 요약 알고리즘 분류: 그리디 난이도: Silver3 문제내용: 실제 성적 등수와 학생 예상 등수 최소 차이를 구해라 사이트: https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 문제풀이 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 밑에 사이트에 참조하면된다. https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy) 이론 그리디 알고리즘은 탐욕 ..

문제 요약 알고리즘 분류: 분할정복, 스택, 세그먼트 트리 난이도: Platinum5 문제내용: 각 케이스마다 위 그림 처럼 히스토그램 넓이중 가장 큰것을 구해라. 사이트 : https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제풀이 이번에는 문제 유형은 분할 정복, 스택, 세그먼트 트리 3가지 방법으로 풀수 있다. 간단하게 완전탐색으로도 답은 나오지만 문제는 주는 데이터의 수가 10만이다..

문제 요약 알고리즘 분류: 그리디 난이도: Silver5 문제내용: 0과 1로 이루어진 문자열 S가 있다. 뒤집다는 의미는 0과 1을 바꾸는것이다. 뒤집을 수 경우는 모두다 뒤집거나 a ~ b 길이 만큼 변경이 가능하다. 모든 숫자가 같을라면 몇번 뒤집어야 하는가 사이트: 거스름돈 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 문제풀이 이번 문제는 최대길이가 100만이고 제한시간 1초라서 O(n)으로 풀어야 한다. 브루드포스 알고리즘으로 풀기에는 무리가 있어서 그리디알고리즘으로 적용해야..

문제 요약 알고리즘 분류: 수학, 분할정복, 재귀 호출 난이도: 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 문제내용: 행렬의 N 제곱을 구한뒤 각 원소마다 1,000을 나눈 나머지를 구해라. 사이트 : https://www.acmicpc.net/problem/11401 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제풀이 이번 문제 내용는 2가지만 알면 쉽게 풀수 있다고 생각한다. 첫번째는 행렬 제곱을 처리 하는 방법이다. 행렬 제곱은 행렬 곱셈만 구현 하면 되기 때문에 밑에 사이트에 문제 풀어보거나 복습하면 풀수가 있다. https://jih3508.t..

문제 요약 알고리즘 분류: 그리디 난이도: Bronze2 문제내용: 잔돈은 500, 100, 50, 5, 1 있다. 내가 가진돈은 1000엔 지폐 한 장을 내면 거스름돈 받아야 최소 개수를 구해라. 사이트: https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 문제풀이 이번 문제는 그리디 알고리즘 중 그리디 알고리즘이다. 그리디 알고리즘의 관련 내용은 아래 사이트에 확인 해보면 되고 예제중에 거스름돈이 있으니 그것 확인 해보면 ..

문제 요약 알고리즘 분류: 구현 난이도: 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 = ..