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

문제 풀이

전형적으로 그래프 탐색 이론인 BFS(너비 우선 탐색)를 이용하면 쉽게 풀리는 문제다.

다만 보편적인 그래프 탐색은 2차원 배열에서 인덱스 접근을 통해 4방 혹은 8방 탐색을 하며 가장 가까운 Target Node를 찾지만 이번 문제는 1번부터 100번까지 각 노드를 번호로 구분할 수 있는 점, 1부터 6까지 적혀있는 주사위를 던져서 옮긴다는 점에 착안하여 1차원 배열에서 6가지 방법을 고려하면 된다는 것을 깨달아야 한다.

이점 외에는 딱히 조심해야 할 부분이 없으므로 바로 코드를 통해 설명하도록 하겠다.

from collections import deque
edge_info=[0 for i in range(101)]
n,m=map(int,input().split())
visited=[0 for i in range(100)]
queue=deque()
for i in range(n+m):
    temp=list(map(int,input().split()))
    edge_info[temp[0]]=temp[1]

             #curr,cnt
queue.append([1,0])
while len(queue)>0:
    curr,cnt=queue.popleft()
    if curr==100:
        print(cnt)
        break
    elif curr>=94:
        print(cnt+1)
        break
    else:
        for i in range(1,7):
            if edge_info[curr+i]==0 and visited[curr+i]==0:
                visited[curr+i]=1
                queue.append([curr+i,cnt+1])
            else:
                if visited[curr+i]==0:
                    visited[curr+i]=1
                    visited[edge_info[curr+i]]=1
                    queue.append([edge_info[curr+i],cnt+1])

1번째 줄은 deque를 사용하기 위해 모듈을 Import 하였다.

물론 이번 문제는 최대 칸이 100개 밖에 없기 때문에 애초에 사이즈가 작아서 시간 복잡도를 줄이기 위해 굳이 deque를 사용할 필요는 없었지만 막상 필요한 상황에서 참고 문서 없이 Import 하려면 까먹기 때문에 잊지 않기 위해서라도 deque를 사용하였다.

만약 deque가 무엇인지 모르는 사람들은 아래 포스팅을 통해 학습하면 될 것이다.

https://khsung0.tistory.com/14

2번째 줄부터 5번째 줄까지는 간선 정보와 방문 체크, 큐 등을 사용하기 위한 초기화 작업이다.

6번째 줄은 반복문을 통해 간선 정보를 저장하였고 11번째 줄은 1번 칸부터 시작해서 BFS를 진행하기 위해 deque에 초기화했다.

12번째 줄부터는 BFS를 구현한 코드이다.

문제에 주어진대로만 구현하면 되기 때문에 딱히 설명할 부분은 없지만 필자는 조금이라도 시간 복잡도 상으로 효율적인 코드를 구현하기 위해 100일 때는 현재 카운트 출력, 94 이상일 때는 주사위를 한 번만 더 돌리면 100이 나오므로 카운트+1 출력, 그 외의 경우에만 다시 deque에 넣도록 구현하였다.

이렇게 구현하면 매번 deque에 넣을 때도 100을 초과하는지 체크하지 않아도 되기 때문이다.

문제는 10X10의 2차원 그래프인 것처럼 나왔지만 1차원 배열로 변환하여 생각하는 게 필요한 문제였다.

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://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/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번째 원소가 될 수 있다는 의미이다.

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

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

문제 설명에서도 잘 나와 있듯이 이진 트리를 순서대로 순회하여 출력하는 문제다.

만약 이진 트리에 대한 구현이나 순회가 잘 이해되지 않는다면 이전 포스팅을 보고 이해하길 바란다.

https://khsung0.tistory.com/24

문제 풀이

이진 트리와 순회에 대해 구현한 경험이 있다면 아주 쉽게 풀 수 있는 문제지만 경험이 없다면 아마 상당히 막막하게 느껴질 수 있는 문제라고 생각한다.

다행히 파이썬은 딕셔너리란 자료구조를 지원하므로 딕셔너리를 이용해서 아주 쉽게 구현해보겠다.

def preorder(trees,root):
    print(root,end="")
    if trees[root][0]!=".":
        preorder(trees,trees[root][0])
    if trees[root][1]!=".":
        preorder(trees,trees[root][1])

