전체 글
-
백준 2226: 이진수코딩 2021. 8. 1. 00:32
https://www.acmicpc.net/problem/2226 2226번: 이진수 0과 1로 구성된 이진수가 있다. 이 이진수에서 0을 10으로, 1을 01로 동시에 치환하면 길이가 두 배인 이진수를 얻을 수 있다. 이러한 이진수들을 차례로 나열하면 하나의 이진수 수열이 된다. 편의 www.acmicpc.net 풀이 작은 N에 대한 문자열을 찾아내 규칙을 파악해보도록 하겠습니다. 1 2 3 4 5 1 01 1001 01101001 1001011001101001 이런 식으로 나오게 됩니다. N에 대한 문자열 S를 앞쪽의 반과 뒤쪽의 반으로 나누어보겠습니다. N 2 3 4 5 앞쪽 반 0 10 0110 10010110 뒤쪽 반 1 01 1001 01101001 앞쪽의 반도 그 전 단계를 이루는 앞쪽의 반..
-
백준 1188: 음식 평론가코딩 2021. 7. 25. 23:46
https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 풀이 예를 들어서 생각해봅시다. 소시지가 18개, 평론가가 8명 있다고 합시다. 그렇다면 몇 번의 칼질이 최소가 될까요? 18개의 소시지 중 16개의 소시지는 한 명당 두 개씩 나누어줍니다. 그러면 구하는 것은 소시지가 2개, 평론가가 8명일 때 필요한 칼질의 수가 됩니다. 2개의 소시지를 8개의 조각으로 나누는 것이 가장 효율적이기 때문에 하나의 소시지 당 3번의 칼질을 하면 6번의 칼질로 8명에게 같은 양을 줄 수 있습니다. 소시지가 10개, 평론가가 6명이 있다고 합시다. 10개 중의 6개는 한..
-
백준 21606: 아침 산책코딩 2021. 7. 24. 08:41
https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 108점 풀이 처음에 생각했던 풀이는 그냥 모든 '실내'에 대해서 dfs를 돌려서 계산을 하는 것이었습니다. 구현을 해놓고 보니 시간복잡도가 $O(N^2)$으로 예상이 되어 마지막 서브태스크를 통과하지 못할 것 같다고 생각했었고, 실제로도 그랬습니다. 108점 받은 코드입니다. #include using namespace std; int n; long long cnt; bool..
-
백준 1407: 2로 몇 번 나누어질까코딩 2021. 7. 21. 12:48
https://www.acmicpc.net/problem/1407 1407번: 2로 몇 번 나누어질까 자연수 N이 주어지면, 자연수를 유지하면서 N을 2로 몇 번까지 나눌 수 있는지를 생각해 볼 수 있다. 즉, N의 모든 약수 중 2의 거듭제곱 꼴이면서 가장 큰 약수를 생각하는 것이다. 예를 들어 15의 www.acmicpc.net 풀이 $$S(n)=\sum_{i=0}^{n} f(i)$$ 라 합시다(f(0)은 아무 값이나 상관없지만 저는 그냥 0으로 두었습니다). 문제에서 구하라 하는 값인 $f(A)+f(A+1)+\cdots+f(B-1)+f(B)$는 $S(B)-S(A-1)$로 나타낼 수 있습니다. 그러면 S(n)값은 어떻게 구하면 좋을까요? f(n)은 n이 홀수라면 무조건 1이 나옵니다. 그리고 n=2k..
-
백준 20929: 중간코딩 2021. 7. 18. 07:50
https://www.acmicpc.net/problem/20929 20929번: 중간 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 개행 간격 등을 조절한 것으로, 실제 입출력과는 다르다. 위 예시는 $N=2$이고, $A=[1,2]$, $B=[2,3]$인 경우에 대한 입출력이다. www.acmicpc.net 풀이 우선 N=1일 때는 A의 1번째 원소, B의 1번째 원소를 질문하여 그 중 작은 값을 출력하여 끝내면 됩니다. 질문의 한계인 40은 2×19+2라는 것을 관찰할 수 있습니다. 그러므로 A와 B를 각각 logN+1번씩 질문하면 될 것입니다. A 배열에서 중앙값이 존재한다고 판단되는 범위를 la번부터 ra번까지, B 배열에서 마찬가지로 lb번부터 rb번까지라고 해봅시다. 초기값은..
-
백준 21600: 계단코딩 2021. 7. 17. 12:30
https://www.acmicpc.net/problem/21600 21600번: 계단 자료의 분포를 아래의 그림과 같이 나타낸 그래프를 히스토그램이라고 합니다. 당신은 히스토그램 영역에서 가장 큰 계단을 찾으려고 합니다. 계단은 아래 조건을 만족하는 영역을 말합니다. www.acmicpc.net 문제는 위와 같습니다. 풀이 히스토그램에서 가장 왼쪽의 높이부터 차례대로 a[0], a[1], a[2], ...라고 합니다. dp[i]를 (a[i]가 계단의 가장 오른쪽인 계단의 최대 높이)라고 합시다. 점화식을 구해봅시다. 만일 a[i]가 dp[i-1]+1 이상이라면, a[i]가 높이 dp[i-1]+1인 계단의 가장 오른쪽 사각형이 될 수 있고, 그것이 최대이므로 $dp[i]=dp[i-1]+1$가 됩니다. 만..
-
백준 1915: 가장 큰 정사각형코딩 2021. 7. 16. 11:57
https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제는 다음과 같습니다. 정해 제가 실제로 푼 방법이랑은 다르지만, dp[i][j]=((i, j)를 포함하는 1로만 된 정사각형의 한 변의 최대 길이)라 잡으면 풀린다고 합니다. 이 방법은 다른 블로그에 많이 소개되어있으니 생략하겠습니다. 풀이 제 풀이입니다. 일단 1-based로 입력을 받습니다. 그리고 (1,1)부터 (i,j)까지의 모든 수의 합을 나타내는 배열 s[i][j]를 구합니다.(포함과 배제의 느낌으로) 만일 모든 수가 0이라면, 0을 출력하고 프로그램을..
-
[자료구조] 우선순위 큐(priority_queue)코딩 2021. 7. 15. 12:12
※코딩뉴비가 자신이 이해한대로 쓴 글이라 정확하지 않은 정보가 담겨있을 수 있습니다. 우선순위 큐란? 자신이 정해놓은 우선순위대로 넣었던 원소가 나오는 자료구조 우선순위 큐의 구현 우선순위 큐는 주로 힙(Heap)이라는 자료 구조로 구현합니다. 왜일까요? 삽입과 삭제에 대한 효율이 좋기 때문입니다. 배열로 우선순위 큐를 구현할 경우, 우선순위에 따라서 배열을 정렬해놓아 사용할 수 있습다. 그러면 가장 우선순위가 높은 원소를 삭제할 때에는 가장 앞의 원소를 삭제하면 되므로 O(1)의 시간복잡도가 걸립니다. 다만, 삽입 과정에서 최악의 경우 모든 원소와 하나하나 비교해야 하기 때문에 O(N)의 시간복잡도가 걸립니다. 연결 리스트로도 비슷하게 생각할 때 삽입은 O(N), 삭제는 O(1)이 걸립니다. 그..