코딩테스트

[백준] 트리의 부모 찾기

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net dfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, root가 없는 트리가 주어지는데 이때, 1번 node를 root로 가정했을 때, 각각의 노드들의 parent 노드가 무엇이 되는지를 return 해야 합니다. (트리의 연결 상태는 단순히 연결이 되어있다 라는 정보로만 주어집니다.) 우선 이 문제는 node나 tree class를 만들 필요가 없습니다. 마치 트리를 구현해야 하는 문제 같지만 dfs를 통해 충분히 해결 할 수 있습니다. 트리의 정..

[백준] 구간 합 구하기 5

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 누적 합(Cumulative sum)을 이용해 구간 합(Prefix sum)을 구하는 문제입니다. 우선 문제부터 간단하게 요약하면, 2d array가 주어질 떄, 해당하는 array의 (x1, y1)와 (x2, y2)가 이루는 직사각형 면적 내부의 원소들의 합을 구해야 하는 문제입니다. 누적 합을 통한 구간 합을 이용하는 문제입니다. 간단한 예시를 통해 ..

[백준] 피보나치 수 6

https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 행렬의 거듭제곱을 분할정복으로 구해서 해결하는 문제입니다. 우선 문제부터 간단하게 요약하면, n번째 피보나치 수를 1,000,000,007로 나눈 나머지를 출력해야 하는 문제입니다. 이 때, n은 1,000,000,000,000,000,000보다 작은 숫자라는 조건이 있습니다. 처음 시도하였던 방법과, 그 방법이 안되는 이유에 대해 설명하고 문제의 정답에 대해 이야기해 보려 합니다. 이전 까지 문제를 해결할 때, 피보나치 수는 항상 다이나믹 프로그래밍으로 해결하였습니다. 하..

[백준] 플로이드

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘을 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, n개의 도시를 잇는 m개의 버스가 존재합니다. 이때, 버스들은 출발지, 목적지, 가는비용을 가지고, 출발지와 목적지가 같은 버스는 존재하지 않을 때, 특정한 도시를 출발하여 특정한 도시에 도착하는 최소 비용을 구해야 하는 문제입니다. 이 때, 이동이 불가능한 경우에는 0을 출력해야 합니다. 이 문제는 전형적인 플로이드..

[백준] 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 다이나믹 프로그래밍을 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 수열이 주어질 때, 그 수열안의 바이토닉 수열중 길이가 가장 긴 것을 return해야 합니다. 이 때, 바이토닉 수열이란 S(1) S(k+1) > ... S(N-1) > S(N)의 조건을 만족하는 수열입니다. 예시를 하나만 첨부하면, [1,2,3,7,5,4,1]은 7을 기준으로 생각해보면 ..

[백준] 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 수열이 주어졌을 때, 이 수열에서 가장 긴 증가하는 부분수열을 구하는 프로그램을 만들어야 합니다. 예를 들면, A = {10, 20, 10, 30, 20, 50}의 수열에서 가장 긴 부분수열은 A = {10, 20, 10, 30, 20, 50}..

[백준] 행렬 제곱

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 분할정복을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N*N의 행렬과 이것을 몇제곱 할지가 주어지면, 행렬을 해당하는 만큼 제곱한 결과를 return해야 합니다. 거듭제곱에 대한 이야기는 이전 여러 문제들에서 분할정복 방식으로 해결한 적이 있습니다. https://life318.tistory.com/61 [백준] 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱..

행렬의 곱셈

# 두 행렬 A,B를 곱해서 결과를 return한다 # input format은 [[1,2,3]],[[1],[2],[3]] 와 같이 곱할 두 행렬을 넣어주면 된다. # 만약 곱셈이 불가능한 경우 assertion에 걸린다. def multiple_matrix(A,B): # find dimension (row -> m, column -> n) m_A = len(A) n_A = len(A[0]) m_B = len(B) n_B = len(B[0]) assert(n_A == m_B) # return matrix return_matrix = [[] for _ in range(m_A)] tmp = list(zip(*B)) for i in range(m_A): for j in range(n_B): return_mat..