알고리즘41

• [백준]10830_행렬 제곱_분할 [문제 링크] https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net [생각 흐름] n이 짝수인 경우에는 n/2를 계산한 만큼의 곱을 한 번 더 제곱하면 되고, n이 홀수인 경우에는 (n-1)을 반으로 나는 것을 제곱하고 후에 배열을 한 번 더 곱해주면 된다. 9인 경우 4*2와 1, 4인 경우 2*2, 2인 경우 1*2로 나누어 아래에서부터 차례로 올라가면 저장해둔 값을 곱해 준다. public static int[][] matrixSquare(int[][] ar.. 알고리즘 2022. 9. 27.

• [백준]14503_로봇청소기 [문제 링크] boj 14503 로봇청소기 구현 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [생각 흐름] 처음에는 문제의 조건대로 각 케이스별로 하려 하였으나 케이스를 묶을 수 있어서 묶어서 풀이하였다. 문제의 조건 2번의 말은 결국 현재 위치에서 왼쪽으로 돌면서 청소가 안되어있으면 가고 청소가 되어 있거나 벽이면 또다시 왼쪽으로 돌아서 확인한다는 것이다. 따라서 처음 시작 dir에서 왼쪽으로 돌아가며 벽이 아닌데 청소가 안되어 있는 경.. 알고리즘 2022. 9. 26.

• [백준]9935_문자열폭발_Stack [문제 링크] https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net [생각 흐름] 처음에는 자바에서 제공하는 replace를 반복하려 했으나 시간 초과 문제가 있다고 하여 스택으로 변경하였다 폭발하는 문자열의 마지막 문자열의 마지막 문자를 저장해 두고 그것과 같은 문자가 들어오는 경우 스택을 확인하는 방식으로 알고리즘을 구현하였다 푸는 중 2%에서 계속 메모리 초과 오류가 발생했는데 StringBuilder 클래스를 사용하여 마지막 스.. 알고리즘 2022. 9. 25.

• [백준]9465_스티커_dp [문제 링크] https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net [생각 흐름] dp 방법으로 해결하였다 선택할 수 있는 방법이 (1번 줄, 2번 줄) OX, XO, XX 세 가지를 가질 수 있으므로 (O는 스티커가 있다, X는 스티커가 없는 경우) 각 경우에 맞춰서 초기값을 계산하였다. 그리고 아래의 코드와 같이 ox-> xx , ox->xo, xx-> ox, xx->xo, xx->xx , xo->ox , xo->xx로 7가지의 경우로.. 알고리즘 2022. 9. 25.

• [Programmers]합승 택시 요금 [문제 링크] https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [생각 흐름] 플로이드워셜 알고리즘이용 start에서 i까지 같이 가고 i 부터 a,b까지 가는 경로 [코드] import java.util.Arrays; public class Main { public int solution(int n, int s, int a, int b, int[][] fares) { int arr[][] = new int[n+1][n+1]; int INF = .. 알고리즘 2022. 9. 23.