✔ 선분 교차 2 [백준 17387] 문제 분석하기 CCW의 특징을 이용하여 두 선분과 관련된 교차 여부를 구하도록 함 두 선분을 A-B, C-D라고 명명했을 때, A-B 선분을 기준으로 점 C와 D를 CCW한 값의 곱과 C-D 선분을 기준으로 점 A와 B를 CCW한 값의 곱이 모두 음수이면 두 선분은 교차 만약 선분이 겹칠 때의 CCW의 결괏값은 모두 0이므로 이때는 각 선분의 min max x, y 값으로 겹침 여부를 판단 (한 선분의 min 값이 다른 선분의 max 값보다 클 때 선분이 겹치지 않음) 손으로 풀어보기 두 선분과 관련된 CCW값의 곱을 구함 결과에 따른 선분 교차 여부를 확인 슈도코드 작성하기 x1, y1, x2, y2, x3, y3, x4, y4 (네 점의 x, y 좌표값을 저장하는..
✔ CCW [백준 11758] 문제 분석하기 전형적인 CCW 문제 손으로 풀어보기 P₁, P₂, P₃ 3개의 점을 입력받아 변수에 저장하고, CCW를 계산 CCW 결괏값에 따라 정답을 출력 슈도코드 작성하기 x1, y1, x2, y2, x3, y3 (세 점의 x, y 좌표값을 저장하는 변수) 세 점의 정보를 x1, y1, x2, y2, x3, y3에 입력받기 CCW 수행 결과가 양수이면 1, 음수이면 -1, 0이면 0을 출력하기 코드 구현하기 /** * 11758) CCW */ public class D097_11758 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new..
✔ 가장 긴 증가하는 부분 수열 5 [백준 14003] 문제 분석하기 0 ~ i까지 i를 포함하는 최장 증가 수열의 길이를 구하도록 하여 동적 계획법으로 문제에 접근 손으로 풀어보기 점화식의 형태와 의미를 도출 D[i]는 0 ~ i까지 i를 포함하는 가장 길게 증가하는 수열의 길이 점화식을 구함 A[i]가 i번째 수열의 값일 때 D[k]는 A[i] > A[k]를 만족하는 최대 길이의 집합이므로 A[i]보다 작은 값을 지니고 있는 수열의 최장 증가 수열의 길이들 중 최댓값을 찾아 해당 값에 + 1을 한 값을 D[i]에 저장 D[i] = max({D[k]}) + 1 (k = 1 ~ i - 1) 이때 자신보다 작은 값을 지니고 있는 최장 증가 수열 길이를 찾기 위해 B 배열을 만들어 현재 가장 유리한 수열을 ..
✔ 외판원 순회 [백준 2098] 문제 분석하기 모든 순서를 완전 탐색을 수행 만약 D[i][j]에서 j가 나타내는 것이 현재까지 방문한 모든 도시 리스트라고 할 때, 리스트 데이터를 변수 1개로 저장하기 위해 방문 도시를 이진수로 표현 예) 4번, 1번 방문 현재 도시가 i이고, 4, 1 도시를 방문한 상태에서 나머지 모든 도시를 경유하는데 필요한 비용을 이진수로 표현 : 1001 → D[i][9] 손으로 풀어보기 점화식의 형태와 의미를 도출 D[c][v]는 현재 도시가 c, 현재까지 방문한 모든 도시 리스트가 v일 때 앞으로 남은 모든 도시를 경유하는데 필요한 최소 비용 점화식을 구함 c번 도시에서 v 리스트 도시를 방문한 후 남은 모든 도시를 순회하기 위한 최소 비용은 현재 방문하지 않은 모든 도시..
✔ 행렬 곱셈 순서 [백준 11049] 문제 분석하기 행렬의 개수 N이 주어지고, 1 ~ N개를 모두 곱햇을 때 최소 연산 횟수를 구해야하므로 만약 1 ~ N - 1, 2 ~ N, 3 ~ N - 2 등 N을 제외한 모든 부분 구역을 1개의 행렬로 만드는데 필요한 최소 연산 횟수를 알 수 있다면 이를 바탕으로 1 ~ N 구역의 최소 연산 횟수를 구할 수 있음 손으로 풀어보기 점화식의 형태와 의미를 도출 D[i][j]는 i ~ j 구간의 행렬을 합치는데 드는 최소 연산 횟수 점화식을 구함 행렬 구간에 행렬이 1개일 때 0을 리턴 행렬 구간에 행렬이 2개일 때 '앞 행렬의 row 값 * 뒤 행렬의 row 값 * 뒤 행렬의 column값'을 리턴 행렬 구간에 행렬이 3개 이상일 때는 Math.min(min, D..
✔ Dance Dance Revolution [백준 2342] 문제 분석하기 한 발만 움직여 N개의 수열을 수행할 때 D[N][L][R]의 위치를 만들 수 있는 모든 경우의 수를 비교해 최솟값을 위치에 저장하는 방식으로 문제에 접근 손으로 풀어보기 점화식의 형태와 의미를 도출 D[N][L][R]은 N개의 수열을 수행한 후 왼발의 위치가 L, 오른발의 위치가 R일 때 최소 누적 합 점화식을 구함 mp[i][j]가 i에서 j로 이동하는데 드는 힘일 때 바로 직전에 오른발을 움직일 때 D[N][L][R] = MIN(D[N - 1][L][i] + mp[i][R]) 바로 직전에 왼발을 움직일 때 D[N][L][R] = MIN(D[N - 1][i][R] + mp[i][L]) 왼발과 오른발을 구분해 두 발로 만들 수..
✔ 고층 빌딩 [백준 1328] 문제 분석하기 가장 큰 빌딩을 마지막에 배치하면 중간 위치에 배치할 경우가 복잡하므로 반대로 가장 작은 빌딩을 N번째 배치하여 문제에 접근 1) 가장 작은 빌딩을 왼쪽 위치에 배치한 경우 : 왼쪽에서 보는 빌딩의 수 1 증가 2) 가장 작은 빌딩을 오른쪽 위치에 배치한 경우 : 오른쪽에서 보는 빌딩의 수 1 증가 3) 가장 작은 빌딩을 가운데 위치에 배치한 경우 : 양쪽에서 보는 빌딩의 수가 증가하지 않음 손으로 풀어보기 점화식의 형태와 의미를 도출 D[N][L][R]은 N개의 빌딩이 있고 왼쪽에서 L개, 오른쪽에서 R개가 보일 때 가능한 경우의 수 점화식을 구함 N - 1개의 빌딩에서 왼쪽에 빌딩을 추가할 때는 왼쪽 빌딩이 1개 증가하므로 이전 경우의 수는 D[N - 1..
✔ 가장 큰 정사각형 [백준 1915] 문제 분석하기 가장 큰 정사각형의 넓이를 구하는 것을 가장 큰 정사각형의 한 변의 길이를 구한다는 것과 동일하므로 이를 통해 문제에 접근 손으로 풀어보기 점화식의 형태와 의미를 도출 D[i][j]는 i, j의 위치를 오른쪽 아래 꼭짓점으로 정하고, 해당 자리에서 그릴 수 있는 가장 큰 정사각형의 변의 길이 점화식을 구함 현재 자리의 원래 값이 1일 때는 위, 왼쪽, 대각선 왼쪽 위의 값 중 가장 작은 값에 1을 더한 값으로 변경 D[i][j] = MIN(D[i - 1][j - 1], D[i][j - 1], D[i - 1][j]) + 1 원래 값이 0일 경우 그대로 둠 D[i][j] = 0 점화식으로 D 배열을 채운 후 D 배열 중 가장 큰 값의 제곱을 출력 슈도코드..
