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. 입력받..

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

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초128 MB274609311647330.856%문제N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.입력첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.출력첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. ..

투 포인터 알고리즘코딩테스트에서 자주 나오는 유형 중 하나인 투 포인터 알고리즘에 대해 알아보자.먼저 말로 풀어보면 선형 데이터 구조에서 두 개의 인덱스를 관리하여 특정 조건을 만족하는 부분집합이나 특정값이다.이렇게 해서는 이해하기 어려우니 문제 예시를 보며 이해를 해보자.[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는 집합이 되므로 입력되는 두 수가 같아서는 안 된..

[17232] 생명 게임시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초512 MB78528422446.186%문제생명 게임은 수학자 콘웨이(John Horton Conway)가 창안한 게임으로, 바둑판 모양의 격자에 '생명'을 배치하고 그 변화를 관찰하는 게임이다.  준표는 콘웨이가 창안한 생명 게임에서 사소한 조건을 바꿔 새로운 규칙의 생명 게임을 제안 해보았다.바둑판의 각 칸은 주위에 몇 개의 생명이 존재하는지에 따라 다음 상황이 아래와 같이 결정된다.생존 : 만약 현재 칸에 생명이 있고, 주위에 a개 이상 b개 이하의 생명이 있다면 현재 칸의 생명은 다음 단계에 살아남는다.고독 : 만약 현재 칸에 생명이 있고, 주위에 a개 미만의 생명이 있다면 현재 칸의 생명은 외로워서 죽는다.과밀 :..

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율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) 둘째..

[11659] 구간 합 구하기 4누적합 배열이 어떻게 사용되는지 문제를 풀어보며 이해해보자.시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB138676567894147038.443%문제수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.출력총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.제한1 ≤ N ≤ 100,0001 ≤ M ≤ 100,0001 ≤ i ≤ j ≤ N문제풀이이 문제는 수 N개가 주어 졌을 ..

[1931] 회의실 배정시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초128 MB237241790935455230.999%문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.입력첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보..