[JAVA] 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)
2023. 8. 20. 16:25
JAVA/알고리즘 개념 정리
LIS 란? Longest Increasing Subsequence ex) 수열 A = {10, 20, 10, 30, 20, 50}가 주어지고 가장 긴 증가하는 부분 수열을 구하는 문제 증가하는 부분 수열을 모두 구해보면 아래와 같음 {10}, {20}, {30}, {50} {10, 20}, {10, 30}, {20, 30}, {20, 50}, {30, 50} {10, 20, 30}, {10, 20, 50}, {10, 30, 50}, {20, 30, 50} {10, 20, 30, 50} 이 중 가장 길이가 긴 부분 수열은 {10, 20, 30, 50} 해결 방법 1 - O(n^2) 가장 쉬운 해결 방법은 일반적인 dp를 사용하는 방법 dp[i] = dp[i - 1]과 arr[i]를 포함시켜 만들 수 있는..
[JAVA] 백준 2162 - 선분 그룹
2022. 10. 26. 19:15
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 해결 방법 이 문제를 풀기 위해 두가지 알고리즘을 알아야 함 CCW를 사용해 두 선분이 겹치는지 판단 Union-Find를 통해 그룹을 합치고 확인하는 작업 진행 위 두 알고리즘을 알고 같이 사용한다면 쉽게 해결할 수 있음 입력받은 모든 선분들끼리 서로 겹치는지 판단 선분이 겹치는지는 CCW를 통해 판단 두 선분이 겹친다면 Union 과정 진행 위 작업이 끝..
[JAVA] Knapsack 알고리즘
2022. 10. 11. 16:51
JAVA/알고리즘 개념 정리
Knapsack 알고리즘 이란? Knapsack은 배낭이란 뜻으로, Knapsack 알고리즘은 배낭 알고리즘 이라고도 불림 Knapsack 알고리즘은 DP의 일종으로 배낭 채우기 문제에서 유래되었음 배낭 채우기 문제란 배낭의 크기 k와 n개의 물건 각각의 무게와 가치가 주어졌을 때, 배낭에 넣은 물건들의 최대 가치의 합을 구하는 문제 ex) 무게가 7까지 담을 수 있는 배낭이 있고, 5개의 물건의 무게와 가치가 아래와 같다고 생각해 보자 물건 1 : 무게 3, 가치 8 물건 2 : 무게 1, 가치 5 물건 3 : 무게 2, 가치 7 물건 4 : 무게 2, 가치 2 물건 5 : 무게 2, 가치 6 이 때, 가방에 넣을 수 있는 최대 가치를 구해보자 만약 1번 물건(3, 8)만 있었다고 가정해보면 DP 테이..
[JAVA] 백준 2166 - 다각형의 면적
2022. 10. 8. 19:19
JAVA/백준(BOJ) 문제풀이
CCW 설명 및 백준 2166번 문제 풀이 https://chb2005.tistory.com/87 [JAVA] CCW CCW 란? Counter-ClockWise의 줄임말로 평면상의 3개의 점의 위치관계를 판한다는 알고리즘 세 점 A(X1, Y1), B(X2, Y2), C(X3, Y3) 이 있다고 가정했을 때 CCW의 공식은 CCW = ( X1*Y2 + X2*Y3 + X3*Y1 ) - ( X2*.. chb2005.tistory.com
[JAVA] 백준 1541 - 잃어버린 괄호
2022. 10. 4. 23:58
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 해결 방법 5자리 이상의 수가 입력되지 않고, 식의 길이가 50이하이기 때문에 int 형으로 해결 가능 괄호를 사용해 최소값을 만들기 위해서는 빼주는 값을 최대로 만들어 주면 됨 ex) a + b + c - d + e + f - g - h 라고 가정해보자 ( a ~ h는 양의 정수 ) 이 결과를 최소로 만들어보면 a + b + c - (d + e + f) - g - h 가 됨 정리해보면..
[JAVA] Object 클래스
2022. 10. 4. 01:19
JAVA/기본 문법
Object 클래스란? Object 클래스는 모든 자바 클래스들의 최고 조상 클래스 따라서 모든 자바 클래스들은 Object 클래스의 모든 메소드들을 바로 사용할 수 있음 Object 클래스의 Method 사용 예제 1 아래 코드에서는 Object 클래스의 toString, getClass, eqauls 메소드를 사용해봄 getClass() : 해당 Object가 어떤 클래스인지 출력 toString() : 해당 Object를 String 타입으로 변환, Student 클래스를 String 타입으로 출력했을 때는 주소값이 출력됨 equals() : 해당 Object가 같은지 출력, student와 student2는 name, age가 같긴 하지만 주소값은 다르기 때문에 false 출력 public cla..
[JAVA] Generic, Wrapper Class
2022. 10. 4. 00:57
JAVA/기본 문법
Generic 이란? List, Map, Set 등을 선언할 때, List, List 와 같은 코드를 사용함 위와 같이 안에 Data Type을 지정해 줌 이 때, 안에 특정 Data Type을 미리 지정하지 않고 개발자의 필요에 의해 지정할 수 있도록 하는것이 Generic 한마디로 Generic은 Data Type을 일반화(generalize) 한다는 의미 우리가 같은 List를 List, List과 같이 Data Type만 달리해서 사용할 수 있는것도 List에서 Generic 문법이 사용되기 때문 JDK 1.5 버전 이후로 사용 가능 Wrapper Class 란? List같은 코드를 보면 왜 int가 아닌 Integer을 사용하는데, 이 때 Integer와 같은 것들을 Wrapper Class라 ..