코딩테스트/Python 문제풀이

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

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번: 곱..

[백준] N-Queen

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백 트래킹을 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N이 주어질 때, N*N의 체스판에 N개의 Queen을 배열하는 가짓수를 return해야 합니다. 사실 이전에 프로그래머스를 통해 해결한 적이 있는 문제입니다. https://life318.tistory.com/5 [프로그래머스] N-Queen https://programmers.co.kr/learn/courses/30/lessons/12952 ..

[백준] 스티커

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 위 그림처럼 스티커와 점수가 있습니다. 이때, 한 스티커를 떼어내면 그 스티커의 바로 이웃한 스티커들은 사용할 수 없다고 할 때, 스티커를 최대한 높은 점수로 떼어낼 때의 점수를 구해야 합니다. 이 문제는 다이나믹프로그래밍을 이용해야 합니다. 우선 스티커를 떼어내는 경우들을 생각해보면, 항상 지그재그 모양인 것..

[백준] 이진 검색 트리

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리 자료구조를 이용하고, dfs 또는 재귀를 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 이진 검색트리를 preorder traversal한 결과가 주어질 때, 이 이진 검색트리를 postorder traversal한 결과를 return 해야 합니다. 사실 이 문제는 이전에 포스팅 했던 https://life318.tistory.com/80 [백준] 트리의 순회 https..

[백준] 치즈

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net bfs를 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 치즈가 펼쳐져 있는 모눈종이가 주어지는데, 가장 바깥쪽 공기와 두면 이상 접촉해 있는 치즈는 한시간 만에 녹아 없어집니다. 이 때, 모든 치즈가 사라지는데 까지 걸리는 시간을 return 해야 합니다. (단, 치즈 내부에 있는 공기와 접촉한 것은 면 수에 포함하지 않습니다) 간단한 예시로 문제를 더 추가설명 해보면, 다음..

[백준] 별 찍기 - 11

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 재귀를 이용하는 문제입니다. 우선 문제부터 요약하면, 첫쨰줄부터 N번째 줄까지 별을 출력해야 하는 문제입니다. N은 항상 3×2^k의 형태로 주어지며, 간단한 예시로는 k=0 -> N=3 k=1 -> N=6 k=2 -> N=12 다음과 같이 규칙성이 있게 출력이 되어야 합니다. 문제에 대한 이해 자체는 쉽습니다. 구현은 어떻게 해야할까요? 위의 표 안의 상황에서 k=0에서 k=1로 변하는 상황을 통해 이후에도 같은 과정을 반복해서 더 큰 별들을 만들..

[백준] LCS

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net Dynamic programming을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 첫째 줄과 둘째 줄에 들어온 두 문자열의 최장 공통 부분수열의 길이를 출력해야 합니다. LCS(Longest Common Subsequence)문제입니다. 점화식을 세워서 Dynamic programming으로 해결 할 수 있습니다. 아이디어는 다음과 같습니다...