# LIS
[Problem Solving] 징검다리2
남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다. 이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 이번에 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟다가 높이가 점점 낮은 돌을 밟으면서 개울을 지나가려고 한다. 돌의 높이가 서쪽의 돌부터 동쪽방
문제 풀이(55)
https://www.acmicpc.net/problem/14003LIS 계산:B1에 A1을 할당하고 D1에 1을 할당하여 초기화한다.각 Ai에 대해 if (BmaxLength < Ai)를 확인하여 Ai가 현재 LIS의 마지막 값보다 큰 경우, LIS 길
[Problem Solving] 징검다리
남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다.이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는
[백준] 11053 가장 긴 증가하는 부분 수열 (LIS) / DP (C++)
문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이
[Softeer][Lv3] 징검다리
동적계획법 문제: di = i번째를 포함하는 최장 증가 부분 수열의 길이b 배열 활용: bi = 최장 증가 부분 수열의 길이가 i인 숫자이분탐색 활용: 1 ~ maxLength에 대하여 numi 가 들어갈 위치 탐색
가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)
본래 수열에서 일부 숫자를 지워 만들 수 있는 수열 오름차순으로 증가하는 부분 수열 중에서 가장 긴(원소의 개수가 많은) 수열dp를 이용한 방법은 수열의 값을 하나씩 비교하기 때문에 시간 복잡도가 O(n^2)이다. dp를 이용하여 최장 증가 부분 수열의 길이를 찾는
SWEA 3307. 최장 증가 부분 수열 (Python, LIS(Longest Increasing Subsequence), D3)
유명한? DP문제다.작은 문제로 쪼개보면 우리는 LISi = A0 … Ai 부수열에 대해, Ai로 끝나는 증가 부수열 중에서 가장 긴 부문자열의 길이라고 정의해보자.정답 LIS는 A0, A1, …, An-1 중 하나의 값으로 반드시 끝나므로 LIS 길이는 max(LIS
[코딩테스트] 가장 높은 탑 쌓기(LIS)
밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래 에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프 로그램을 작성하시오.(조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할
[백준 / C++] 2568번: 전깃줄 - 2
백준 2568번: 전깃줄 - 2알고리즘 분류: 가장 긴 증가하는 부분 수열: o(n log n)백준 문제 바로가기오늘 하루 종일 LIS 문제만 잔뜩 풀었다.대부분 코드 복붙이라 레이팅 꽁짜로 얻은 격 히힛ㅎ이 문제는 맥락 상 14003번이랑 비슷한 문제다. 아 그래서
[백준 / C++] 14003번: 가장 긴 증가하는 부분 수열 5
백준 14003번: 가장 긴 증가하는 부분 수열 5알고리즘 분류: 이분 탐색, 가장 긴 증가하는 부분 수열: o(n log n)백준 문제 바로가기오늘 푼 LIS 시리즈 문제 2, 3과 유사한 문제다.다만 달라진 건 길이 뿐만 아니라 수열 자체도 구해야하는 것이다.직전에
[백준 / C++] 12015번: 가장 긴 증가하는 부분 수열 2
백준 12015번: 가장 긴 증가하는 부분 수열 2알고리즘 분류: 이분 탐색, 가장 긴 증가하는 부분 수열: o(n log n)백준 문제 바로가기시리즈가 많은 이번 문제.. 미루고 미루다 오늘에서야 풀었다.DP로 푸는 실버 문제는 이미 풀었는데 이건 DP로 풀게되면 바
백준 7570
대한 어린이집에 올해 입학한 어린이들이 놀이터에 한 줄로 서있다. 모든 어린이들에게는 입학할 때 주어진 번호가 있고 모두 옷에 번호표를 달고 있다. 그런데 어린이들은 아직 번호 순서대로 줄을 잘 서지 못하므로 선생님이 다음과 같은 방법을 사용해서 번호순서대로 줄을 세우
[Tech Interview] 알고리즘(Algorithm)
Bubble Sort에 대해 설명할 수 있다.Bubble Sort 과정에 대해 설명할 수 있다.Bubble Sort을 구현할 수 있다.Bubble Sort의 시간복잡도와 공간복잡도를 계산할 수 있다.Bubble Sort는 Selection Sort와 유사한 알고리즘으로
[BOJ 14448] - Subsequence Reversal (LIS, 담금질 기법, 무작위화, 휴리스틱, C++, Python)
BOJ 14448 - Subsequence Reversal (LIS, 담금질 기법, 무작위화, 휴리스틱, C++, Python)