반응형 분할정복4 [백준 20187] 종이접기 2020년 정보 올림피아드 2차 대회에서 초등부 2번, 중등부 1번 문제였던 종이접기, 백준 온라인 저지에서 20187번을 풀어 보도록 하겠습니다.문제 출처 : https://www.acmicpc.net/problem/20187문제 이해하기어릴적에 종이를 얼마나 접을 수 있을지 꼬깃꼬깃 접었던 기억이 있습니다. 그렇게 종이를 접고 접다보면 최종적으로 1 X 1 크기의 정사각형이 됩니다. 여기에 4등분 하여 하나의 위치에 구멍을 뚫고 접었던 반대로 풀기 시작하면서 구멍이 뚫린 위치를 출력해주면 됩니다.마지막 1 X 1 정사각형의 위치는 어떻게 잡으면 될까요? 규칙적으로 접고 접었다가 다시 펼치는 알고리즘을 생각해보면 분할 정복으로 문제를 해결할 수 있습니다. 전체크기를 하나하나 줄여 나가다보면 제일 마지막.. 2024. 10. 15. [백준 4779] 칸토어 집합 문제 출처 : https://www.acmicpc.net/problem/4779 이 문제는 재귀함수나 분할정복으로 구현할 수 있는 문제 입니다. 다빈치코딩 알고리즘 재귀 부분에 이 문제가 없어 아무 생각없이 작성했는데 분할 정복에서 이미 작성해 놓았다는 것을 알았습니다. 분할정복과 재귀 두 방법을 비교해 보면서 확인해 보시기 바랍니다. 분할 정복으로 푼 방법 : https://wikidocs.net/206410 02. 칸토어 집합[백준 4779]# 칸토어 집합(4779) 문제 출처 : [칸토어 집합](https://www.acmicpc.net/problem/4779) 3등분으로 분할 정복하는 문제 입니다. 주어진 길이…wikidocs.net 칸토어 집합이란 0과 1 사이를 삼등분 해나가면서 가운데 부분을.. 2024. 10. 1. [백준 17613] 2019 정올 1차 고등부 "점프" 문제 출처 : https://www.acmicpc.net/problem/17613 17613번: 점프 T개의 줄에 각각 하나의 정수를 출력한다. 각 줄에 출력되는 정수는 구간 [x, y]안의 수들의 점프넘버들 중 최댓값이다. 각 정수는 입력으로 주어지는 구간의 순서에 맞게 출력되어야 한다. 즉, 첫 www.acmicpc.net 이 문제는 2019년 정보올림피아드 1차 고등부 2번 문제 입니다. 점프를 하면서 해당 위치에 갈 수 있는 가장 짧은 점프 횟수를 찾는 문제 입니다. 여기 까지는 쉽지만 범위 안에 있는 모든 짧은 점프 횟수를 찾아 그중 가장 큰 수를 출력해야 합니다. 문제 이해하기 예제 입력에 있는 3번째 경우를 보겠습니다. 12부터 16사이에 가장 큰 점프 횟수를 찾아야 합니다. 먼저 12에 도.. 2024. 2. 29. [백준 1725] 히스토그램(세그먼트 트리) 문제 출처 : https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 히스토그램은 다양한 풀이 방법으로 유명한 문제 입니다. 스택, 분할정복, 세그먼트 트리로 풀 수 있습니다. 여기서는 세그먼트 트리의 다양한 응용에 대해 배우기 위해 세그먼트 트리로 푸는 방법을 알아보겠습니다. 문제 이해하기 문제 풀이를 위한 개념은 이렇습니다. 아래와 같은 히스토그램이 있습니다. 처음부터 끝까지를 모두 포함하는 직사각형은 가장 낮은 높.. 2023. 9. 18. 이전 1 다음 반응형
