코딩테스트/Python 문제풀이
[백준] 외판원 순회
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 다이나믹 프로그래밍과, bit masking을 이용하는 문제입니다. 우선 문제의 핵심부터 간단하게 요약하면, N개의 도시를 임의의 도시에서 출발해서 한번씩 전부 방문하고 원래 있던 도시로 돌아오는 최소 비용을 구해야하는 문제입니다. https://en.wikipedia.org/wiki/Travelling_salesman_problem Travelling sal..
[백준] N과 M (5)
https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net Permutation(순열)을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N개의 자연수가 주어질 때, 길이 M인 수열을 만들어 사전순으로 출력해야 하는 것이 문제입니다. 크게 어려운 점 없이 python의 경우 itertools libraray를 사용하여 permutations를 활용하면 됩니다. 이 때, 사전순 정렬을 위해 list를 미리 sorting 해주면 자동적으로 p..
[백준] 트리의 부모 찾기
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을 기준으로 생각해보면 ..