알고리즘 문제를 풀다 split에 대해 새로운 사실을 알게되어 글을 쓰게 됐다. ​ Java에서 split 함수를 알아보겠다. 문자열을 자르고(분할하고) 배열에 반환하고 싶을 때 많이 사용하는 함수이다. 매개변수로는 regex 즉, 정규표현식이 들어갈 수 있고 정규표현식과 limit (정수) 가 함께 들어갈 수 있다. ​ 먼저 매개변수에 정규표현식만 들어간 방식이다. String으로 선언한 aPhoneNumber 에서 "-" 기준으로 잘라 String 배열 a에 반환하는 방식이다. 실행결과는 아래와 같다. ​ ​ 그 다음은 limit 매개변수 까지 들어간 방식이다. limit는 뜻 그대로 제한을 두는 매개변수 이며 문자열을 자르고 배열을 반환할 때 배열의 갯수를 제한하는 것이다. 문자열 bPhoneNum..

https://www.acmicpc.net/problem/2822 2822번: 점수 계산 8개 줄에 걸쳐서 각 문제에 대한 참가자의 점수가 주어진다. 점수는 0보다 크거나 같고, 150보다 작거나 같다. 모든 문제에 대한 점수는 서로 다르다. 입력으로 주어지는 순서대로 1번 문제, 2번 문 www.acmicpc.net 알고리즘 분류 정렬 풀이 먼저 Node라는 인덱스와 점수를 담은 내부 클래스를 생성하였다. public static class Node{ private int index; private int score; public Node(int index, int score) { this.index = index; this.score = score; } } 그리고 Node 클래스형 1차원 배열을 만든..

https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 어떻게 풀까 매우 고민했었다. 정육면체의 한면의 최솟값을 구하고 x6을 할까 생각을 했었다. 하지만 정육면체중 한면, 두면, 세면만 보이는 작은 정육면체의 갯수를 구하고 그 합들을 더하기로 했다. ​ 먼저 한면만 보이는 정육면체이다. 먼저 내가 생각한 로직은 맨 위 한줄과 그 밑의 정육면체의 갯수를 구하고 그 한줄을 뺀 나머지 밑에 있는 정육면체의 갯수를 구한뒤 더하자고 생..

객체지향 개념에서 모든 것은 객체로 다루어져야 한다. 그러나 자바에서는 8개의 기본형(int, boolean 등등)을 객체로 다루지 않는데 이것이 바로 자바가 완전한 객체지향 언어가 아니라는 얘기를 듣는 이유이다. 그 대신 보다 높은 성능을 얻을 수 있었다. 때로는 기본형 변수도 어쩔 수 없이 객체로 다뤄야 할 하는 경우가 있다. 예를들면, 매개변수로 객체를 요구할 때, 기본형 값이 아닌 객체로 저장해야할 때, 객체간의 비교가 필요할 때 등등의 경우에는 기본형 값들을 객체로 변환하여 작업을 수행해야 한다. 이때 사용되는 것이 래퍼(Wrapper) 클래스 이다. 8개의 기본형을 대표하는 8개의 래퍼클래스가 있는데, 이 클래스들은 이용하면 기본형 값을 객체로 다룰 수 있다. 기본형 래퍼클래스 기본형 래퍼클래..

그리디라는 사전적 의미는 "탐욕스러운" 이다. 즉, 탐욕적으로 "현재 상황에서 가장 베스트인 것만 고르는 방법"인 알고리즘이다. 부분 최적해가 모이면 전체 최적해가 되다는 알고리즘이다. ​ 예를들어 서울 대구 부산을 지나간다고 가정을 해보자 (서울 - 대구 길에서 가장 빠른 길) + (대구 - 부산길에서 가장 빠른길) 를 찾아 더하면 최적해를 구할 수 있다. ​ 이 알고리즘이 쓰이게 된 이유는 속도 때문이다. 완전탐색으로 정답을 찾게 되면 속도가 느리게 되니 DP 알고리즘을 사용하게 됐다. 하지만 DP프로그래밍도 항상 최적해를 보장하기 위해서 모든 경우의 수를 고려한다. 그러다보니 속도가 느려지게 된다. 그래서 항상 최적해를 찾는 그리디를 사용해 좀더 빠르게 문제를 풀 수 있게 되었다. 현실에서는 최적해..

https://www.acmicpc.net/problem/1500 1500번: 최대 곱 세준이는 정수 S와 K가 주어졌을 때, 합이 S인 K개의 양의 정수를 찾으려고 한다. 만약 여러개일 경우 그 곱을 가능한 최대로 하려고 한다. 가능한 최대의 곱을 출력한다. 만약 S=10, K=3이면, 3,3,4는 www.acmicpc.net 수학 문제 알고리즘이다. 정수 S가 주어졌을 때 갯수가 K개이고 합이 S인 양의 정수를 구해야 한다. 중요 로직을 말하자면 먼저 1의 갯수가 적어야 곱이 최대로 크므로 중간값을 많이 구해야 한다고 생각했다. 중요 로직 코드를 설명하겠다. while (true){ if(s

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net N구역에서 M구역으로 다리를 건설한다. (N

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 전형적인 bfs 문제이다. Queue를 사용해서 풀었다. ​ 먼저 초기화 작업이다. 문제에 나와있듯이 각 케이스마다 m, n, k를 구해야 한다. StringTokenizer를 사용해 변수에 값을 넣었다. t = new StringTokenizer(br.readLine()); int m = Integer.parseInt(st.nextToken()); int n = Integer.parseInt(st.nextT..

https://www.acmicpc.net/problem/1059 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net 구간을 찾는 문제이다. 정수 집합 S가 있고, 주어진 숫자가 포함된 구간을 좋은 구간이라고 한다. A n) { if(numbers[i] < end) end = numbers[i]; }else if(numbers[i] < n) { if(start < numbers[i]) start = numbers[i]; } else if(numbers[i] == n){ // 만약 갖고 있다면 break; System.out.println("0"); System.exit(0); } } 아래는 전체 코드이다. import ja..