본문 바로가기
반응형

재귀5

백준 1662] C++ 압축 해당 문제는 백준 사이트에서 풀 수 있습니다. www.acmicpc.net/problem/1662 1. 문제 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오. 입력 첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다. 출력 첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 int범위다. 예제 입력 1 33(562(71(9))) 예제 출력 1 19 예제 입력 2 142(6(2)45(99)).. 2020. 11. 24.
백준 2447] C++ 별 찍기 - 10 해당 문제는 백준 사이트에서 풀 수 있습니다. www.acmicpc.net/problem/2447 1. 문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. 입력 첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다. 출력 첫째 줄부터 N번째 .. 2020. 11. 22.
백준 2630] C++ 색종이 만들기 해당 문제는 백준 사이트에서 풀 수 있습니다. www.acmicpc.net/problem/2630 1. 문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서, 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, .. 2020. 11. 17.
프로그래머스] C++ 연습문제 - 줄 서는 방법(level 3) 해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다. 아래 링크를 통해 풀 수 있습니다. https://programmers.co.kr/learn/courses/30/lessons/12936# 1.문제n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.제한사.. 2020. 6. 14.
C++ 이진탐색 구현하기(재귀) 이진탐색이란? 정렬되어 있는 배열의 수를 효율으로 빠르게 찾는 방법입니다. 실생활에서 쓰일 수 있는 예로는...... 술게임의 업다운이 있습니다. 물론 해당 숫자를 찾을 때, 50, 25, 17.... 이런식으로 진행하면 안되지만..... 떠오르는 예제가 이것밖에 없내요..ㅎㅎ..... 시간 복잡도는 O(longN) 이며 4,294,967,296개(약 43억개)를 32번만에 찾아낼 수 있는 빠른 알고리즘 입니다. 기초적이지만 재귀함수를 사용해 찾는 방법이라 재귀를 처음 접하거나 익숙하지 않다면 구현이 다소 어렵고 이해하기도 어렵습니다. 이런 좋은 알고리즘이지만 한가지 제약조건이 필요한데, 그것은 숫자가 정렬되어 있어야 한다는 점입니다. 우선 코드를 보겠습니다. #include using namespace.. 2019. 12. 4.
반응형

스킨편집 -> html 편집에서