Beelog

www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제는 위와 같으며 이전에 풀었던 파일 합치기 문제와 유사하게 ABC 행렬의 곱은 (AB)C 또는 A(BC) 중 최소값을 저장하는 방식으로 문제를 해결할 수 있습니다. 예제를 살펴보면 먼저 행렬(matrix)을 [[5, 3], [3, 2], [2, 6]] 으로 저장하고 순차적인 행렬의 곱을 나타내는 dp 이차원 배열에 dp[i][i + 1] = matrix[i][0] * matrix[i][1] * ..

www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 이 문제의 경우, 앞뒤로 붙어있는 두 파일을 합치는 방식으로 모든 경우를 확인하여 문제를 해결할 수 있습니다. 예제를 살펴보면 파일은 [40, 30, 30, 50] 이렇게 비용이 들고 앞에서부터 [a, b, c, d] 파일이라고 할 때, a 부터 d 파일까지 모두 합치는 경우는 (1) b+c+d 를 먼저 합치고 a+b+c+d 가 되는 비용 ((b+c+d) + (a+b+c+d)) (2) a+b 를 먼저 ..

programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 문제는 위와 같으며, 이 문제는 최대 공약수를 이용하여 문제를 해결할 수 있습니다. 예제를 통해 살펴보면 w = 8, h = 12 일 때, 대각선을 그으면 아래와 같이 작은 직사각형 패턴이 생기는 것을 알 수 있습니다. 작은 직사각형의 크기를 보면 w, h 를 최대 공약수로 나눈 것임을 알 수 있습니다. 따라서 유클리드 호제법을 통해 최대 공약수(G..

www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 문제는 위와 같으며, 이 문제는 다익스트라 알고리즘을 사용하여 문제를 해결할 수 있습니다. 1. 주어진 컴퓨터의 관계를 이차원 배열에 기준 컴퓨터(b) 인덱스에 [감염되는 시간(s), 연결된 컴퓨터(a)] 형태로 데이터를 저장합니다. 2. 다익스트라 알고리즘을 수행하여 감염 시작 컴퓨터(c) 부터 연결된 컴퓨터 각각이 감염되는데 걸리는 최소 시간이 담긴 배열을 구합니다. 3. 해당 배열에서 값이 INF (무한대) ..

www.acmicpc.net/problem/1325 max_value: # 현재 연결된 컴퓨터 수가 기존 최대 연결 컴퓨터 수보다 큰 경우 max_value = c # 현재 연결된 컴퓨터 수로 최대값 수정 result = [i] # 해당 컴퓨터 번호도 수정 elif c == max_value: # 현재 연결된 컴퓨터 수가 기존 최대 연결 컴퓨터 수와 같은 경우 result.append(i) # 해당 컴퓨터 번호 추가 for r in result: print(r, end=" ") 자바 코드는 다음과 같습니다. 파이썬과 같은 로직이지만, 시간 초과 문제를 해결하지 못하였습니다... ㅠㅠ import java.io.BufferedReader; import java.io.InputStreamReader; imp..