일지 & 개발

문제 요약 알고리즘 분류: 이분탐색 난이도: Gold2 문제내용: 크기 N×N 배열이고 시작 인덱스는 0이 아니고 1부터 시작한다. 배열 A[i][j]의 값은 i × j이다. 2차원 배열 A를 일차원 배열 B로 만들어서 오름차순으로 정렬하면 배열 B에서 K번째 인덱스 값을 구해라 사이트: https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제풀이 이번 문제는 간단해 보일거 같은데.. 배열 A에서 완전탐색으로 값을 넣..

문제 요약 알고리즘 분류: 그리디 난이도: 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 문제풀이 이번 문제는 그리디 알고리즘 중 그리디 알고리즘이다. 그리디 알고리즘의 관련 내용은 아래 사이트에 확인 해보면 되고 예제중에 거스름돈이 있으니 그것 확인 해보면 ..

이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알고리즘이다. 이 알고리즘은 이론상 설명 단순하고 다른 알고리즘에서 기초적으로 다루는 알고리즘이다.