Problem Solving 19

[백준/JAVA] 20926 - 얼음미로

문제 정보https://www.acmicpc.net/problem/20926 문제문제 해결과정문제 분석 및 시간복잡도 계산 1. 출발점 ~ 도착점까지의 최단시간을 구하는 '최단경로' 문제였다.2. 정점 사이의 (인접한 두 좌표간의) 가중치(미끌시간)이 달랐다. ⇒ BFS를 사용할 수 없다. (BFS는 가중치가 동일해야 함)3. 각 가중치는 0이상 9이하라고 주어졌으므로, 가중치가 양수였다. ⇒ '다익스트라'와 '플로이드워셜' 모두 사용 가능다익스트라 : '시작점 ~ 다른 모든 정점' 사이의 최단거리 구함. 시간복잡도는 O(E*logV)플로이드워셜 : '모든 정점 쌍' 사이의 최단거리 구함. 시간복잡도는 O(V^3)시간복잡도는 이전 블로그 포스팅을 참고4. 출발점과 도착점이 주어졌으므로, 시간복잡도가 더 ..

[백준/JAVA] 14501 - 퇴사

문제 정보https://www.acmicpc.net/problem/14501 문제  문제 해결 과정완전 탐색 풀이Ti와 Pi를 살펴보면, 상담기간이 길다고해서 상담금액이 큰 것이 아니었다. 즉, 상담기간과 상담금액은 랜덤하게 주어졌으므로, 그리디와 같은 방법으로는 접근할 수 없고 완전탐색이 필요한 문제이다. 각 날짜의 상담을 진행하거나 미진행할때의 모든 경우를 생각해보면, 가능한 경우의 수는 다음과 같다.1일(상담/미상담) x 2일(상담/미상담) x ... x n일(상담/미상담) = 2^n가지 문제에서 n이 최대 15라고 주어졌으므로, 시간복잡도는 O(2^15)이므로 주어진 시간 내에 풀 수 있다.하지만, 퇴사2와 같은 경우에는 n이 최대 1,500,000이므로 주어진 시간 내에 불가능하다.그렇다면, 랜..

[백준/JAVA] 2579 - 계단 오르기

문제 정보https://www.acmicpc.net/problem/2579 문제  문제 해결 과정완전 탐색 풀이매 번 계단을 한 칸(+1칸)  또는 두 칸(+2칸)을 오르는 경우, 가능한 경우의 수는 다음과 같다. 이동 1(+1칸/+2칸) x 이동 2(+1칸/+2칸) x ... x 이동 k(+1칸/+2칸) = 2^k가지 이때 계단의 개수가 최대 300개이므로, 이동은 최소 150번(+2칸으로만) 최대 300번(+1칸으로만) 일어나게 된다.따라서, 150 ≤ k ≤ 300이므로, 2^150  DP 풀이계단 4에 도착할 수 있는 경우를 주목해보았을 때, 다음과 같이 나뉘어 질 수 있다.계단 3에서 + 1칸계단 2에서 + 2칸연속하여 세 개의 계단을 밟을 수 없으므로, 불가능한 경우를 삭제(위에서 빨간색 x)..

[SWEA/JAVA] 8275 - 햄스터

