728x90 Lis 썸네일형 리스트형 [백준알고리즘] 2565번: 전깃줄 -C++ [백준알고리즘] 2565번: 전깃줄 -C++ 2565번: 전깃줄 (acmicpc.net) 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 주어진 전깃줄 중에서 최소의 전깃줄을 제거해 겹치는 선이 없게 만드는 문제다. 예전에 파이썬으로 풀었던 적이 있는 문제다. 예전에 풀었던 코드를 보니 '역시 파이썬은 코드가 쉽구나'라는 생각과 동시에 '이때는 왜 이리 쉽게 푼 것 같지..'라는 생각이 들었다. 그만큼 오늘 바로 풀어내지는 못했었다. [백준알고리즘] 2565번: 전깃줄 -Python (tistory.com) [백준알.. 더보기 [백준알고리즘] 2631번: 줄세우기 -Python [백준알고리즘] 2631번: 줄 세우기 -Python https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 www.acmicpc.net LIS문제이다. 세워져있는 상태에서 정상적으로 줄 서있는 학생들의 수를 구해서 전체 .. 더보기 [백준알고리즘] 2352번: 반도체 설계 -Python [백준알고리즘] 2352번: 반도체 설계 -Python https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 언뜻 봐서는 O(N^2)의 방식의 풀이도 통과할 줄 알았는데 시간 초과가 발생했다. 이 문제는 LIS문제이다. 가장 긴 증가하는 부분 수열을 만들어야 한다. 여기서는 직접 부분 수열을 출력하는 것이 아닌 길이만 출력하면 되기 때문에 간단한 lower .. 더보기 [백준알고리즘] 2565번: 전깃줄 -Python [백준알고리즘] 2565번: 전깃줄 -Python https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net 20200408 아래부분에 새롭게 푼 코드를 올렸다. 내용은 동일한데 코드가 더 깔끔하다. 전깃줄 문제를 풀어봤다. 저번 문제에 이어서 LIS를 응용하는 문제라고 설명이 되어있습니다. '이게 왜 LIS 문제이냐'라고 한다면, 최소.. 더보기 [백준알고리즘] 11054번: 가장 긴 바이토닉 부분 수열 -Python [백준알고리즘] 11054번: 가장 긴 바이토닉 부분 수열 -Python https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 밑에 새로 풀면서 추가 설명을 적어놨다. 첫 풀이가 어려우면 밑의 풀이를 보면 된다. 2019-08-13 첫 번째 풀이 LIS(Longest Increasing Subsequence)의 응용문제 중 하나이다. 문제를 보면 뽑아낸 부분수열이 증가하다가 감소하는 형태를 가질 때의 최대길이를 구하는 문제이다. 쉬운 버전인 11053번의 경우 증가하는.. 더보기 이전 1 다음