본문 바로가기

백준 PS일지/LongestIncreasingSubsequence

 (4)
[백준/Swift] 3745: 오름세. while문 무한 입력 EOF처리 방법 | PS일지 문제 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 간단한 문제 요약 n일동안 매일 주가를 적어 놓고 가장 긴 오름세를 찾으시오 고려해야 할 사항 둘째 줄에서부터 주가가 첫 날부터 순서대로 주어집니다. 이때 주가는 한 개 이상의 공백으로 구분되어 있습니다. 문제 풀이 이 문제는 LIS문제입니다. 하지만 종료조건이 주어지지 않습니다. EOF처리 방법을 알아야 합니다. EOF처리에 대해 처음으로 관심을 갖게 한 문제입니다. while let input = readLine() { ... } 기본적으로 Swift..
[백준/Swift] 2568: 전깃줄 - 2 문제 부수기!! + LIS 개념과 이분 탐색, 역 추적 개념 정리 | PS일지 문제 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 간단한 문제 요약 두 전봇대 사이에 여러 개의 전깃줄이 있다. 이 전깃줄 등 교차하는 경우가 발생했다. 그래서 교차하지 않도록 몇 개의 전깃줄을 최소한으로 제거하려 할 때 없애야 하는 전깃줄의 A 전봇대에 연결되는 위치 번호를 오름차순으로 출력하시오. 고려해야 할 사항 답이 여러 개의 경우가 있을 수 있습니다. 그 중 하나를 출력해야 합니다. 전깃줄의 개수가 최악의 경우 100,000개입니다. 문제 풀이 이 문제는 LIS 알고리즘 + 역추적(정말 쉽습니..
[백준/Swift] 14002: 가장 긴 증가하는 부분 수열4 파해치기 | PS일지. 문제 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 간단한 문제 요약 수열이 주어졌을 때 가장 긴 증가하는 부분 수열을 구하시오! 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 고려해야 할 사항 2차원 dp를 활용한 LIS는 단순 길이 정보를 dp에 저장합니다. 따라서 역추적을 통해 가장 큰..
[백준/Swift] 2565 : 전깃줄 BOJ_2565.swift 2565 : 전깃줄/ 문제 소개 풀이 과정 코드 구현 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 2565 : 전깃줄 / 문제 소개 전봇대 A와 B가 있다. 전봇대에 전깃줄을 추가하는데 교차하면 안된다.(합선의 위험) 합선의 위험이 있어 전깃줄에서 몇개의 전깃줄을 없애 교차하지 않도록 만들려고 한다. 이때 교차하지 않게 만들기 위해 없애야 하는 전깃줄 최소 개수를 구해라! 풀이 과정 입력을 보면 전깃줄 개수는 100 이..

티스토리툴바