일지 & 개발

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

문제 요약 알고리즘 분류: 큐, 데크 난이도: Silver4 문제내용: 배열 담을수 있는 공간 N 원소는 첫뻔째 원소만 뽑을 수 있다. 앞에 원소를 뒤로 옮길수 있다. 뒤에 원소를 앞으로 옮기수있다. M개의 빼야될 목록을 주면 최소 몇번 이동해야는 구해라. 문제풀이 이번 문제 큐와 데크에 관련된 문제이다. 일반적으로 배열이나 리스트로 구현하기에는 힘들어서 모듈을 들고 와서 처리를 해야한다. 큐와 데크에 대한 자세한 내용은 아래의 사이트에서 확인하면된다. https://namu.wiki/w/%ED%81%90(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0) 큐(자료구조) - 나무위키 어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용한다. 서로 다른 쓰레드 사이 또는 프로..

문제 요약 알고리즘 분류: 큐 난이도: Silver4 문제내용: 큐 담을수 있는 공간 N -1이면 입력 종료 0이면 pop연산 나머지는 큐 저장 큐 저장시 담을 수 있는 공간 꽉 차면 버린다. 문제풀이 이번 문제 큐에 관련된 문제이다. 일반적으로 구현하면 시간 초과가 떠서 큐 이론을 적용한 상태로 풀어야 된다. 큐에 대한 자세한 내용은 밑에 사이트에 참조하면된다. https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 큐 (자료 구조) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out..