전체 글

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 문제 풀이 쉽게 풀 수 있을줄 알았다 .. 최단 경로 찾아서 없애주고 , 처음 구한 최단경로보다 높은 값 나올때까지 다익스트라 다시 쓰면 되는줄 ..하지만 실패하고 반례를 살펴보니 다른 조건이 추가되어야 했다. 예를들어 , 0에서 출발하여 2로 도착하는 예시에서 최단 경로가 될 수 있는 경우의 수는 2가지이다. (0->3->2 , 0->3->1->2) 만약 0->3-..

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 문제 풀이 특정 노드 i 번째로 갔다고 가정을하자. 그럼 두 가지의 경우가 나뉘는데 , (얼리아답터를 EA) 1. i번째가 EA 일 경우 => i의 자식은 EA 이거나 아니다. 2. i번째가 EA 아닐 경우 => i의 자식은 반드시 EA 여야함. 문제는 EA의 최소값을 구하는것이 목표이므로 , EA의 최솟값을 나타내는 메모배열을 DP[노드의수][EA] 로 나타낼 ..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 풀이 두 문자열(arr1,arr2) 을 문자 하나하나 비교하는것에서 시작을 해야한다. ( arr1 를 i 로 순차탐색 ) ( arr2 를 j 로 순차탐색) 차례대로 (i, j)비교하다가 만약 문자 하나가 같은경우 => arr1[i] == arr2[j] 일 경우 카운트를 증가시킨다. 이것을 끝날때 까지 진행하면 된다. 하지만 이대로하면 중복되는부..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net [문제] [풀이] 위와 같이 task 를 수행하는 순서가 있는 경우엔 위상정렬로 접근해야 한다. 이 문제에선 건물을 짓는데 있어서 선행조건이 존재하므로 위상정렬을 이용하여 inDegree 를 하나씩 낮춰가면서 진행. A,B 라는 건물을 지어야만 C를 지을수 있을 때 A와 B 건물중에서 더 오래걸리는 건물 기준으로 C까지 짓는데 걸리는 시간이 정해진다. 건물 n을 짓는데 걸리는 시간을 time..

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 이전에 포스팅했던 LIS 알고리즘에 + 추척 까지 해줘야 하는 문제이다. (이전 포스팅 참고 : https://katastrophe.tistory.com/39?category=956141 ) 1. DP 풀이 최종적으로 나온 부분 수열의 길이 값을 ans 라고 하면 각 구간마다 길이를 저장해놓은 DP배열의 ..

https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 문제 풀이 전깃줄이 서로 꼬여야 하지 않아야 하므로 가령 , 4 -> 1 번 전봇대로 가는 선을 제거해야 꼬이지 않는다. 즉 , 반대쪽의 전봇대의 번호가 증가하는 수열의 형태면 꼬이지 않으므로 LIS 알고리즘을 통해 해결해야한다. LIS에 대한 이전 포스팅에서 해결방법이 3가지가 있다고 했는데 , 문제에서 조건을보면 N의 갯수가 10만개가 넘어간다. N^2 이상의 시간복잡도를 가지는..

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 문제 풀이 LIS(LDS) 풀이는 3가지다. 1. 완전탐색으로 푸는경우 => 시간복잡도 O(n^3) 2. DP => O(N^2) 3. 이진탐색 => O(nlongn) 완전탐색인 경우 for문을 이용한 단순 반복이므로 생략 DP로 접근 할 경우 , 부분 중복 되는부분을 찾아 최적화 시켜야한다. 2중 for문( 바깥쪽 i , ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 풀이 KnapSack 이라는 굉장히 유명한 다이나믹 프로그래밍 유형의 문제이다. 그리디 접근이 왜 안되는가 .. ? 가방에 넣는 순서를 무게순 혹은 가치순이라고 가정을 해보면 1. 무게순으로 일단 넣어서 무게합이 11이 되고, 가치합이 12가 되었다. 그런데 바로 뒤에 무게11짜리 가치 100짜리가 있는 경우가 생겨버렸다. =..