문제 정보https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWxQ310aOlQDFAWL 문제 문제 해결 과정완전 탐색 풀이1) 각 우리별 햄스터 숫자 순열 생성각 우리별로 최소 0마리 최대 x마리의 햄스터를 배치할 수 있고, 이러한 우리가 n개가 있다고 하였다. 각 우리별로 햄스터 숫자를 배치하는 순열을 만들어 보면 경우의 수는 다음과 같다.1번 우리(0~x마리 → x개) * 2번 우리(0~x마리 → x개) * ... * n번 우리(0~x마리 → x개) = x^n가지 x는 최대 10이고 n은 최대 6이라고 하였으므로, 우리별로 햄스터 숫자를 배치하는 순열의 경우의 수는 10^6이 된다. (정확히는 0~x마리는 x+1..

[백준/JAVA] 12865 - 평범한 배낭

문제 정보https://www.acmicpc.net/problem/12865 문제 문제 해결 과정완전 탐색 풀이서로 다른 N개의 물품품으로 배낭을 채울 수 있는 경우의 수는 다음과 같다.물품 1(사용/미사용 → 2개) x 물품 2(사용/미사용 → 2개) x ... x 동전 N(사용/미사용 → 2개) = 2^N개 문제 조건에서 N이 최대 100이라고 하였으므로, 2^100 ≒ 10^30이므로, 문제 제한인 2초를 많이 초과한다. 따라서, 서로 다른 N개의 물품으로 배낭을 채울 수 있는 모든 경우의 수에 대해 이 무게가 K를 넘는지 확인하는 방식은 적합하지 않다. DP 풀이우선 그리디 풀이(가치 큰 것부터, 무게 작은 것부터, 단위무게당 가치 큰 것부터)를 생각했지만, 무게가 무겁다고해서 가치가 큰 것은 아..

[백준/JAVA] 2805 - 나무 자르기

문제 정보https://www.acmicpc.net/problem/2805 문제 문제 해결 과정완전 탐색 풀이절단기 높이를 최대 높이인 1,000,000,000부터 시작해서 0이될때까지 1씩 줄여보면서, 현재 절단기로 자른 나무 높이의 합이 필요 나무 길이 이상인지 확인하면 된다. 이 경우에 시간복잡도는 O(NH)이고 (N: 나무의 수, H: 절단기의 최대 높이), 문제 조건에서 N의 최대 10^6이고 H는 최대 10^9이므로, O(NH) = O(10^15)이므로 시간 제한인 1초를 초과하게 된다.따라서, 절단기 높이를 1씩 줄어가면서 자른 나무 높이의 합이 필요 나무 길이 이상인지 확인하는 방식은 적합하지 않다. 이분 탐색 풀이 이분 탐색을 위해서는 "데이터가 정렬이 되어있어야 한다"는 조건을 만족해야..

[백준/JAVA] 2293 - 동전 1

문제 정보https://www.acmicpc.net/problem/2293 문제 문제 해결 과정완전 탐색으로 풀이서로 다른 n가지 동전을 사용하는 경우의 수는 다음과 같다.동전 1(사용/미사용 → 2개) x 동전 2(사용/미사용 → 2개) x ... x 동전 n(사용/미사용 → 2개) = 2^n개 문제조건에서 n이 최대 100이라고 하였으므로, 2^100 ≒ 10^30이므로, 문제 제한인 1초를 많이 초과한다. (사실은 하나의 동전을 무한 번 사용 가능하므로, 실제로는 이보다 경우의 수가 많을 것이다.)따라서, 서로 다른 n가지 동전을 사용하는 모든 경우의 수에 대해 이 금액이 k원인지 확인하는 방식은 적합하지 않다. DP 풀이DP[ i ][ j ]를 1, 2, ... i번째까지 동전을 고려해서, j원을..

[백준/JAVA] 1863 - 스카이라인 쉬운거

문제 정보https://www.acmicpc.net/problem/1863 문제 문제 해결 과정1. 문제 조건의 x좌표 범위와 y좌표 범위1 ≤ 고도가 바뀌는 x좌표 ≤ 1,000,000.    0 ≤ 고도가 바뀌는 y좌표 ≤ 500,000만약 좌표를 byte 2차원 배열로 만들어 기록하게 된다면, 공간복잡도 = 1,000,000*500,000*1B = 500GB이므로, 메모리 제한인 128MB를 초과하게 된다. 따라서 2차원 배열로 저장하는 것은 불가능하다고 생각하였다.사실상 중요한 것은 x좌표가 아닌 높이인 y좌표 이므로, 이것만 저장하자고 생각하였다. 2. 아이디어같은 높이들끼리는 최대한 이어 건물을 만드는 것이 건물의 개수를 최소로 하기 위한 방법이라고 생각하였다.예를 들어, 1, 2, 1, 3,..