[1182] 부분수열의 합시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초256 MB99180449482929243.323%문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.문제 풀이이 알고리즘의 문제풀이는 수열이 있을때 크기가 양수인 부분수열중에서 그 수열의 원소가 더한 값이 S가 되는 경우의 수를 구하..

[14267] 회사 문화 1시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초512 MB112084301323936.492%문제영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력하시오,입력첫째 줄에는 회사의 직원 수 n명, 최초의 칭찬의 횟수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤..

트리계층적인 자료구조그래프의 일종사이클이 비순환적 구조이다.최상위 노드를 루트로가 한다.노드트리를 구성하는 각각의 요소루트트리의 최상위 노드부모 노드어떤 노드의 바로 위 노드자식 노드어떤 노드의 바로 아래 노드리프자식 노드가 없는 노드서브 트리트리내 특정노드를 루트로 하는 트리레벨Level 1으로 하였을 때, 각 노드의 깊이[11725] 트리의 부모 찾기시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB99818454693188243.170%문제루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.입력첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두..

재귀함수자기 자신을 호출하는 함수를 재귀함수라고 한다.사용 이유하나의 커다란 문제를 작은 문제로 나누어 해결하기 위해서문제를 귀납적으로 생각하기 위해서귀납적 예시, {i}번째 답을 구하기 위해 (i-1), (i-2), … 번째 결과를 활용한다.예시숫자 출력오름차순과 내림차순을 재귀로 출력하는 방법을 봐 보자.아래 사진을 보면 재귀를 통하여 출력되는 것을 볼 수 있다.class Main { static class PrintNumber { public void asc (int n) { if (n==0) return; asc(n-1); System.out.println(n); } public void desc..

[1966] 프린터 큐시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초128 MB87682509864012458.876%문제여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤..

Queue먼저 넣은 데이터가 먼저 나오는 형태(선입선출)의 자료구조를 의미한다. (First - In - First - Out)가장 뒤에 원소가 추가되고, 가장 앞에 원소가 처리된다.예를 들어, 티겟팅 대기열, 프린터 출력, 운영체제 스케줄링, 메세지 큐 등Queue 역시 인터페이스로 구현 되어 있다.Linked list 기반의 Queueenqueue: addLast를 사용해 리스트의 가장 앞 원소를 추가한다. (push)dequeue: removeFirst를 사용해 리스트의 가장 앞 원소를 삭제한다. (pop)public class MyListQueue { private int size = 0; private Node frontNode = null; private Node rearNode = null;..

List Interface와 구현체간의 비교일단 List를 알기전 Array를 알아보자.Array(배열)정의동일한 타입의 여러 원소를 선형 집합으로 관리하는 정적 데이터 구조선형: 데이터가 순차적으로 저장되는 구조, 순서가 있는 데이터의 집합정적: 생성과 동시에 크기가 고정되어 늘릴 수 없다.메모리상에 일렬로 저장되어 Random Access가 가능하다.Random Access: 데이터의 위치(인덱스)를 알고 있다면 한 번에 접근이 가능한 특성메소드특징원소에 접근하고 변경하는 것은 빠르다.중간 원소를 추가/삭제시 연속적인 상태를 유지하기 위해 원소를 옮기는 작업이 필요하다.List동일한 타입의 여러 원소를 선형 집합으로 관리하는 동적 데이터 구조동적: 원소가 추가/삭제됨에 따라 크기가 변경 될 수 있음...

[17609] 회문시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초 (추가 시간 없음)512 MB315558988663429.094%문제회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는..

[12891] DNA비밀번호시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초512 MB2857410363754635.011%문제평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어..

투 포인터 알고리즘코딩테스트에서 자주 나오는 유형 중 하나인 투 포인터 알고리즘에 대해 알아보자.먼저 말로 풀어보면 선형 데이터 구조에서 두 개의 인덱스를 관리하여 특정 조건을 만족하는 부분집합이나 특정값이다.이렇게 해서는 이해하기 어려우니 문제 예시를 보며 이해를 해보자.[2003] 수들의 합 2문제N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각..

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초128 MB221546761462529.061%문제현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우..

Parmaetric SearchBinary Search를 이용한 최적값 탐색 기법을 Parmaetric Search라고 한다.최적값이란, ~~를 할 수 있는 최소값, 최대값, 어떤 조건을 만족하는 최적값을 의미한다. 좀 더 자세히 봐보자.연속적이거나 이산적인 값의 집합에서 최적갑 X를 찾는 문제에서 X를 경계로 조건을 만족하는 집합과 답이 될 수 없는 집합을 판정할 수 있을 때 추정값 A에 대한 판정을 반복해 X를 찾는 방법이다.이전에 풀었던 문제 숫자 카드 2를 비유해서 봐보자.모든 추정값 A를 모두 확인하지 않아도 최적값 X를 기준으로 판정결과가 나눠진다면 Binary Search를 적용해볼 수 있다.그렇다면 Parmaetric Search를 이용한 문제를 풀어 보자.[2417] 정수제곱근시간 제한 ..

문제KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특..

[2295] 세 수의 합시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초128 MB163975042335728.500%문제N(5 ≤ N ≤ 1,000)개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라.예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다.입력첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에 차례로 U의 원소가 하나씩 주어진다. 주어진 U는 집합이 되므로 입력되는 두 수가 같아서는 안 된..

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB84218385052856343.919%문제N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.입력첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째..