본문 바로가기

전체 글

 (84)
백준 11049 행렬 곱셈 순서 www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net 이 문제는 개인적으로 좋은 문제라고 생각한다. 또한 나에게 분할정복과 다이나믹 프로그래밍에 대한 많은 깨달음을 준 문제이기도 하다. 상당한 난이도가 있다고도 생각된다. 일단 곱셈이 이루어질 2개의 행렬 A, B가 있을 때, A의 행의 수와 B의 열의 수와 A의 열의 수(=B의 행의 수)의 곱이 두 행렬의 곱에서 발생하는 곱셈 횟수가 된다. 행렬 ABCDEF가 주어질 경우, 앞에서부터 순서대로 곱해..
백준 9095 - 1, 2, 3 더하기 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이전 포스팅과 마찬가지로 이번에도 다이나믹 프로그래밍 문제이다. 아주 기본적인 형태이다. DP(Dynamic Programming)문제를 풀 때, 가장 중요한 것 중 하나가 바로 점화식을 구하는 것이다. 점화식이란 말 그대로 어떠한 연속된 연산의 불을 붙여주는 기초 공식이라고 볼 수 있다. 즉, 이전 포스팅(백준 회의실 배정 문제)에서 살짝 언급한 바와 같이, 연속된 연산이 하나의 공식(점화식)하에서 계속 이루어지기 위해서는 모든 정점(상황)에서 항상 같은 규칙이 적용될 수 있어야 한다. 이 문제에서는 어떠한..
백준 1003 피보나치 함수 www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 이 문제는 피보나치 수열을 응용하여 만든 재미있는 문제이다. 피보나치 수열은 기본적으로 f(n)=f(n-1)+f(n-2)의 형태를 갖는다. 따라서 재귀함수의 형태로 공식을 구현할 수 있지만, 중간 과정에서 찾은 값들을 기록하지 않는다면 너무 많은 연산이 필요하게 된다. 이 문제에서는 f(0)에 다다랐을 경우, '0'을 출력하고 f(1)에 닿으면 '1'을 출력하도록 되어있다. 단순하게 생각하면 재귀로 계속 파고 들어 f(0)이나 f(1)에 닿아야 할 것 같지만, 그렇게 하면 당연히 너무 많은 시간이 필요하게 ..
백준 2292 벌집 www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌�� www.acmicpc.net 이 문제는 관찰과 약간의 산수(?)를 통해 해결할 수 있다. 벌집은 육각형으로 이루어져 있고, 계속 중심의 육각형을 감싸는 방식으로 확장하므로, 바깥쪽 둘레는 항상 안쪽보다 6씩 더 길어진다. 그 점에 착안하여 공식을 세우면 된다 #include #define endl '\n' using namespace std; int cnt,n,m=1; int main() { ios::sync_with_stdio(false);c..
백준 11000 강의실 배정 (C++, 파이썬) www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 백준 1931 회의실배정 문제와 함께 풀어보아야 할 기본적인 그리디 알고리즘 문제라고 생각한다. 이 문제는 계속 강의실을 새로 개설할 수 있고 몇 개의 강의실이 필요한지를 구한다는 점에서 다르다. 바로 풀이내용부터 설명하면, 우선순위 큐를 2개 사용하여, 하나에는 강의시간표를 담고 (시작시간 오름차순), 다른 하나에는 보유하고 있는 강의실 목록 (종료시간 오름차순)을 담으면 된다. 이처럼 정렬을 통해 기본적인 문제 설정 몇 가지를 해결하고, 가장 일찍 시작하..

티스토리툴바