새벽_나그네
12시 지난 새벽
새벽_나그네
전체 방문자
오늘
어제
  • 분류 전체보기
    • TIL
    • DevLog
    • Algorithm
    • ComputerScience
    • etc

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 자기주도학습
  • Python
  • 스파르타코딩클럽
  • portfolio
  • Github
  • 국비지원
  • docker
  • 내일배움카드
  • 코린이
  • Selenium 4
  • 개발일지
  • AI트랙
  • 프로그래머스
  • 코딩
  • 내일배움단
  • 내일배움캠프
  • TodayILearned
  • til
  • machine learning
  • 코딩프로젝트

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
새벽_나그네

12시 지난 새벽

Algorithm

[백준_12015] 가장 긴 증가하는 부분 수열 2

2022. 6. 19. 20:48

문제 보기: 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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

새로 사용한 함수

bisect.bisect_left( 탐색 문자열, 탐색 값)

이진 탐색을 수행해주는 함수로 파이썬에서 지원한다. 

결과 값으로는 해당 구간에서 값이 들어가야 하는 위치를 알려준다 left와 right가 있으며 left는 왼쪽으로 right는 오른쪽으로 알려준다.

 

 

풀이 과정

코드 2번 방식으로 이전에 풀었던 것을 생각하면서 풀었고 결괏값이 계속 맞게 나오는데 실패라고 결과가 계속 나와서 다른 답을 찾아보았으나 왜 틀렸는지 이해가 되지 않는다.

1. 기본적인 풀이과정은 이진 탐색을 수행해서 결과 수열을 만들 때 시간 복잡도를 고려하여 작성하면 된다.

2. 처음에 수열을 찾을 값을 배열로 입력받고 해당 값을 순회하면서 점점 커지도록 만들어준다.

3. 기본적인 내용으로는 다음으로 탐색하는 값이 이전 값보다 큰지 작은 지를 비교하면서 진행하게 되지만 만들어진 수열에서 이진 탐색을 하여 추가적인 경우의 수가 있을 가능성을 확인한다.

4. 1~3번 내용을 반복적으로 수행하고 마지막으로 만들어진 배열의 값의 길이를 출력한다.

 

코드 1번의 풀이 방식도 2번과 같아서 같은 풀이과정으로 남겨두지만 1번은 성공 2번은 실패한 코드

 

코드

코드 1

import sys
import bisect
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

result = []
result.append(arr[0])

for i in range(1, N):
    if arr[i] > result[-1]:
        result.append(arr[i])
    else:
        index = bisect.bisect_left(result, arr[i])
        result[index] = arr[i]

print(len(result))

 

코드 2

import bisect

i = int(input())

num = [] * i
max = []
str = input().split()

for _ in str:
    num.append(_)

max.append(num[0])

# print(":::::::: process check ::::::::")
for i, check in enumerate(num[1: len(num)], start=1):
    if num[i - 1] < num[i]:
        max.append(num[i])
    else:
        index = bisect.bisect_left(max, num[i])
        # print(f"{i} : {index}")
        max[index] = num[i]
    # print(i, check)

# print(":::::::: process check ::::::::")

# max.append(num[-1])
# print(max)
print(len(max))
저작자표시 비영리 변경금지 (새창열림)

'Algorithm' 카테고리의 다른 글

[프로그래머스] 코딩테스트 연습2020 KAKAO BLIND RECRUITMENT - 문자열 압축  (0) 2022.06.23
[프로그래머스] 코딩테스트 연습2022 KAKAO BLIND RECRUITMENT - 신고 결과 받기  (0) 2022.06.20
[백준_2775] 부녀회장이 될테야  (0) 2022.06.18
[백준_2675] 문자열 반복  (0) 2022.06.17
[백준_3009] 네 번째 점  (0) 2022.06.16
    'Algorithm' 카테고리의 다른 글
    • [프로그래머스] 코딩테스트 연습2020 KAKAO BLIND RECRUITMENT - 문자열 압축
    • [프로그래머스] 코딩테스트 연습2022 KAKAO BLIND RECRUITMENT - 신고 결과 받기
    • [백준_2775] 부녀회장이 될테야
    • [백준_2675] 문자열 반복
    새벽_나그네
    새벽_나그네
    IT, 프로그래밍, 정보, 스마트스토어

    티스토리툴바