def inorder(trees,root):
    if trees[root][0]!=".":
        inorder(trees,trees[root][0])
    print(root,end="")
    if trees[root][1]!=".":
        inorder(trees,trees[root][1])

def postorder(trees,root):
    if trees[root][0]!=".":
        postorder(trees,trees[root][0])
    if trees[root][1]!=".":
        postorder(trees,trees[root][1])
    print(root,end="")

n=int(input())
trees={}
root="A"
for i in range(n):
    temp=input().split()
    trees[temp[0]]=[temp[1],temp[2]]

preorder(trees,root)
print()
inorder(trees,root)
print()
postorder(trees,root)

뭔가 코드는 많아 보이지만 하나씩 보면 별 거 없는 문제이다.

23번째 줄의 trees는 딕셔너리로 선언했고 문제에서 A가 루트라 했으므로 24번째 줄에서 루트를 A로 지정해준다.

그리고 25번째 줄에서 반복문을 돌면서 딕셔너리에 키와 값을 저장하는데 길이가 2인 리스트 형태의 값에서 0번째 인덱스는 왼쪽 자식 노드를 뜻하고 1번째 인덱스는 오른쪽 자식 노드를 뜻한다.

이때 자식 노드가 없다면 . 으로 쓴다는거만 주의하면 된다.

선언한 3개의 함수는 각 각 전위 순회, 중위 순회, 후위 순회하는 함수인데 이것도 상당히 간단하다.

현재 노드의 키를 출력하는 코드의 위치만 변경하면 되기 때문이다.

전위 순회를 기준으로 현재 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순이기 때문에 현재 노드의 키 출력, 왼쪽 자식 노드가 있다면 왼쪽 자식 노드로 재귀 호출, 오른쪽 자식 노드가 있다면 오른쪽 자식 노드로 재귀 호출 했다.

순서만 바꾸면 되기 때문에 이진 트리만 구현할 수 있다면 상당히 쉬운 문제였다.

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

문제 풀이

문제에서도 한눈에 알 수 있듯이 그래프 탐색을 하는 문제다.

문제를 간략하게 다시 설명하자면 0은 비어있는 땅, 1은 배추가 있는 땅이고 각 케이스마다 배추가 이어져있는 구역을 세서 출력하면 된다.

그래프를 탐색하는 방법은 스택을 쓰는지, 큐를 쓰는지에 따라 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)으로 나뉘는데 둘 다 시간 복잡도는 비슷하므로 편한 방식으로 구현하면 된다.

필자는 최단 거리를 찾을 때 BFS가 유리하므로 보통 BFS로 구현한다.

바로 전체 코드를 확인해 보자.

testcase=int(input())
dir=[[-1,0],[0,1],[1,0],[0,-1]]
for i in range(testcase):
    queue=[]
    res=0
    M,N,K=map(int,input().split())
    graph=[[0 for j in range(M)]for k in range(N)]
    for j in range(K):
        tempm,tempn=map(int,input().split())
        graph[tempn][tempm]=1
    for j in range(N):
        for k in range(M):
            if graph[j][k]==1:
                res+=1
                queue.append([j,k])
                graph[j][k]=0
                while len(queue)>0:
                    tempn,tempm=queue.pop(0)
                    for a in range(len(dir)):
                        dx=tempn+dir[a][0]
                        dy=tempm+dir[a][1]
                        if 0<=dx<N and 0<=dy<M and graph[dx][dy]==1:
                            graph[dx][dy]=0
                            queue.append([dx,dy])
    print(res)

1번째 줄은 테스트 케이스만큼 반복하기 위한 변수이고 2번째 줄은 각 노드에서 탐색 방향(위, 오른쪽, 아래, 왼쪽)을 묶어놓은 리스트이다.

이렇게 방향을 리스트로 묶으면 4가지 방향을 탐색할 때 반복문으로 해결할 수 있다는 장점이 있기에 꼭 잊지 말길 바란다.

대부분은 4가지 방향이지만 가끔 대각선도 고려하는 8가지 방향 문제도 있는데 단순하게 방향을 고려해서 8개의 리스트를 넣으면 된다.

4번째 줄의 queue는 큐를 사용함으로써 BFS 방식을 쓰기 위해 선언한 리스트이다.

가끔 리스트를 큐 방식으로 쓸 때 시간 초과가 나는 경우가 있는데 이는 pop() 함수에서 마지막 원소부터 탐색하기 때문에 첫 번째 원소를 제거하기 위해서는 O(n)의 시간 복잡도가 걸리기 때문이다.

그럴 경우엔 deque 모듈을 사용하면 O(1)로 첫 번째 원소에 삽입하고 삭제할 수 있다.

8번째 줄은 배추의 위치를 갱신하는 반복문이고 11번째 줄부터는 그래프를 전체 탐색하면서 배추 구역을 카운트하는 반복문이다.

13번째 줄은 배추가 있을 경우 카운트를 하고 인접한 배추 구역을 0으로 바꾸는 작업이다.

보통 원본 그래프를 변경하지 않기 위해 visited로 그래프와 똑같은 크기의 리스트를 선언하고 방문한 노드인지 아닌지 체크하여 중복된 방문을 방지하는데 해당 문제에서는 단지 배추 구역만 세면 되므로 원본 리스트를 변경해도 상관없어서 아예 0으로 바꿨다.

또한 20, 21번째 줄에서 탐색할 노드의 위치를 계산하여 따로 변수에 저장하는 이유는 미리 값을 저장해놔야 그래프 크기 안인지 배추가 있는 노드인지 체크할 때 불필요한 연산 횟수를 줄일 수 있기 때문에 값을 저장하는 것을 추천한다.

탐색 방향을 고려할 필요도 없고 단지 구역만 세면 되기 때문에 그래프 문제 중에서도 꽤 쉬운 편에 속한다고 생각한다.

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

문제 풀이

문제를 좀 더 쉽게 설명하자면 길이가 N개인 수열이 있는데 여기서 두 개를 뽑아 서로 곱한 값을 모든 경우의 수에서 다 더한 뒤 1000000007로 나눈 값을 출력하라는 뜻이다.

즉, 수학의 조합(Combination)을 떠올리면 된다.

하지만 제한 조건을 잘 봐야한다.

수열의 길이는 최대 500000(50만)이 될 수 있으며 평소 조합을 구하는 방식대로 첫 번째 원소부터 완전 탐색, 두 번째 원소부터 완전 탐색 ... 이렇게 반복하면 O(n^2)의 시간 복잡도가 걸리므로 시간 초과가 날 수밖에 없다.

따라서 어떻게 해야되나 고민을 해본 결과 예제에서 힌트를 얻을 수 있었다.

예제는 '1 x 2 + 2 x 3 + 1 x 3 = 11' 이렇게 있었다.

이걸 원래 조합 구하는 방식으로 순서를 조금 바꿔보면 '1 x 2 + 1 x 3 + 2 x 3 = 11' 이렇게 나타낼 수 있고 조금만 더 이해하기 쉽게 바꾸면 '1 x (2 + 3) + 2 x 3 = 11' 이렇게 나타낼 수 있다.

즉 문제가 원하는 답은 각 원소와 해당 원소의 뒷 원소들의 합을 곱하고 이를 다 더한 값에 1000000007로 나눈 결과를 원하는 것이었다.

이렇게 하면 처음 수열의 합을 구할때 O(n), 수열 탐색할 때 O(n), 총 O(n)의 시간 복잡도가 걸리므로 시간 초과가 나지 않을 것이다.

다음은 전체 코드다.

n=int(input())
num_list=list(map(int,input().split()))
sum_list=sum(num_list)
res=0
for i in num_list:
    sum_list-=i
    res=(res+i*sum_list)%1000000007
print(res)

원리만 떠올린다면 구현 자체는 아주 쉬운 문제였다.

3번째 줄에서 sum() 함수는 O(n)의 시간 복잡도가 걸린다.

5번째 줄의 반복문에서는 해당 원소를 리스트의 합에서 빼주고 해당 원소와 리스트의 합을 곱한 값을 결과값(res)에 더하면서 1000000007의 나머지로 갱신하면 끝이다.

테스트 케이스를 이용하여 원리를 떠올리는 것이 중요한 문제인 것 같다.