분류 전체보기
-
1485 정사각형백준/기하학 2022. 6. 9. 21:08
1. 풀이 정사각형을 만들 수 있는지 구하라고 해서, 이런 경우만 생각했다. 하지만, 이런 경우도 정사각형이다. 회전 된 상태라고 생각하면 된다. 그래서 정사각형을 구할 때, 1) 네 변의 길이가 같은지 2) 대각선의 길이가 같은지 두 가지 경우를 확인해주면 된다. 즉, 네 변의 길이가 모두 같고, 2개의 대각선이 길이가 같다면 정사각형이다. 2. 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; class Posit..
-
13334 철로백준/스위핑 2022. 6. 6. 21:49
1. 풀이 다른 블로그를 참고해서 풀었다. 여기에는 스위핑 알고리즘이 사용되는데, 스위핑 알고리즘은 특정한 자료구조나 구체적인 코드가 있는 것이 아니라 한 쪽 방향에서 시작해서 다른 방향으로 해결해 나가는 기법이다. 문제 풀이를 보면 이해가 갈 것이다. 그러면 예제를 가지고 설명하겠다. 8 5 40 35 25 10 20 10 25 30 50 50 60 30 25 80 100 30 (5,40) 부터 (80,100) 까지 첫번째 값은 집, 두번째 값은 사무실의 위치를 나타낸다. 하지만 집이 사무실보다 앞에 위치하던지, 뒤에 위치하던지 중요하지 않다. 그저 집과 사무실 거리가 선분 L 보다 작은지가 중요하다. 그러면 집과 사무실이 모두 L 에 포함되기 때문이다. 그래서 리스트에 (5,40) 이런식으로 값을 넣..
-
17845 수강 과목백준/배낭 문제 2022. 6. 5. 21:38
1. 풀이 배낭 문제 알고리즘을 사용하면 된다. 이에 대한 설명은 다음 글에 자세하게 설명해 놓았다. https://happy-fun.tistory.com/246 12865 평범한 배낭 1. 배낭 문제 알고리즘 배낭 문제 알고리즘을 이용해서 풀면 된다. 배낭 문제 : 배낭에 담을 수 있는 무게의 최댓값이 정해져 있을 때, 일정한 가치, 무게가 정해져 있는 짐들을 배낭에 담아야 한 happy-fun.tistory.com 2. 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public..
-
20444 색종이와 가위백준/이분탐색 2022. 6. 5. 00:36
1. 풀이 다른 블로그를 참고했다. 이분탐색으로 풀면 된다. 1) 예제 먼저 아래와 같은 경우를 생각해보자. 4 5 4 = n, 5 = k => 4번의 가위질로 5개 색종이 조각을 만들 수 있는지 확인해야 한다. 이분탐색 변수로 left, right, mid 를 사용한다. 처음에는 다음과 같다. left = 0 right = n mid = (left + right) / 2 여기서 mid는 색종이를 세로로 자른 횟수가 된다. 즉, 여기서는 left = 0, right = 4 이므로 mid = 2 가 된다. 즉 세로로 2번 자르고, 가로는 총 4번의 가위질에서 2번을 제외한, 2번 자르게 된다. 2) 색종이를 자른 후 총 개수 처음 아래와 같은 상태에서 세로로 1번 자르면 색종이가 2개가 된다. 이 상태에서..
-
12865 평범한 배낭백준/배낭 문제 2022. 6. 2. 23:10
1. 배낭 문제 알고리즘 배낭 문제 알고리즘을 이용해서 풀면 된다. 배낭 문제 : 배낭에 담을 수 있는 무게의 최댓값이 정해져 있을 때, 일정한 가치, 무게가 정해져 있는 짐들을 배낭에 담아야 한다. 이 때 가치의 합이 최대가 되도록 짐을 고르는 방법 두 가지로 분류 할 수 있는데, 1) 물건을 쪼갤 수 있는 배낭 문제 => 가치가 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는 방식 => 그리디 알고리즘 사용 2) 물건을 쪼갤 수 없는 배낭 문제 => dp를 활용해서 해결 2. 문제 풀이 이 예제는 물건을 쪼갤 수 없는 배낭 문제로 dp를 활용한다. 문제 예제를 가지고 설명하겠다. 4 7 6 13 4 8 3 6 5 12 물품의 수(N) : 4 배낭에 넣을 수 있는 최대 무게(K) : 7 item 배열의..
-
2143 두 배열의 합백준/누적 합 2022. 5. 31. 22:01
1. 풀이 다른 블로그를 참고해서 풀었다. 누적 합과 두 포인터를 이용한다. 예제를 가지고 설명하겠다. 5 4 1 3 1 2 3 1 3 2 1) 누적합 A 배열에 1 3 1 2 를 입력하고, B 배열에 1 3 2를 입력한다. 그 후 sumA 리스트에 A 배열의 누적 합을 넣어준다. A[0] A[0] + A[1] A[0] + A[1] + A[2] A[0] + A[1] + A[2] + A[3] A[1] A[1] + A[2] A[1] + A[2] + A[3] A[2] A[2] + A[3] A[3] 이런 식으로 누적 합을 sumA리스트에 넣어준다. 그 후 오름차순 정렬해준다. B 배열의 누적 합도 마찬가지로 만들어준다. => sumA : 1 1 2 3 3 4 4 5 6 7 sumB : 1 2 3 4 5 6 2)..
-
17265 나의 인생에는 수학과 함께백준/그래프 이론 2022. 5. 29. 17:35
1. 풀이 dfs를 이용해서 풀면된다. (1,1) 에서 시작해서, max 배열에는 연산 결과가 큰 값으로, min 배열에는 연산 결과가 작은 값으로 채우면 된다. 그 후 max[N][N] 과, min[N][N] 을 출력하면 정답이 된다. 아래 그림은 예제에서 일부분을 가져온 것이다. 5가 입력되어 있는 부분은 (1,1)의 위치이다. 이 때, (2,2) 위치에는 두가지 연산이 있다. 1) 오른쪽, 아래 이동 5+3 = 8 이 먼저 연산되었다고 하자. 그러면 max[2][2] = 8 이 된다. 2) 아래, 오른쪽 이동 그 이후에 아래, 오른쪽 이동으로 5 * 3 = 15 가 결과로 나왔다면 더 큰 값, 15로 바꿔주어 max[2][2] = 15 가 된다. 2. 최종 코드 import java.io.Buffe..
-
1561 놀이 공원백준/이분탐색 2022. 5. 28. 23:06
1. 풀이 다른 블로그를 참고했다. 예제 3을 가지고 설명하겠다. 22 5 1 2 3 4 5 1) 시간에 따른 놀이기구 이용 상황 아이들이 22명 있고, 놀이기구가 5개 있다. 시간에 따른 아이들의 놀이기구 이용 상황을 표로 나타내면 다음과 같다. 즉, 맨 처음 0분에는 5명의 아이들이 각 놀이기구에 탑승한다. 1분 뒤에는 1번 놀이기구를 이용할 수 있고, 2분 뒤에는 1번, 2번 놀이기구를 이용할 수 있다. 위에서 보면 아이들이 놀이기구를 모두 탑승했을 때의 시간이 8분이다. 이 시간을 이분탐색을 이용하여 찾아낼 것이다. 8이라는 숫자로 어떻게 정답, 즉 마지막 아이가 타게 되는 놀이기구 번호를 찾는지 살펴보자 일단 8분보다 1분 작은 7분동안 몇 명의 아이들이 놀이기구에 탑승하는지 살펴보자. 일단 0..