알고리즘

[16198] 에너지 모으기 성공시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초512 MB65974967402476.270%문제N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.x번째 에너지 구슬을 제거한다.W × W의 에너지를 모을 수 있다.x+1x-1N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.N과 에너지 구슬의 무게가 주어..

[2529] 부등호시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB31504186331267758.215%문제두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다.3 1 7 0이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족..

[1759] 암호 만들기시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초128 MB85939412702828044.931%문제바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그..

[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..

[10799] 쇠막대기시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB59085384942858665.295%문제여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위..

균형잡힌 세상시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초128 MB160431549434232032.936%문제세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.모든 괄호들의 짝은 1:1 매칭만 가..

[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동일한 타입의 여러 원소를 선형 집합으로 관리하는 동적 데이터 구조동적: 원소가 추가/삭제됨에 따라 크기가 변경 될 수 있음...

[16472] 고냥이시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초512 MB63432645189640.085%문제고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고양이의 언어로, 고양이의 언어를 사람의 언어로 바꾸어 주는 희대의 발명품이 될 것이다.현재 고양이말 번역기의 베타버전이 나왔다. 그러나 이 베타버전은 완전 엉망진창이다. 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 굉장히 별로지만 그나마 이게 최선이라고 사람들은 생각했다. 그리고 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 ..

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

[11728] 배열 합치기시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1.5 초256 MB46953224241492846.484%문제정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.입력첫째줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.출력첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.문제풀이이 문제는 정렬된 두 배열을 주고 하나의 배열로 합치는데 다시 정렬하면 된다.처음에는 TreeSet을 사용하여 문제를 풀었지만 중복을 제거하면 안된다.0. 입력받..