어흥

문제 링크: https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKaG6_6AGQDFARV SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 매 TC마다 초기화를 해야 한다 - Check[][] 배열을 최대값으로 초기화한다 - 결승 지점에 도착하지 못하면 -1을 출력한다 2. 구현 - BFS를 통해 구현한다 - 다음으로 이동하려는 칸이 0이라면, Check[][] 배열을 비교하여 현재 시간(Cv)+1보다 크다면 이동 - 다음으로 이동하려는 칸이 2라면(소용돌이), 현재 시간을 3으로 나눴을때..

문제 링크: https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 1. 주의할 점 - Arr[] 배열을 Long Long 타입으로 받는다 - DP[] 배열에 가장 긴 증가하는 부분 수열이 저장되어 있는 것이 아니다 2. 구현 - 모든 수를 Arr[]배열에 입력받고, Dp[0]=Arr[0], Idx=0, Ans[0].idx=0, Ans[0].val=Arr[0]으로 초기화 하고 시작한다 - For문을 1~Num-1까지 돌리..

문제 링크: https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 1. 주의할 점 - 이분탐색을 사용하는 LIS에 대해 알고 있어야 한다. - 가장 긴 증가하는 부분 수열 2와 풀이 방법은 같다. 다른점은 모든 변수를 Int가 아닌 Long Long으로 받아들인다. 풀이 방법: https://imnotabear.tistory.com/183 [백준 12015] 가장 긴 증가하는 부분 수열 2 (C++) 문제 링크: htt..

문제 링크: https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 1. 주의할 점 - 직전의 게시물과 같이 N^2의 시간복잡도를 지니는 방법으로는 TLE가 난다 - 이분탐색을 사용하여 NlgN의 시간복잡도를 지니게 한다 2. 구현 - 모든 배열에 대한 정보를 Arr[] 배열에 저장하고 Dp[0]= Arr[0], idx=0으로 초기화한다 - i: 1~Num-1까지 For문을 수행하며, Dp[idx]< Arr[i]인 경우, 무조건 추가한다 - 이외의 경..

문제 링크: 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 1. 주의할 점 - DP처럼 진행한다 - 가장 긴 증가하는 부분 수열을 어떤 방식으로 담을 건지 생각한다 2. 구현 - 배열을 입력받으면서, Result[]배열도 초기화 작업을 한다 - i: 1~Num-1, j: 0~i-1까지 반복하면서 Arr[i]>Arr[j]를 만족한다면 Result 배열의 인자를 비..

문제 링크: https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 � www.acmicpc.net 1. 주의할 점 - 이분탐색을 사용한다 - 몬스터와 싸울 경우, While문을 통해 모든 과정을 반복하지 않는다-> While문 사용하면 TLE 발생 2. 구현 - Left = 1, Right = LLONG_MAX로 설정하며 이분탐색을 시작한다 - Cal(Mid) 함수를 통해 Mid의 체력으로 용사가 공주를 구할..

문제 링크: https://www.acmicpc.net/problem/4650 4650번: Jungle Roads The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 < n < 27, and the villages are labeled with the first n letters of the a www.acmicpc.net 1. 주의할 점 - 매 TC마다 Par[] 배열 초기화 - MST 알고리즘에 대해 알고 있어야 한다 2. 구현..

문제 링크: https://www.acmicpc.net/problem/2406 2406번: 안정적인 네트워크 첫째 줄에 두 정수 n(1≤n≤1,000), m이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서로 다른 두 컴퓨터, www.acmicpc.net 1. 주의할 점 - 1번 Node를 제외하고 MST를 만든다 - 총 Node-2개의 간선이 만들어지면 된다(Cycle을 생성하는 간선은 개수에 포함 안함) 2. 구현 - 크루스칼 알고리즘을 통해 MST 문제를 해결한다 - 이미 연결된 지사의 컴퓨터 중, 같은 부모를 공유하고 있지 않다면 Make_union(a,b) 함수를 통해 같은 부모를 공유하도록 설정하..