![]()
문제 출저 https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 문제 풀이 재료들의 번호가 주어집니다. 재료들의 고유 번호를 합쳐서 M이 되는 경우의 수를 구해야 합니다. 두 포인터를 이용해 풀었습니다. 재료들을 정렬합니다. start, end 두 개의 포인터를 사용합니다. start는 배열의 시작, end는 배열의 끝에서 시작합니다. 두 개의 합을 합쳐서 M 보다 작으면 start를 올리고 M보다 크면 end를 줄입니다. ..
![]()
문제 출저 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 문제 풀이 인식할 수 있는 알파벳의 종류 n과 문자열이 주어집니다. 문자열에서 인식할 수 있는 최대의 길이를 구해야 합니다. 투 포인터를 이용해 풀었습니다. 어떤 알파벳이 몇 개 나왔는지 세기 위한 int[] counts = new int[26]; 일차원 배열을 이용했습니다. 알파벳 갯수는 26개 이므로 배열의 크기를 26으로 설정했습니다. int start = 0, int end = 1 인 두..
![]()
문제 출저 https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 문제 풀이 N개의 눈덩이가 주어집니다. 언니 엘자와 동생 안나는 각각 두 개의 눈덩이를 선택합니다. 눈 사람의 크기는 두 개의 눈덩이 지름의 합입니다. 두 사람의 눈사람 크기 차이가 최소일 경우를 구해야합니다. N의 크기는 4이상 600이하 입니다. 이중 포문과 투 포인터로 문제를 풀었습니다. 이중 포문으로 눈덩이 2개를 골랐습니다. 2개의 나머지 부분을 ..
![]()
문제 출저 https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 문제 풀이 -100,000,000 ~ 100,000,000 값을 갖는 용액이 n개 주어집니다. 두 개 용액을 섞어 0에 가장 가까운 값이 무엇인지 구해야 합니다. 투 포인터로 문제를 풀었습니다. int[] liquors 용액 배열에 입력값을 받습니다. Arrays.sort() 메소드를 통해 liquors int 배열을 정렬합니다. 처음과 끝은 두 개의 포인터..
![]()
문제 출저 https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 문제 풀이 성원이는 다이어트 중이다. 성원이의 현재 몸무게의 제곱 - 기억하는 몸무게의 제곱 = G 이다. 이 때 G를 만족하는 현재 몸무게를 구해야 한다. 투 포인터를 이용해 풀었습니다. long e : 현재 몸 무게 long s : 기억하는 몸 무게 이렇게 두 개의 포인터를 사용하여 e*e - s*s
![]()
문제 출저 https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 문제 풀이 수열이 주어질 때, 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구해야 한다. 투 포인터로 문제를 풀었습니다. end, start를 두 개의 포인터를 이용했습니다. end, start는 모두 0에서 시작합니다. end는 배열의 끝까지 탐색합니다. end 포인터에 걸린 숫자의 갯수를 +1 해줍니다. 만약 숫자의 갯수가 K보다 크다면 start가 움직입니다..
![]()
문제 출저 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 풀이 자연수의 숫자 n이 주어진다. 이 n을 제곱수로 표현할 때, 제곱수의 최소 갯수를 구해야 한다. 제곱수란 1, 4, 9 ... 와 같은 자연수의 제곱으로 만드는 숫자이다. DP를 이용해서 풀었습니다. n의 범위는 1부터 50,000 입니다. int[] dp = new int[50001]을 선언했습니다. dp 배열에 각 숫자의 제곱수의 최소값..
![]()
문제 출저 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 문제 풀이 히스토그램이 주어진다. 이 때, 히스토그램 내부에 가장 넓이가 큰 직사각형의 넓이를 구해야 한다. Stack을 이용해 문제를 풀었습니다. Stack에는 현재 탐색하는 막대보다 작거나 같은 값만이 들어갈 수 있습니다. 히스토그램의 막대의 위치를 Stack에 넣으며 탐색합니다. Stack에 담긴 이전 막대의 높이가 현재 탐색하는 막대의 높이보다 크..
![]()
자료구조란? 자료구조는 데이터를 효율적으로 저장, 관리, 처리하기 위한 다양한 형태입니다. 각각의 자료구조는 특정 문제를 해결하기 위해 설계되어있습니다. 상위 10개의 데이터 구조가 실제 세계에서 사용하는 모든 데이터 구조의 99%를 차지합니다. Array, Stack, Queue, Set, Map, Heap, Tree, Graph 질문 정리 저는 Java를 주로 사용하므로 Java 위주로 정리했습니다. 선형, 비선형 자료구조에 대해 설명해 주세요. 더보기 선형 구조 선형 구조는 데이터가 연속적으로 나열된 자료구조입니다. 긱 요소는 그 전후에 단 하나의 요소만을 가질 수 있습니다. 이로 인해 데이터 요소들은 한 줄로 나열될 수 있어 직선의 관계를 가집니다. 예시로는 배열, 연결 리스트(Linked Lis..
![]()
문제 출저 https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 문제 풀이 금액 T가 주어집니다. 동전의 금액과 갯수가 K개 주어집니다. 금액 T를 거슬러줄 수 있는 방법을 구해야 합니다. 예제) 20 3 5 3 10 2 1 5 금액 20원과 동전의 금액과 갯수가 3개 주어집니다. 동전의 금액과 갯수는 각각 5원짜리 3개, 10원짜리 2개, 1원짜리 5개입니다. DP를 이용해 풀었습니다. 냅색 알고리즘이 생각나 이를 응용해 풀었습니다..
![]()
문제 출저 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제 풀이 테스트케이스 t가 주어집니다. t만큼 주어진 문제를 풀어야 합니다. 문제는 나라의 개수 n개가 주어집니다. 그리고 항공편이 k개 주어집니다. 모든 나라를 탐색할 수 있는 항공편의 최소 개수를 구해야 합니다. 이 문제는 최소 신장 트리(MST)문제입니다. 최소 신장 트리의 특징은 간선의 갯수는 (정점의 갯수-1) 입니다. 그러므로 정답은 n..
![]()
이번에는 Generic을 정리해 보겠습니다. Generic이란? 제네릭이란 타입을 파라미터로 사용할 수 있 해주는 기술입니다. 제네릭을 사용하면 데이터 타입을 클래스 내부에서 지정하는 것이 아니라 외부에서 지정할 수 있습니다. List list = new ArrayList(); 부분이 제네릭입니다. Integer를 입력하여 List의 내부 타입을 Integer로 만듭니다. ava의 제네릭은 클래스, 인터페이스, 메소드를 정의할 때 타입을 파라미터로 사용할 수 있게 해주는 기능입니다. 제네릭을 사용하면 클래스, 메소드에 사용할 내부 데이터 타입을 컴파일 시에 미리 지정할 수 있습니다. 이를 통해 코드의 타입안정성, 재사용성, 가독성을 높일 수 있습니다. JDK 1.5 이전에는 여러 타입을 사용하는 클래스나..
