Beelog

www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제는 위와 같으며, 지점의 높이를 이차원 배열로 저장하고 해당 배열과 동일하게 특정 위치를 방문했는지 알 수 있는 배열을 생성한 뒤 -1로 초기화 합니다. 방문했던 위치가 - 도착 지점과 같은 경우 1을 반환하고 - 한번이라도 방문한 적이 있는 경우(저장된 값이 -1이 아닌 경우)는 해당 위치에 지금까지 방문했던 값을 반환하고 - 두 가지 경우가 아닌 경우는 상하좌우로 이동할 수 있는지 확인하고 이동하려는 위치의 ..

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 를 먼저 ..

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..