본문 바로가기

알고리즘/문제풀이

 (78)
연속부분최대합L 문제N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다. 입력첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 1,000,000 ) 두 번째 줄에 n개의 정수가 주어진다. 출력연속된 부분을 선택하였을 때의 최댓값을 출력한다. 예제 입력8 2 3 -5 8 -3 4 2 -9 예제 출력11 예제 입력5 -1 -2 3 -2 4 예제 출력5 연속부분최대합을 동적계획법으로 푸는 풀이다. Table(i) 를 i번째 수를 오른쪽 끝으로 하는 연속부분 중 최대합이라고 정의한다. 그러면 Table에 대한 점화식은 Table(i) = max ( Table(i-1) + Data(i) ..
연속부분최대합 문제N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다. 입력첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두 번째 줄에 n개의 정수가 주어진다. 출력연속된 부분을 선택하였을 때의 최댓값을 출력한다. 예제 입력8 2 3 -5 8 -3 4 2 -9 예제 출력11 예제 입력5 -1 -2 3 -2 4 예제 출력5 주어진 숫자들 중에서 연속부분의 최대합을 구하는 문제이다. 완전탐색을 해서 범위를 점점 늘리거나 줄여가면서 구하면 쉽게 구할 수 있는 문제이지만, 입력을 보면 범위가 100,000 까지 이기 때문에, 완전탐색으로 시간복잡도가 이 되면 시간..
전염병 문제철수네 마을에는 갑자기 전염병이 유행하기 시작하였다. 이 전염병은 전염이 매우 강해서, 이웃한 마을끼리는 전염되는 것을 피할 수 없다. 철수네 마을은 1번부터 N번까지 번호가 매겨져 있다. 철수네 마을의 구조는 꽤나 복잡한데, i번 마을에서 출발하면 i * 2 번 마을에 갈 수 있고, 또한 i / 3(i를 3으로 나눈 몫) 번째 마을에도 갈 수 있다. 전염병은 사람에 의하여 옮는 것으로 알려져 있다. 따라서 i번 마을에 전염병이 돌게 되면, i * 2 번 마을과 i / 3(i를 3으로 나눈 몫) 번 마을 역시 전염병이 돌게 된다. K번 마을이 가장 처음으로 전염병이 돌기 시작했을 때, 전염병이 돌지 않는 마을의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 전체 마을의 개수 N과, 처음으로 전염..
탑 문제KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가..
중복없는구간 문제n개의 숫자가 주어지고, 이 중에서 r개의 연속된 숫자를 선택했을 때, 이 연속 부분 내에는 숫자가 중복되지 않기를 원한다. 예를 들어, 다음과 같이 10개의 숫자에서 3개의 연속된 숫자를 선택할 수 있다.이렇게 선택을 하면, 선택된 숫자들 사이에서는 중복이 존재하지 않는다. r의 최댓값을 구하는 프로그램을 작성하시오. 위의 경우, (4, 2, 1, 3)을 선택하면 되므로 r의 최댓값은 4이다. r이 5 이상이 될 경우, 중복 없이 연속 부분을 선택하는 것이 불가능하다. 입력첫째 줄에는 숫자의 개수 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 둘째 줄에 n개의 숫자가 주어진다. 각 숫자는 항상 1보다 크거나 같고, n보다 작거나 같다. 출력r의 최댓값을 출력한다. 예제 입력10 1 3 1 2 ..
mountain 문제봉우리가 여러개인 산 모양을 출력한다. 산 모양은 그림과 같고 좌우 대칭이다. 입력첫 번째 줄에 숫자를 입력 받는다. 숫자의 크기는 20보다 작은 자연수이다. 출력출력 예의 형식으로 출력한다. 예제 입력3 예제 출력1213121 예제 입력5 예제 출력1213121412131215121312141213121 binary 문제와 똑같다고 볼 수 있는 문제이다. 입력이 4일때 설명해보면 그림과 같이 나타낼 수 있다.m이 mountain 함수라고 치면, m(4)를 호출했을때 양쪽에서 m(3)이 호출되는 구조로 볼수 있다. 그래서 기저조건인 1까지 내려갔을때 1을 출력하면 된다.
binary 문제숫자를 입력 받아 이진수로 출력하는 프로그램을 작성하시오. 입력첫 번째 줄에 숫자를 입력 받는다. 숫자의 크기는 1,000보다 작거나 같다. 출력첫째 줄에 숫자를 이진수로 바꾸어 출력한다. 예제 입력14 예제 출력1110 예제 입력31 예제 출력11111 이번에 재귀함수를 정리하면서 풀게된 기초문제이다. 14를 2진수로 표현해 보자. 몫을 계속 2로 나누고 몫이 1이 되었을때 나머지들을 역순으로 출력하면 된다. 주의할점은 재귀함수를 호출하고나서 나머지를 출력해야 숫자가 역순으로 나와서 답이 된다.
괄호의 값 문제4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.‘()’ 인 괄호열의 값은 2이다.‘[]’ 인 괄호열의 값은 3이다.‘(X)’ 의 괄호값은 2×값(X) ..

티스토리툴바