목록알고리즘 (4)
차근차근
https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 간단 설명 : 자연수 A를 B번 곱한 수를 C로 나눈 나머지 구하기 시간 제한은 0.5초인데 입력 값인 A, B, C의 범위가 1부터 2,147,483,647 이니까 시간복잡도를 잘 생각해서 코드를 짜야했다. 1. 나머지 연산 분배법칙 (A * B)%Q = (A%Q) * (B%Q) A와 B를 곱해서 나머지 연산을 나눈 값과 A의 나머지, B의 나머지를 곱한 값이 같다는 뜻이다 이유를 간단히 설명해보면 A = aQ + R1 ( a = A를 Q로 나눴을 때 몫, R..
해당 문제를 풀면서 고민했던 과정들을 정리해봤다 ੭ ᐕ)੭ 자 이번 문제는 (1)3으로 나누기 (2)2로 나누기 (3)1빼기 3가지 방법을 써서 가장 적은 횟수로 1을 만드는 경우의 최솟값를 출력하는 것이다 문제를 이해하기 쉽게 10을 1로 만드는 경우 과정을 그려보면 아래와 같다 3이나 2로 나누고 1로 빼면서 1이 만들어지면 멈춘다 구현은 큐를 이용해서 10을 넣고 꺼내면서 10/3 10/2 10-1 한 값을 큐에 넣고 다시 그 값을 꺼내면서 a/3 a/2 a-1 한 값을 큐에 넣는 과정을 반복할 것이다 여기서 생각해야 할 것은 (1) 꺼낸 값이 1이 되면 반복을 멈춘다 (2) 위의 3과 4처럼 이미 거쳐간 숫자는 다시 연산할 필요가 없으므로 visited 배열을 만들어서 사용한 수는 큐에 넣지 않고..
백준 2740번 - 행렬곱셈 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 보기 편하게 나타내면 다음과 같다 간단히 곱하는 과정을 보면 반복되는 여부에 따라 for문에 3개로 나눠진다 // 간단히 표현해 보면 for(i < A의 N){ for(j < B의 K){ for(t < A의 M){ a[i][k] * b[k][j] } } } BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer ..