https://www.acmicpc.net/problem/15903

문제 풀이

문제 설명이 길지만 간단하게 요약하자면 입력받은 m번만큼 가장 작은 두 개의 카드 숫자를 더해서 갱신을 반복하는 것이다.

m번의 반복이 끝난 뒤 모든 카드의 합을 가장 작게 만드는 것이 목표이므로 매순간 가장 작은 카드 두개를 선택하여 갱신하는것을 파악하는게 가장 중요한 문제같다.

이 문제를 푸는 방법으로 생각난 것은 그리디 알고리즘과 최소 힙이며 두 가지 모두 구현해보았다.

n이 최대 1000이고 m은 최대 15000이므로 그리디 알고리즘을 사용하여 매번 갱신하면 약 15000 X 5000(1000*log1000) = 75000000 (7천 5백만)의 연산 횟수가 나오므로 약간 간당간당할꺼 같다고 생각했지만 결과적으론 통과하였다.

우선 그리디 알고리즘은 m번을 반복하면서 계속 리스트를 오름차순 정렬하여 가장 작은 두 개를 갱신하는 방식이고 최소 힙은 자체에서 가장 작은 원소를 뽑아내는 효율적인 알고리즘을 갖고 있기에 단순하게 원소 두 개를 뽑고 합을 두 번 넣어주면 해결할 수 있다.

당연하게도 오름차순 정렬할 땐 O(nlogn)의 시간 복잡도가, 최소 힙은 정렬 시 O(logn)의 시간 복잡도가 걸리기 때문에 최소 힙을 사용하는게 더 효율적인 방식이다.

전체 코드를 보면서 설명하겠다.

그리디 알고리즘 코드

n,m=map(int,input().split())
card=list(map(int,input().split()))
for i in range(m):
    card.sort()
    card[0],card[1]=card[0]+card[1],card[0]+card[1]

print(sum(card))

1, 2 번째 줄은 n과 m, card 리스트를 입력받았다.

그리고 m번 반복하면서 card 리스트를 정렬하고 가장 작은 두 개를 갱신한 뒤 전체 합을 출력하면 된다.

이때 주의해야 할점은 말했듯이 매번 정렬을 해야 한다는 점인데 그 이유는 가장 작은 두 개의 숫자를 더해서 갱신했을 때 해당 숫자들이 전체 리스트에서 가장 작은 두 개의 숫자라는 보장이 없기 때문이다.

이렇게 매번 O(nlogn)의 시간 복잡도가 걸려서 갱신해야 되기 때문에 보다 비효율적인 방식이다.

다음은 최소 힙을 이용한 코드이다.

최소 힙 코드

import heapq

n,m=map(int,input().split())
card=list(map(int,input().split()))
heapq.heapify(card)
for i in range(m):
    tempa=heapq.heappop(card)
    tempb=heapq.heappop(card)
    heapq.heappush(card,tempa+tempb)
    heapq.heappush(card,tempa+tempb)

print(sum(card))

먼저 힙 모듈을 사용하기 위해 heapq를 import 했고 n, m, card 리스트를 입력받는 부분까진 똑같다.

5번째 줄의 heapify는 기존의 리스트를 heap 형태로 변환하는 함수이다.

그리고 6번째 줄부터는 m번 반복하면서 두 번 숫자를 뽑고 더한값을 다시 두 번 넣어준다.

마찬가지로 sum 함수를 이용해 전체 합을 출력하면 된다.

그리디 알고리즘이랑은 다르게 매번 갱신 시 O(logn)의 시간복잡도가 걸리므로 더 효율적인 코드인 것을 알 수 있다.

결과화면에서 확인할 수 있듯이 실제로도 시간에서 차이가 났다.

같은 문제를 풀더라도 방식에 따라 효율성에서 차이가 나므로 항상 효율적인 방법을 고민하는게 중요한 것 같다.

https://www.acmicpc.net/problem/2206

문제 풀이

전형적으로 시작 노드에서 도착 노드까지 장애물을 피해 도착하는 최단 거리를 출력하는 문제이다.

다만 다소 어렵게 느껴질 수 있는 부분은 기존의 그래프 탐색은 방문 가능한 노드인지(장애물이 아닌지), 방문한 노드인지를 체크하고 탐색하지만, 이 문제에선 최대 한 개의 벽을 부수고 이동할 수 있다는 개념이다.

아마 정답 비율이 낮은 이유(약 23%)는 이 개념 때문이지 않을까 추측해본다.

이 문제에서는 살짝 다르게 생각하는 방법이 필요하다.

물론 문제대로 매번 현재 상태가 벽을 부수고 이동한 상태인지 아닌지 기록할 수도 있겠지만 3차원 리스트로 생각하면 좀 더 이해하기 쉬울 것이다.

즉, 기존의 2차원 리스트를 2개 갖는 3차원 리스트로 생각하고 벽을 부수지 않은 상태라면 0번째 인덱스의 2차원 리스트, 벽을 부순 상태라면 1번째 인덱스의 2차원 리스트로 생각하면 된다.

벽을 부수는 것을 한 층 올라간다고 생각하면 이해가 쉬울 것이다.

이렇게 개념만 잡고 간다면 나머지는 기존의 2차원 리스트에서 최단 거리를 찾는 알고리즘과 같기 때문에 어렵지 않게 구현할 수 있을 것이다.

전체 코드를 따라가면서 이해하면 도움 될 것이다.

import sys
from collections import deque

#위,오른,아래,왼
dx=[-1,0,1,0]
dy=[0,1,0,-1]
n,m=map(int,input().split())
graph=[]
res=-1
queue=deque()
for i in range(n):
    graph.append(list(map(int,list(sys.stdin.readline().rstrip()))))
visited=[[[0 for i in range(m)] for j in range(n)]for k in range(2)]

       #벽 부수기 전,시작위치,거리
queue.append([0,0,0,1])
visited[0][0][0]=1
while len(queue)>0:
    temp_list=queue.popleft()
    for i in range(4):
        x=temp_list[1]+dx[i]
        y=temp_list[2]+dy[i]
        if 0<=x<n and 0<=y<m:
            if x==n-1 and y==m-1:
                res=temp_list[3]+1
                break
            elif graph[x][y]==0 and visited[temp_list[0]][x][y]==0:
                visited[temp_list[0]][x][y]=1
                queue.append([temp_list[0],x,y,temp_list[3]+1])
            elif graph[x][y]==1:
                if temp_list[0]==0 and visited[0][x][y]==0:
                    visited[1][x][y]=1
                    queue.append([temp_list[0]+1,x,y,temp_list[3]+1])

    if res!=-1:
        break
if n==1 and m==1:
    print(1)
else:
    print(res)

먼저 최대 1000000개의 노드가 가능한 그래프이고 3차원 리스트로 생각하므로 최대 2000000개가 가능하기에 최대한 시간을 줄일 필요성이 있었다.

따라서 sys 모듈을 이용하여 입력 시간을 줄였고 시작과 끝부분에서 데이터 삽입 삭제가 가능한 deque 모듈을 사용하여 BFS에서 최대한 시간을 줄이려고 노력했다.

그냥 List에서 BFS를 위해 pop(0)을 한다면 매번 O(n)의 시간 복잡도가 걸리기 때문이다.

5, 6번째 줄에선 한 노드를 기준으로 0번째 인덱스부터 차례대로 위 노드, 오른쪽 노드, 아래 노드, 왼쪽 노드로 가능한 방향을 저장한 리스트이다.

10번째 줄은 BFS 탐색을 위해 데크로 선언하였다.

11번째 줄에선 그래프로 저장하며 13번째 줄의 visited 리스트는 각 각 방문한 노드인지 체크하는 리스트인데 중요한 것은 3차원 리스트로 선언한 것이다.

최대 한 번 벽을 부수고 이동할 수 있기 때문에 2개의 2차원 리스트로 선언했고 만약 2번 3번 벽을 부수고 이동한다면 각 층을 올라간다고 생각하여 3개, 4개의 2차원 리스트로 선언하면 된다.

16번째 줄에서 데크에 넣은 리스트는 벽을 부수기 전, 시작 위치, 거리이다.

그러고 나서 18번째 줄에서 BFS를 실행하면 된다.

19번째 줄의 popleft()는 O(1)의 시간 복잡도가 걸리고 24번째 줄에선 도착하면 res를 갱신한 뒤 BFS를 탈출한다.

27번째 줄은 방문 가능한 노드일 경우 데크에 넣는 코드고 30번째 줄은 벽이 있을 때 부수고 온 상태가 아니라면 벽을 부수고(층을 이동하여) 노드를 데크에 넣어준다.

마지막으로 res를 출력하면 통과할 수 있다.

알고리즘 구현 자체는 다른 그래프 탐색과 비슷한 수준이지만 벽을 부수고 이동할 수 있다는 조건 때문에 어렵게 다가왔다.

주어진 조건을 이해와 구현이 쉬운 방법으로 변환하는 게 핵심 포인트이며 이처럼 다차원 리스트로 변환하여 생각하는 방법은 은근히 나오니 꼭 익숙해지는 게 좋을 것 같다.

비슷하게 다차원 리스트를 이용하는 문제를 추천하며 마무리 짓도록 하겠다.

https://www.acmicpc.net/problem/7569

해당 문제와 비슷하지만 조건에서 차이가 나기 때문에 정렬 함수를 이용해서 푼 문제가 있다.

정렬 함수가 다소 익숙하지 않다면 해당 포스팅을 참고해서 익숙해지면 좋을 것 같다.

https://khsung0.tistory.com/37

문제 풀이

https://www.acmicpc.net/problem/10989

이번 문제도 데이터를 입력받아 정렬한 뒤 오름차순으로 출력하는 부분은 동일하지만 윗 문제와 다르게 수의 범위가 10000 이하인 자연수이다.

이 조건이 중요한 이유는 수의 범위가 충분히 적기 때문에 각 인덱스를 해당 숫자로 생각하여 카운팅으로 정렬할 수 있기 때문이다.

이 정렬 방식은 계수 정렬(Counting Sort)이라 하며 계수 정렬 자체는 다소 사용하는 경우가 적을지라도 해당 방법이 인덱스를 원소로 여기는 방식이기 때문에 학습하면 좋다.

인덱스를 원소로 여기는 방식은 Union-Find 알고리즘 같은 부분에서 집합들의 부분 집합을 구한다든가 최소 신장 트리(Minimum Spanning Tree)에서 사이클을 찾는데 자주 쓰이기 때문이다.

관련 알고리즘들을 포함하여 알아야 될 법한 알고리즘들은 직접 작성한 "쉽게 풀어쓴 자료구조와 알고리즘" 전자책에 자세하고 쉽게 설명해 놓았으니 관심 있는 사람은 한 번씩 구경하면 좋을 것 같다.

다시 문제로 넘어와서 실버 5 치고는 상당히 낮은 23%의 정답 비율이 나타나는데 어려운 개념이 필요한 문제가 아니므로 전체 코드를 보면 쉽게 이해할 수 있을 것이다.

import sys
n=int(input())
num_list=[0 for i in range(10000)]
for i in range(n):
    num_list[int(sys.stdin.readline())-1]+=1
for i in range(len(num_list)):
    for j in range(num_list[i]):
        print(i+1)

num_list는 9999까지(파이썬의 for문은 10000 미만까지 반복하기 때문에) 0으로 초기화했는데 이 부분은 수의 범위가 10000 이하인 자연수이기 때문에 0번째 인덱스는 1을, 1번째 인덱스는 2를 의미한다.

만약 인덱스와 숫자가 헷갈린다면 10000까지(range(10001)) 초기화시키고 1번째 인덱스를 1로 생각하면 된다.

또한 입력받을 때 sys 모듈을 import 하여 sys.stdin.readline()을 사용하였다.

내장 함수인 input()은 prompt message를 출력하고 각 줄의 개행 문자를 삭제하지만 sys.stdin.readline()은 이러한 작업 없이 각 줄을 입력받기 때문에 입력 양이 많을수록 input() 보다 sys.stdin.readline()이 더 효율적이다.

이 차이로 인해 통과와 시간 초과가 갈리는 경우가 많으니 많은 양을 입력받는 문제에서 활용하는 것이 좋다.

5번째 줄에서 해당 원소가 뜻하는 인덱스의 값을 카운팅 해주면 해당 원소는 그만큼 입력받았단 뜻이다.

즉 0번째 인덱스의 값이 1이라면 1을 한 번 입력받은 거고 3번째 인덱스의 값이 2라면 4를 두 번 입력받은 것이다.

따라서 6번째 줄에서 num_list를 전체 반복하며 num_list [i]가 1 이상이라면 해당 횟수만큼 반복하여 원소를 출력하면 된다.

조건에 따라 유연하게 방식을 적용하는 게 중요한 문제인 것 같다.

https://www.acmicpc.net/problem/2751

문제 풀이

문제 자체는 단순하다.

입력으로 받는 데이터를 그대로 오름차순으로 정렬해서 출력하면 되기 때문이다.

다만 문제의 조건에서 수의 개수는 1000000개 이하, 각 수는 절댓값이 1000000보다 작거나 같은 정수이기 때문에 인덱스로 접근하는 방식은 256MB로 제한되어 있는 메모리에서 너무 많은 공간을 차지하여 불가능하고 결국 정렬하는 방법밖에 없다.

하지만 파이썬을 사용하기에 상당히 유용한 정렬 함수를 사용할 수 있다는 이점이 있다.

바로 기본 라이브러리로 제공하는 sort, sorted 함수이다.

이 함수들은 파이썬 내부에서 삽입 정렬과 병합 정렬을 섞은 방식으로 작동하도록 되어있어 최악의 경우에도 O(nlogn)이라는 효율적인 시간 복잡도를 나타낸다.

O(nlogn)의 시간 복잡도를 나타내는 정렬 방식을 직접 구현하려면 다소 복잡하고 시간도 걸리기에 알아두면 자주 유용하게 사용할 수 있다.

두 함수의 차이점은 sort는 원본 리스트를 정렬하고 sorted는 원본 리스트는 변함없이 정렬된 리스트를 반환한다는 점이다.

또한 해당 함수들의 인자로 key를 사용할 수 있다.

num_list=[[1,2],[2,2],[1,1],[2,1]]
num_list.sort(key = lambda x : (x[1],-x[0]))

이렇게 사용하면 정렬할 때 각 원소들의 1번째 인덱스를 기준으로 오름차순, 1번째 인덱스가 같다면 0번째 인덱스를 기준으로 내림차순으로 정렬하겠단 의미이다.

해당 정렬방법은 코딩 테스트에도 유용하게 쓰이고 필자도 사용한 적이 많으므로 반드시 익숙해지는 것을 권장한다.

다음은 문제를 통과한 전체 코드이다.

num=int(input())
numbers=[]
for i in range(num):
    numbers.append(int(input()))
for i in sorted(numbers):
    print(i)

정답률이 30%인 문제 치고 상당히 짧고 간결한 코드가 나왔다.

numbers 리스트에 원소들을 입력받고 sorted로 numbers를 정렬한 리스트를 반복하며 출력할 뿐이다.

이때 numbers를 정렬한 리스트를 다시 사용할 필요가 없어서 sorted를 썼지만 재사용해야 한다면 새로운 변수에 정렬한 리스트를 할당하든가 sort로 원본 리스트를 정렬하든가 문제 상황에 맞게끔 적용하는 것을 주의해야 한다.

또한 Python3 자체가 다소 느리기 때문에 제출은 PyPy3로 했다.

분명 맞는 코드 같은데 시간 초과가 뜬다면 PyPy3로 제출해보는 것을 권장한다.

관련 문제인 10989번 수 정렬하기 3은 비슷한 문제지만 조건에서 차이가 나기 때문에 다른 방식으로 풀었다.

해당 문제를 풀어보고 만약 막혔다면 풀이 방식에서 도움받으면 좋을 것 같다.

https://khsung0.tistory.com/38

https://www.acmicpc.net/problem/2436

문제 풀이

최대 공약수와 최소 공배수에 관한 수학 문제이다.

문제에 들어가기 앞서 최대 공약수와 최소 공배수에 대한 관계와 최대 공약수를 구하는 방법인 유클리드 호제법을 알고 있어야 수월하게 풀 수 있다.

간단하게만 설명하자면 두 수 A, B가 있을 때 동시에 나눠서 나머지가 0이 되는 가장 큰 수를 최대 공약수라 하고 A의 배수, B의 배수 중 가장 작은 수를 최소 공배수라 한다.

