[자바] 투 포인터(Two Pointers) 알고리즘
2022. 7. 12. 21:04
자바
Two Pointers 배열에서 두 개의 포인터를 갖고 원하는 결과를 얻는 알고리즘을 일컫는다. 각 포인터의 배치방법은 두 가지가 있다. 두 포인터 모두 배열의 첫 번째 원소에 배치 각각 첫 원소와 마지막 원소에 배치 투 포인터를 사용하지 않고 단순 이중 for문으로 문제를 해결한다면, 시간복잡도에서 효율성이 다소 떨어질 수 있다. 예를 들어 위 배열에서 합이 7을 이루는 부분배열을 찾고자 한다면, i를 index 0에 두고 j를 index 1부터 배열의 끝까지 가면서 찾으면된다. j가 끝까지 도달했다면 i를 index 1로 한칸옮기고 j는 다시 index 2부터 배열의 끝까지 간다. 코드로 간단히 나타내면 이렇다. public static int[] forExample(int[] arr, int tar..
[백준] 1260번 DFS와 BFS 문제풀이 (JAVA)
2022. 7. 7. 23:18
알고리즘
문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. ..
[자바] 배열의 오름차순과 내림차순 정렬
2022. 7. 6. 16:37
자바
배열을 오름차순, 내림차순으로 정렬하는 방법을 알아보겠다. 간단하다. 두 경우 모두 비슷한 함수로 구현이 된다. 오름차순 public static void main(String[] args) { int[] arr1 = {5, 4, 3, 2, 1}; Arrays.sort(arr1); System.out.println(Arrays.toString(arr1)); // [1, 2, 3, 4, 5] } Arrays.sort로 간단히 나타낼 수 있다. String[] 타입도 동일하다. 내림차순 public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5}; String[] str = {"a","b","c","d","e"}; Integer[] intArr ..
[자바] 계수정렬(Counting sort) 개념과 구현
2022. 7. 6. 12:47
자바
계수정렬 Counting sort 계수정렬 별도의 메모리공간을 만들어서 각 원소값 만큼의 index에 해당 원소의 갯수를 채운 뒤 기존 배열의 값을 재설정하는 방식이다. 예를들어, 특정 값이 10만이라고 하면 해당 원소는 index 100,000에 채워지므로 메모리공간의 최대 길이는 10만까지 늘어나서 비효율적이다. 하지만 최대값의 크기가 적당하다면 효율적으로 사용할 수 있겠다. 시간복잡도는 O(n + k)이다. 여기서 k는 위에서 말한 최대 원소값을 뜻한다. 하지만 메모리공간을 HashMap으로 할당함으로써 워스트케이스에 어느정도 대처할 수 있다. 정렬방식 이와같이 별도의 메모리공간을 만들고, 각 원소 크기에 해당하는 index를 찾아 해당 원소 갯수만큼 채워넣는다. 모든 값을 채워넣었다면 최종적으로 ..
[자바] 기수정렬 (Radix sort) 개념과 구현
2022. 7. 6. 10:59
자바
기수정렬 Radix sort 기수정렬 정렬 방식 중 하나이다. 각 원소간 크기를 비교하지 않아서 빠른 시간복잡도를 가지고 있으며, 대신 별도의 메모리 공간이 필요하다. 시간복잡도는 O(dn)이다. 여기서 d는 모든 원소 중 가장 높은 자릿수를 의미한다. 예를들어 가장 높은 자릿수가 10만인 워스트케이스를 생각해보면 이 때 시간복잡도는 100000 x n이 되는것이다. 정렬방식 Step 1 1. 별도의 List 혹은 Queue를 만든다. 2. 배열의 각 원소를 List 또는 Queue에 넣는데, 이 때 각 원소의 1의자리 숫자에 해당하는 index를 찾아 배열 순서대로 넣는다. 3. 2번에서 별도의 테이블에 담은 원소들을 다시 초기 배열에 순서대로 넣는다. Step 2 Step 1과 동일하며, 봐야할 자릿..
[자바] Math 클래스의 여러가지 메서드를 알아보자. (ceil & floor & round & pow & sqrt & abs)
2022. 7. 1. 15:02
자바
Math Math 클래스가 기본적으로 max와 min 메서드를 갖는다는 것은 대부분 알것이다. 그 외에도 Math 클래스는 수많은 메서드를 갖고있다. 그 중 몇가지를 예시와 함께 소개하겠다. ceil & floor & round public class Note { public static void main(String[] args) { double num = 21.476; System.out.println(Math.ceil(num)); // 올림 System.out.println(Math.floor(num)); // 버림 System.out.println(Math.round(num)); // 반올림 } } 출력 22.0 21.0 21 세 함수 모두 소수점 첫째자리에 대해서 적용되며, ceil은 올림 / ..
[자바] equals와 equalsIgnoreCase, contentEquals 개념과 예시
2022. 6. 28. 17:40
자바
equals() & equalsIgnoreCase() equals() / equalsIgnoreCase() 우리는 숫자형을 비교할 때 == 을 사용해서 비교한다. 단, String 타입은 equals() 혹은 equalsIgnoreCase()를 사용하여 비교해 true 혹은 false를 반환한다. 그리고 equals()는 대소문자를 구별해서 비교하며, equalsIgnoreCase()는 대소문자를 구별하지 않고 비교한다. 추가로, equals()는 Object 타입도 비교가 가능하지만 equalsIgnoreCase()는 오로지 String 끼리만 비교할 수 있다. (대소문자의 개념은 String에만 있기 때문!) 사용법은 예시에서 간단하게 나타내보겠다. class test { public static v..
[자바] 공백 제거하기 (trim & replaceAll)
2022. 6. 26. 23:03
자바
trim String클래스에 포함된 공백 제거 메서드이다. 문자열.trim() 으로 사용하며, 문자열 앞과 뒤의 공백을 없애준다. 바로 예시코드를 보여주겠다. public class Test { public static void main(String[] args) { String str = " Hello java!! "; System.out.println(str.trim()); } } 출력 Hello java!! 문자열에서 가운데 공백은 제거가 안되고 양 끝의 공백만 제거되었다. 만약 문자열 양 끝에 공백이 없다면 해당 문자열을 그대로 출력한다. 문자열 사이의 공백까지 제거하고 싶다면? replaceAll를 사용해보자. public class Test { public static void main(Str..