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) 둘째..

[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 줄까지 각 회의의 정보..

[10250] ACM호텔시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB206413709675986933.316%문제ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 여러분은 지우를 도와 줄 프로그램을 작성하고자 한다. 즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다.문제를 단순화하기 위해서 호텔은 직사각형 모양이라고 가정하자. 각 층에 W 개의 방이 있는 H 층 건물이라고 가정하자 (1 ≤ H, W ≤ 99). 그리고 엘리베이터는 가장 왼쪽에 있다고 가정하자(그림 1 참고). 이런 형태의 호텔을 H..

회문인 수시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초256 MB47662414200154.331%문제어떤 수를 왼쪽부터 읽어도, 오른쪽부터 읽어도 같을 때 이 수를 회문인 수라고 한다. 예를 들어, 747은 회문인 수이다. 255도 회문인 수인데, 16진수로 표현하면 FF이기 때문이다. 양의 정수를 입력받았을 때, 이 수가 어떤 B진법 (2 ≤ B ≤ 64)으로 표현하면 회문이 되는 경우가 있는지 알려주는 프로그램을 작성하시오. B진법이란, 한 자리에서 수를 표현할 때 쓸 수 있는 수의 가짓수가 B라는 뜻이다. 예를 들어, 십진법에서 B는 10이다.입력입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T..

완전탐색즉 무식하게 모든 케이스를 다 시도해보는 것문제해결의 가장 기본적인 방법정답률 100% 보장완전탐색이란 모든 경우의 수를 시도한다. 모든 경우의 수를 체계적으로 검사할 수 있도록 설계해야 함.문제가 요구하는 바를 이해하고, 정확히 구현할 수 있어야 한다.가장 쉽고 간단한 접근효율을 생각하지 않기 때문에 문제의 크기가 작으면 유용하다.문제의 크기가 클수록 시간/공간복잡도가 늘어나 적용이 어려울 수 있다.완전한 정답이 되지 못하더라도 문제를 이해하거나 테스트케이스를 확인하기 위한 용도로 적용해볼 수 있다.부분점수 문제라면 전체를 풀지 못해도 작은 데이터에 대한 점수를 얻을 수 있다.선형 완전탐색, 비선형 완전탐색등이 있으나 아직은 선형탐색만시뮬레이션문제에 주어진 상황을 그대로 진행하며 해결해보는 기법..

수 정렬하기 3시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율5 초 (하단 참고)8 MB (하단 참고)324390777255931523.852%문제N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.출력첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.문제풀이이 문제는 저번에 풀었던 줄세우기와 유사한 문제로 입력받은 값을 배열로 받아 정렬을 해주는 문제이다.이 문제의 시간복잡도와 공간복잡도를 생각해보자.시간복잡도 & 공간복잡도시간 제한은 5초이다. 만약 저번 줄세우기 문제를 풀었던 ..