여기까지는 누구나 알고 있지만 관계에 대해서 이해해야 보다 수월하게 풀 수 있다.

최대 공약수를 c, 최소 공배수를 d라 하고 A를 c로 나눈 몫을 a, B를 c로 나눈 몫을 c로 한다면 a와 b는 서로소 관계(1을 제외한 공약수가 없는 관계)가 된다.

따라서 a x b x c = d 가 성립하기 때문에 이를 자유자재로 이용할 수 있어야 한다.

또한 유클리드 호제법은 두 수가 있을 때 큰 수를 작은 수로 나눈 나머지가 0이 될 때까지 반복하여 최대 공약수를 구하는 방식이다.

전체 코드에서 구현 방법을 보면 이해될 것이다.

def gcd(num1,num2):
    if num2%num1==0:
        return num1
    else:
        return gcd(num2%num1,num1)
a,b=map(int,input().split())
b=b//a
res=[]
for i in range(1,b+1):
    if b%i==0:
        if i<b//i:
            if gcd(i,b//i)==1:
                res.append([i*a+(b//i)*a,i*a,(b//i)*a])
        else:
            if gcd(b//i,i)==1:
                res.append([i*a+(b//i)*a,(b//i)*a,i*a])
if len(res)>0:
    res.sort(key=lambda x:x[0])
    print(res[0][1],res[0][2])

먼저 유클리드 호제법을 사용하는 최대 공약수를 구하는 함수를 gcd로 선언했다.

gcd는 최대 공약수(Greatest Common Divisor)의 약자이기 때문인데, 이처럼 코드를 작성할 때는 해당 변수가 무엇을 뜻하는지, 해당 함수가 어떤 기능을 하는지 의미하는 이름으로 짓는 게 차후에 코드를 이해하기 편해서 좋다.

num2가 num1보다 더 큰 수이고 함수를 보면 알 수 있듯이 큰 수를 작은 수로 나눴을 때 나머지가 0이면 작은 수를 리턴, 아니라면 나머지와 나눴던 작은 수를 매개변수로 재귀 호출한다.

이렇게 반복하면 최대 공약수를 얻을 수 있다.

7번째 줄에서 b를 a로 나눈 몫으로 저장하는 이유는 최소 공배수에서 최대 공약수를 없애고 서로소인 두 수의 곱만 고려하기 위해서다.

만약 서로소 관계인 두 수를 구한다면 각 각 최대 공약수를 곱해서 출력하면 답을 구할 수 있을 것이기 때문이다.

8번째 줄의 res 리스트는 서로소인 두 수와 두 수의 합을 저장하는 용도다.

문제에서 분명 조건에 부합하는 자연수 쌍은 여러 개 있을 수 있는데 두 자연수의 합이 최소인 경우를 출력하라 했으니 합을 기준으로 정렬하여 가장 작은 경우를 출력하면 될 것이다.

따라서 9번째 줄에서 1부터 b까지 반복을 하는데 i로 b를 나눈 나머지가 0이면 두 수의 곱으로 나타낼 수 있는 숫자고 두 번째 if문은 더 큰 수를 gcd 함수의 두 번째 인자에 넣기 위한 조건문이다.

또한 gcd 함수의 반환 결과가 1이라면 두 수가 서로소 관계이므로 두 수의 합과 두 수를 최대 공약수를 곱해서 res 리스트에 넣었다.

반복문이 종료되면 res 리스트를 두 수의 합을 기준으로 오름차순 정렬하고 첫 번째 원소에 들어가 있는 두 수를 출력하면 통과한다.

문제를 통과하긴 했지만 조금 더 생각하면 탐색하는 범위를 절반 정도로 줄일 수 있을 것 같다.

https://www.acmicpc.net/problem/1009

문제 풀이

브론즈 문제 치고 정답 비율이 24%로 엄청 낮은 통계였다.

왜 그런가 싶어서 문제를 자세히 봤더니 아마 생각난 방식 그대로 제출한다면 시간 초과가 날 것 같단 생각이 들었다.

문제 자체는 단순하게 데이터의 개수만큼 컴퓨터 대수인 10개를 나눈 나머지를 출력하고 0만 10으로 변환하면 되는데 여기서 문제는 데이터의 개수가 a^b 만큼 들어오고 a는 100 미만, b는 1000000 미만의 자연수이므로 총 100000000(1억) 개의 데이터가 될 수 있으며 심지어 테스트 케이스도 입력받기 때문에 단순하게 제곱수를 통한 구현은 시간 초과가 날 가능성이 높았기 때문이다.

혹시나 해서 그대로 구현하여 제출했더니 역시 시간 초과가 났다.

n=int(input())
for i in range(n):
    a,b=map(int,input().split())
    print(a**b%10)

따라서 시간을 줄일 수 있는 방식을 생각해야 했고 일의 자리가 나올 수 있는 숫자들을 구해서 해당 개수만큼 나눈다면 어느 정도 정답에 근접할 것이라 생각했다.

다음은 통과한 전체 코드이다.

n=int(input())
for i in range(n):
    a,b=map(int,input().split())
    if a==1:
        print(1)
    else:
        last=a%10
        last_num=[last]
        sum_last=(last**2)%10
        while sum_last not in last_num:
            last_num.append(sum_last)
            sum_last=(sum_last*last)%10
        if last_num[(b-1)%len(last_num)]==0:
            print(10)
        else:
            print(last_num[(b-1)%len(last_num)])

먼저 4번째 줄에서 if문을 쓴 이유는 a가 1이라면 b가 어떤 숫자가 나와도 데이터 개수는 1개이므로 무조건 1이 나올 수밖에 없기 때문에 처리했다.

a가 1이 아닌 나머지의 경우엔 일의 자리를 구해서 리스트에 저장하고 동일한 숫자가 나오기 전까지 a를 곱하여 일의 자리를 계속해서 추가한다.

10으로 나누기 때문에 최대 10개가 나올 수 있으며 0은 10으로 치환해야 한다는 것을 잊으면 안 된다.

해당 반복문이 종료되면 인덱스는 0부터 시작하기 때문에 b-1을 last_num의 길이(일의 자리에 나올 수 있는 숫자들)로 나누고 해당 숫자가 0이면 10으로 치환, 아니면 해당 숫자를 출력하면 통과한다.

역시 구현 자체가 어려운 문제는 아니라 단순하게 생각해서 제출한 경우가 많아 정답 비율이 낮게 나온 것 같다.

https://www.acmicpc.net/problem/10818

문제 풀이

언어를 배우는 초기에 풀어볼 법한 아주 기초적인 문제라 포스팅하지 않으려 했지만 생각보다 정답 비율이 엄청 낮아서 작성하기로 했다.

단순하게 최솟값과 최댓값을 구하는 건 상당히 쉽다.

최솟값과 최댓값을 뜻하는 변수 두 개를 선언하고 전체 Data를 돌면서 각각 최솟값보다 작은 수가 나오면 갱신, 최댓값보다 큰 수가 나오면 갱신하면 끝이다.

이때 처음 변수 선언 시 팁이 될 수 있는 것은 최솟값 변수엔 가능한 최댓값보다 큰 값을, 최댓값 변수엔 가능한 최솟값보다 작은 값으로 초기화하는 것이다.

그래야 단 한 번이라도 갱신할 수 있으며 파이썬스럽게 선언하는 방법은 float('inf'), float('-inf') 이렇게 양의 무한대, 음의 무한대로 선언하는 것이다.

이걸 그대로 출력해도 inf, -inf로 나오기 때문에 편하게 무한대라 생각하면 된다.

문제를 푸는 코드는 먼저 C를 이용하여 앞서 설명한 방식대로 답을 구하는 방법과 파이썬의 함수를 이용하여 단 3줄로 구현하는 방법을 소개하겠다.

먼저 C 코드이다.

#include <stdio.h>
int main() {
	int a,b,min=1000000,max=-1000000;
	scanf("%d", &a);
	for (int i = 0; i < a; i++) {
		scanf("%d", &b);
    	if (min > b) {
            min = b;
        }
    	if (max < b) {
            max = b;
        }
	}
	printf("%d %d", min, max);
	return 0;
}

원소는 -1000000 이상, 1000000 이하로 제한되어 있으므로 3번째 줄에서 딱 맞게 초기화했다.

그리고 5번째 반복문에서 원소를 하나씩 입력받으며 입력받은 값이 최솟값 변수보다 작다면 갱신, 최댓값 변수보다 크다면 갱신하고 결괏값을 출력하면 된다.

그저 완전 탐색하면 풀리는 상당히 쉬운 문제다.

다음은 파이썬 코드이다.

n=int(input())
num_list=list(map(int,input().split()))
print(min(num_list),max(num_list))

단 3줄로 상당히 간단하게 풀었다.

2번째 줄의 map은 input으로 받은 문자열을 split을 통해 공백을 기준으로 분리하고 int로 형 변환하는 함수이다.

따라서 리스트로 형 변환하여 저장한 뒤 min함수를 통해 최솟값을, max함수를 통해 최댓값을 출력하면 된다.

각 함수 별로 데이터 전체를 탐색하기 때문에 O(n)의 시간 복잡도가 걸리는데 이걸 두 번 반복해도 충분히 시간 초과에 걸리지 않고 통과할 수 있다.

https://www.acmicpc.net/problem/11053

문제 풀이

동적 계획법(Dynamic Programming, 이하 DP)을 활용하는 문제였다.

DP란 정해진 방식이 있는 게 아니라 큰 문제를 해결하기 위해 문제를 세분화시키고 각각 작은 문제를 해결하여 나온 값들을 이용하는 방식을 총체적으로 지칭하는 알고리즘이다.

따라서 이미 연산한 값을 이용함으로써 불필요한 연산을 줄일 수 있다.

이것의 대표적인 예시가 피보나치 수열이다.

매번 필요한 값을 연산하도록 구현할 수 있지만 DP를 활용하게 되면 획기적으로 연산 횟수가 줄어들기 때문에 더 많은 수열을 구할 수 있다.

다시 문제로 돌아와서 문제는 A란 수열에서 원소가 증가하는 부분 수열을 찾는 것이며 각 원소는 연속하지 않아도 된다.

해당 문제는 최장 증가 수열(Least Increasing Subsequence) 알고리즘으로 알려져 있으며 DP를 활용하는 기법이기도 하다.

문제의 조건은 다음과 같다.

1. 수열 A의 크기는 1000 이하다.
2. 각 원소도 1000 이하의 자연수이다.

수열 A의 크기는 1000 이하이므로 O(n^2)의 시간 복잡도도 충분히 연산이 가능하다.

바로 전체 코드를 통해 어떻게 DP를 활용했는지 확인해 보자.

n=int(input())
sequence=list(map(int,input().split()))
res=[0 for i in range(n)]
res[0]=1
for i in range(1,n):
    cnt=0
    for j in range(0,i):
        if sequence[j]<sequence[i] and cnt<res[j]:
            cnt=res[j]
    res[i]=cnt+1
print(max(res))

3번째 줄 res란 리스트가 DP를 활용하는 리스트이기 때문에 핵심 포인트이다.

sequence는 원래의 수열 A를 뜻하고 res는 각 원소가 부분 수열의 몇 번째에 해당하는지를 나타낸다.

따라서 n만큼 수열의 길이를 입력받으므로 res를 n의 길이만큼 초기화시키고 res의 0번째 인덱스를 1로 한 이유는 0번째 인덱스의 원소가 부분 수열의 첫 번째 원소가 된다는 의미이다.

5번째 줄부터 중첩 for문을 사용하는데 버블 정렬과 원리는 비슷하다.

첫 번째 for문에서는 1번째 원소부터 n-1번째 원소까지 반복하는데 매번 카운트를 0으로 초기화하고 두 번째 for문에서는 i번째 원소보다 작으면서 카운트보다 res의 원소가 더 크다면 카운트를 갱신한다.

즉 해당 원소보다 작은 원소들이 최대한 몇 개 포함될 수 있는지 계산하는 방식이다.

두 번째 for문이 끝나면 res의 i번째를 카운트+1로 갱신한다.

예를 들어 카운트가 2라면 i번째 인덱스는 3이 되고 i번째 원소보다 작은 원소가 두 개, i번째 원소는 부분 수열의 3번째 원소가 될 수 있다는 의미이다.

이렇게 리스트에 몇 번째 원소가 될 수 있는지 카운트함으로써 부분 수열을 일일이 구하지 않아도 최장 길이를 구할 수 있다.