Problem Solving
[백준] 1976번 여행 가자(feat. 유니온 파인드)
[백준] 1976번 여행 가자(feat. 유니온 파인드)
2023.03.26https://www.acmicpc.net/problem/1976 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) N개의 도시가 있다. 임의의 두 도시 사이에 길이 있을 수도 있고, 없을 수도 있다. 여행일정이 주어졌을 때, 이 여행 경로가 가능한 것이지 알아보자. 중간에 다른 도시를 경우해도 OK ex) 도시가 5개 있고, A-B B-C A-D B-D E-A 의길이 잇고, 여행계획이 ECBCD 라면 E-A-B-C-B-C-B-D 라는 여행경로를 통해 목적 달성 OK 도시들의 개수와 도시간의 연결 여부가 주어져있고, 여행계획이 순서대로 주어져있을 때, 여행이 가능한지 판별하는 프로그램 작성 할 것.(같은 도시를 여러 번 방문 OK) - 입력 첫 줄에 도시의 수 N (N
[백준] 1717번 집합의 표현(feat. 유니온 파인드)
[백준] 1717번 집합의 표현(feat. 유니온 파인드)
2023.03.26https://www.acmicpc.net/problem/1717 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악) 초기화 n + 1개의 집합 {0}, {1}, ..., {n}이 있다. 이 집합에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성할 것. - 입력 조건 첫째 줄에 n, m이 주어진다. 이때 n은 0~n까지의 초기 집합이 주어짐을 의미. m은 입력으로 주어지는 연산의 개수임. 합집합은 0 a b 의 형태로 주어지고, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어짐 - 출력 조건 1로 시작하는 입력에 대해서는 a와 b가 같은 집합에 포함되면 "YES" 또는 "yes" 그렇지 ..
[백준] 2565번 전깃줄(feat. 다이나믹 프로그래밍, LIS)
[백준] 2565번 전깃줄(feat. 다이나믹 프로그래밍, LIS)
2023.02.04https://www.acmicpc.net/problem/2565 문제 접근 첫 번째 단계(문제 요약 및 조건 파악 하기) 입력으로 첫번쨰 줄에 n이 주어지고, 두번째 줄부터 n + 1 번째 줄 까지 각각 A to B가 주어진다. (전깃줄의 연결 정보) 이 그림에 대한 입력은 아래와 같다. 8 1 8 3 9 2 2 4 1 6 4 10 10 9 7 7 6 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구해야 한다. 두 번째 단계(문제 핵심 파악 하기) 모든 전깃줄을 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력해야 한다. 전깃줄이 서로 교차하지 않기 위해서는, 1번에서 출발한 전깃줄의 도착지점은 그 이후의 번호에서 출발한 전깃줄의 도착지점들보다 낮은 ..
[백준] 17216번 가장 큰 감소 부분 수열(feat. 다이나믹 프로그래밍, LDS)
[백준] 17216번 가장 큰 감소 부분 수열(feat. 다이나믹 프로그래밍, LDS)
2023.02.02https://www.acmicpc.net/problem/17216 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악) 가장 큰 감소 부분 수열의 요소 합을 구하는 문제이다. 예를 들어 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 인 경우에 가장 합이 큰 감소 부분 수열은 A = {100, 60, 8, 7, 6, 5} 이다. 입력으로는 수열의 크기 N (1
[백준] 11054번 가장 긴 바이토닉 부분 수열(feat. 다이나믹 프로그래밍, LIS, LDS)
[백준] 11054번 가장 긴 바이토닉 부분 수열(feat. 다이나믹 프로그래밍, LIS, LDS)
2023.02.02https://www.acmicpc.net/problem/11054 첫 번째 단계(문제 요약 및 조건 파악하기) 문제에서 말하는 바이토닉 수열에 대해서 간단하게 정리하면, 어떤 특정 수 X를 기준으로 왼쪽은 X보다 작은 LIS, 오른쪽은 X보다 작은 LDS 인 수열이다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 입력 조건으로는, 수열의 크기 N은 1 arr[j] and dp_left[i] < dp_left[j]: dp_left[i] = dp_left[j] dp_left[i] = dp_..
[백준] 11053번 가장 긴 증가하는 부분 수열(feat. 다이나믹 프로그래밍, LIS)
[백준] 11053번 가장 긴 증가하는 부분 수열(feat. 다이나믹 프로그래밍, LIS)
2023.02.01https://www.acmicpc.net/problem/11053 문제 접근 첫 번째 단계(문제 요약 및 조건 파악) 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하는 문제이다. 입력 조건은 수열의 크기 N은 1 arr[j] and dp[i] < dp[j]: dp[i] = dp[j] dp[i] = dp[i] + 1 print(max(dp)) DP문제는 DP테이블을 어떻게 정의하느냐가 관건.