전체 글
-
[Java]SetAlgorithm/자료구조 for Algorithm 2022. 3. 22. 00:52
Set Set은 내부 데이터를 중복해서 저장할 수 없고, 저장된 객체에 순서가 없다. 따라서 Set은 List와 같이 인덱스를 사용하여 원소에 바로 접근할 수 없다. HashSet Java는 내부적으로 Set 인터페이스를 따로 정의해 두었다. 이곳에 다양한 Set 구현체를 활용하여 코드를 작성할 수 있는데, HashSet은 기본적인 Set의 특성을 그대로 반영한 클래스이다. Set set = new HashSet(); set.add(5); set.add(5); set.add(1); set.add(1); set.add(3); System.out.println(set); 다음과 같이 중복된 자료를 저장하더라도 중복되지 않게 저장되는 것을 확인할 수 있다. TreeSet Set은 TreeSet을 사용하여 내부..
-
[Java]우선순위큐(PriorityQueue)Algorithm/자료구조 for Algorithm 2022. 3. 22. 00:16
우선순위큐(PriorityQueue) 스택은 후입선출, 큐는 선입선출을 특징을 가졌다. 이와 달리 우선순위큐는 사용자가 지정한 우선순위에 의거하여 원소를 꺼내는 특징이 있다. 기본적인 사용 Java에서는 PrioryQueue 클래스를 이미 내부적으로 포함하고 있다. 이는 기본적으로 오름차순으로 수를 꺼낼 수 있도록 구현되어 있다. PriorityQueue pq = new PriorityQueue(); pq.offer(5); pq.offer(3); pq.offer(9); pq.offer(1); while(!pq.isEmpty()) { System.out.println(pq.poll()); } 정렬기준 정하기(사용자 정의) PriorityQueue의 생성하는 단계에서 Comparator 인터페이스를 재정의한..
-
[Java] 문자열 문제풀이시 자주 사용되는 내용들Algorithm/문자열 2022. 3. 21. 22:23
String ↔ Integer // String -> Integer int num = Integer.parseInt(string); // Integer -> String String string = Integer.toString(num); // Byte, Long, Float, Double 모두 동일한 함수를 가지고 있다. String ↔ Character /*** * String -> Character */ String sentence = "15151515"; // 한 글자 변환 char c = sentence.charAt(0); // 전체 글자 변환 char[] c_arr = sentence.toCharArray(); /*** * Character -> String */ // 한 글자 변환 Strin..
-
[Java]최장 공통 부분 수열(LCS, Longest Common Subsequence)Algorithm/동적 계획법 2021. 7. 11. 18:49
*최장 공통 부분 수열(LCS, Longest Common Subsequence) ->최장 공통 부분 수열이란, 주어진 두 수열이 주어졌을 때 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 말한다. ->LCS를 구하는 문제는 역시 백준 Gold5 9251 LCS 문제를 기반으로 알고리즘을 설명하도록 하겠다. ※ 문제 주소 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net ->해당 테스트 ..
-
[Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence)Algorithm/동적 계획법 2021. 7. 11. 17:19
*최장 증가 부분 수열(LIS, Longest Increasing Subsequence) ->최장 증가 부분 수열이란, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제이다. 여기서 부분 수열은 연속적이거나, 유일할 필요는 없다. ->아래 그림을 참고하여 이해하도록 하자. 해당 예시로 주어진 배열에서는 가장 긴 증가하는 부분 수열(이하 LIS)은 1, 2, 3, 7임을 직관적으로 알 수 있다. ->LIS를 구하는 문제는 Knapsack, LCS와 더불어 다이나믹 프로그래밍의 기초를 다지는데 자주 사용되는 예제 중 하나이다. 이 문제 역시 백준 Silver2 11053 가장 긴 증가하는 부분 수열 문제를 기반으로 알고리즘을 설명하도록 하겠다. ※ 문제 주소 : https://www.acm..
-
[Java]배낭 문제(Knapsack Problem)Algorithm/동적 계획법 2021. 7. 11. 02:32
*배낭 문제(Knapsack Problem) ->배낭 문제는 조합 최적화의 유명한 문제로, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있는 경우, '일정 가치'와 '무게'가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되로록 짐을 고르는 방법을 찾는 문제이다. ※ 조합 최적화란 쉽게 말해 모든 조합의 경우의 수를 고려하지 않고, 최적화하여 조합의 경우의 수를 줄이는 것을 말한다. ->배낭 문제는 두 가지로 나눌 수 있다. (1) 분할가능 배낭문제(Fractional Knapsack Problem) ->짐을 쪼갤 수 있다는 가정을 둔다. 예를 들어, 물건이 4kg이고 가치가 8이라면 물건을 2kg으로 나눠 가치가 4인 경우로 분할 해 배낭에 담을 수 있다고 생각하면 된다. ->해당 문제는 그리디 알고..
-
[Java]동적 계획법(Dynamic Programming)Algorithm/동적 계획법 2021. 7. 10. 22:37
*동적 계획법(Dynamic Programming) ->동적 계획법이란 특정 범위까지의 최적해(상위 문제)를 구하기 위하여 다른 범위까지의 최적해(하위 문제)를 이용하여 효율적으로 해를 구하는 알고리즘 설계 기법이다. ->쉽게 말해, 이전에 구한 값을 기반으로 규칙성을 파악하여 다음 값을 구하는 것이라고 생각하면 된다. ->알고리즘 설계 기법(패러다임) 중 하나이다. 하위 문제의 최적해를 적절히 사용하여 상위 문제를 해결함으로써, 불필요한 계산을 줄일 수 있다. ※ 어떤 문제를 해결할 때, 기본적인 방법은 모든 경우의 수를 고려하는 것(완전 탐색)이다. 어떤 문제를 해결할 때, 그 문제에 대한 모든 경우의 수를 고려할 수 있는 설계가 가능하다면, 그 문제는 시간과 자원이 매우 많이 들지는 몰라도 언젠가 ..
-
[Java]삽입 정렬(Insertion Sort)Algorithm/정렬 2021. 6. 25. 01:38
*삽입 정렬(Insertion Sort) ->삽입 정렬이란 2번째 원소부터 n번째 원소까지 차례로 해당 원소가 위치할 인덱스에 원소를 삽입하는 방식을 사용하는 정렬 방식이다. ->2번째 원소부터 n번째 원소부터 차례로 각 원소가 맞는 위치에 '삽입'하는 방식을 사용하며 배열을 정렬하기 때문에 삽입 정렬이라고 이름지었다. ※사람에게 어떤 대상을 정렬하라고 한다면 무의식적으로 수행하는 정렬 방식이라고 한다! *삽입 정렬의 이해 ->어떤 대상을 '오름차순'으로 정렬할 때 삽입 정렬은 2번째 원소부터 앞의 원소와 비교하는 과정을 통해 적절한 위치에 삽입하고, n번째 원소까지 이 방식을 반복함으로써 정렬을 진행할 수 있다. 예를 들어 [6, 2, 3, 4, 1]이라는 배열을 삽입 정렬을 이용하여 오름차순 정렬을 ..
-
[Java]선택 정렬(Selection Sort)Algorithm/정렬 2021. 6. 25. 00:44
*선택 정렬(Selection Sort) ->선택 정렬이란 한 번의 배열 탐색에서 가장 작은 원소의 '위치'를 찾고, 그 위치와 배열의 가장 첫 번째 원소부터 차례로 바꿔주는 방식을 사용(오름 차순으로 정렬하는 경우)하는 정렬 방식이다. ※가장 큰 원소의 위치를 찾고, 배열의 가장 마지막 원소부터 차례로 바꿔주는 방식을 사용해도 된다. 다만 반복문을 구현할 때 작은 원소의 값을 찾는 방식이 조금 더 구현하기 편하기 때문에 작은 원소를 찾는 방법을 주로 사용한다. ->말 그대로 큰 원소나 작은 원소를 선택하고 그 위치를 바꿔주기 때문에 선택 정렬이라는 이름을 사용한다. *선택 정렬의 이해 ->어떤 대상을 '오름차순'으로 정렬할 때 선택 정렬은 원소를 처음부터 탐색하면서, 작은 수를 찾고 그 수를 배열의 앞..
-
[Java]버블 정렬(Bubble Sort)Algorithm/정렬 2021. 6. 25. 00:08
*버블 정렬(Bubble Sort) ->버블 정렬이란 인접한 두 원소를 비교하며, 큰 수를 계속하여 뒤로 보내 정렬하는 방식을 사용(오름 차순으로 정렬하는 경우)하는 정렬 방식이다. ->원소들이 거품이 올라오는 것처럼 보여 거품 정렬(Bubble Sort)이라고 이름지었다. *버블 정렬의 이해 ->어떤 대상을 '오름차순'으로 정렬할 때 버블 정렬은 원소를 처음부터 탐색하면서, 큰 수를 계속하여 뒤로 밀어내는 방식을 사용한다. 예를 들어 [5, 3, 1, 10, 7]이라는 배열을 버블 정렬을 이용하여 오름차순 정렬을 해보면 다음과 같다. 먼저, Array[0]와 Array[1]을 비교해보자. Array[0]가 Array[1]보다 크기 때문에, 이 두 배열의 원소의 위치를 바꾸어준다. 다음으로 Array[1..