본문 바로가기

Programming456

#76 합의 경우의 수(Dynamic Programming) 이번 문제는 경우의 수를 계산하는 것입니다. 보통 분할(partition) 문제는 중복조합, 조합, 순열 등의 기법이 사용될 수 있지만, 이 문제와 같은 경우에는 분할이 쉽지 않습니다. 문제는 짧은 편입니다. N이란 숫자가 주어지면, 1부터 N-1 까지의 숫자중 2개 이상을 선택해서 그 합이 N이 되도록 하는 경우의 수를 찾는 것입니다. 예를 들어서 N=5라고 한다면, \( 5 = 1 + 1 + 1 + 1 + 1 \) \( 5 = 1 + 1 + 1 + 2 \) \( 5 = 1 + 1 + 3 \) \( 5 = 1 + 4 \) \( 5 = 1 + 2 +2 \) \( 5 = 2+ 3 \) 위와 같이 총 6가지가 나옵니다. 이 문제에서는 N=100일 때의 경우의 수가 얼마인지 계산하라는 문제입니다. 문제의 원본.. 2020. 1. 15.
#1286 부분 직사각형(구현) 이번 문제는 Gold IV 난이도 문제네요. N개의 줄에 M개의 글자가 각자 써져 있는 문자들을, 3번 복사를 해서 2N개의 줄에 2M개의 글자가 써져 있는 문자들로 만든 다음, 직사각형을 선택해서 부분 문자열들을 만드는 작업을 할 때, 모든 부분 직사각형에 나타나는 문자들의 빈도를 계산하라는 문제입니다. 예를 들어서 ABCD EFGH 라는 2줄에 걸쳐 각각 4글자씩의 문자열이 주어졌다면, 3번 복사를 해서 ABCDABCD EFGHEFGH ABCDABCD EFGHEFGH 를 만들고, 직사각형을 선택해서 필요한 부분문자열을 만듭니다. 예를 들어서 왼쪽위가 (1, 1), 오른쪽 아래가 (3, 2) 직사각형이 있다면, ABCDABCD EFGHEFGH ABCDABCD EFGHEFGH 가 선택되어서, F 글자의 .. 2020. 1. 15.
#1276 교각 놓기(정렬) 이번 문제는 Gold V 등급 난이도라고 되어 있지만, 문제 자체는 아주 쉽습니다. 영어가 제공되는 문제들의 특징들이 문제가 명확하게 설명되어서, 굳이 한글이 번역되지 않은 문제라도 풀만합니다. 2차원상에 다리가 있는데, 이 다리에 교각을 놓으려고 합니다. 다리 밑에 다른 다리가 있는 경우 거기까지만 교각을 세우면 됩니다. 이 때 교각의 총 길이를 계산하면 됩니다. 예를 들어서 다음과 같이 다리가 있다고 해보죠. 왼쪽 그림에서 총 다리가 3개가 있는데, 이 다리에 교각을 내려놓으면, 다른 다리에 얹히는 경우 실제 다리 높이보다 짧은 길이의 교각을 세우게 됩니다. 그렇게 해서 만들어진 교각이 오른쪽 그림입니다. 영어 문제에서는 다리가 서로 겹쳐있지 않다고 했으니까, 예외를 생각하지 않아도 됩니다. 서로 겹.. 2020. 1. 14.
[C/C++] 백준 #1275 커피숍2(세그먼트 트리) #1275 커피숍2는 세그먼트 트리를 이용한 전형적인 문제입니다. 문제 링크입니다. https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 백준 알고리즘 문제들 중 어려운 문제들의 유형이 몇가지가 있는데, 이 문제는 그 중 세그먼트 트리 등 이진트리의 변형을 이용하고 있습니다. 비트 단위로 만들 수 있는 펜윅트리도 있고, 원한다면 자신만의 트리를 만들 수 있습니다. 일반적인 2진트리가 왼쪽과 오른쪽 링크를 연결하는 구조로.. 2020. 1. 14.
#75 단일길이 정수 직각 삼각형 이번 문제는 피타고라스 삼각형을 만들고, 그것을 에라스토테네스의 체처럼 사용하는 문제입니다. 난이도 25% 문제입니다. 하지만, 피타고라스 삼각형을 만드는 공식만 알면 크게 어려움 없이 풀 수 있는 문제입니다. 이 프로그램을 작성할 때만 해도 STL을 거의 사용하지 않았을 때인지라 무식하게 배열을 사용했지만, STL의 map 자료형을 사용하면 더 쉽게 풀 수 있을거라고 보입니다. 문제를 간단하게 요약하자면 다음과 같습니다. 변의 길이가 정수인 직각삼각형이 있습니다. 둘레 길이가 주어졌을 때, 어떤 정수 직각 삼각형은 여러개가 나올 수 있습니다. L < 1,500,000 인 둘레길이를 가지면서, 해당 둘레에서 그러한 정수 직각삼각형이 오직 한개인 개수를 구하세요. 문제의 원본은 다음과 같습니다. https.. 2020. 1. 14.
#1256 사전(Combination Digit) 이번 문제는 사실상 조합을 찾아내는 문제입니다. 그런데 조합을 찾기 위한 숫자가 좀 큽니다. 그래보았자, 100이지만요. 난이도는 Gold IV입니다. 정답률은 28.5%이긴 하지만, 크게 어렵지 않았다고 생각했습니다. 문제의 내용을 정리하자면, N개의 a 문자와 M개의 z 문자를 조합하여 사전순으로 배열할 때, K번째 문자열을 출력하는 문제입니다. 예를 들어서 3개의 a와 2개의 z가 있다면 다음과 같이 사전순으로 나열할 수 있습니다. aaazz aazaz aazza azaaz azaza azzaa zaaaz zaaza zazaa zzaaa 이렇게 해서 총 10개의 문자열이 나옵니다. 10개의 문자열이 나온 이유는 5개의 공간 중에 2개의 공간을 선택해서 그곳에 z를 채우고, 나머지 공간에는 a로 채우.. 2020. 1. 13.
728x90

티스토리툴바