[모각코] 210710 Today I Learned

백준 #18234 당근 훔쳐 먹기

 

18234번: 당근 훔쳐 먹기 (acmicpc.net)

18234번: 당근 훔쳐 먹기

 

 

 

영양제(p) 크기는 최종적인 맛의 크기와 관련이 없을 거란 생각에 p는 w에 더해주는 값으로만 생각을 했는데 p의 크기가 포인트였다. 문제에 w<=p, N<=T 이 조건들이 힌트였는데 내가 모두 배제한채 문제를 풀었다 ㅜ 당근 개수보다 일수가 더 크고, 기존 크기(w)보다 영양제의 크기(p)가 더 크기 때문에 결국 영양제가 큰 것부터 선택하는 것이 최종적으로 가장 큰 값이 된다. 영양제순으로 당근을 정렬해준 후, greedy 기법으로 영양제 크기가 가장 큰 것부터 선택해나가면 된다.

 

이걸 알고서도 몇 번의 시간초과가 났는지 모르겠다. 이중 for문도 없고 O(n)이면 처리가 될 거 같은데 시간초과가 계속 났다. 후 

# 마지막날부터 제일 맛있는 거 선택
import sys

n, t = map(int, input().split())    # 당근 종류, 일수
sweet = []
for i in range(n):
    w, p = map(int, sys.stdin.readline().split())   # 기본 맛, 영양제
    sweet.append([p, w])     # 영양제, 기본 맛 순서로 리스트 저장 (리스트 형태로)

sweet.sort(reverse=True)	# 영양제를 기준으로 내림차순 정렬
max_eat = 0

for i in range(n):
    eat = sweet.pop(0)
    max_eat += eat[1] + (eat[0] * (t-(1+i)))
    
print(max_eat)

힌트를 알고 나서 처음 푼 게 이건데 타임아웃이 났다...... 설마 append 하면서 시간이 오래 걸리는 건가 싶어 검색을 해봤는데 append 하는 데 상수 시간밖에 안 걸린다고 한다...  input을 다른 방법으로 다르게 받아볼까 해서

sweet = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
sweet.sort(reverse=True, key=lambda p: p[1])    # 영양제를 기준으로 내림차순 정렬

이렇게도 짜봤는데 역시나 타임아웃이 났다. 🤬 그러다 순간 reverse가 오래 걸리나 싶어 검색해보니 reverse 하는 데 O(n) 시간이 걸린다는 거다. reverse를 빼고 해보니 드디어 맞았습니다!! 나왔다. 하... 근데 난 정렬하고 reverse를 한 게 아니라 정렬메소드 인수로 reverse=True 줘서 정렬 자체를 내림차순으로 하게 한 건데 그것도 오래 걸리나? 처음부터 정렬을 내림차순으로 하는 게 아니라 sort > reverse를 하나 .... 그래서 O(nlogn)+O(n) 시간이 걸려서 안 되는 건가... 아시는 분 댓글 좀 ㅠㅠ 라이브러리 보려 했으나 어떻게 보는 지 몰라서 실패.

 

어쨌든 몇 시간만에 드디어 풀었다. 그림 귀엽게 그려놓고 이렇게 스트레스 받게 하기 있냐 ^^

나는 시간초과에 좀 약한 것 같다. 알고리즘 첫 번째 과제 때도 시간초과 때문에 애먹었는데 이번에도 이거 푸는 데 몇 시간이 걸렸는지 모르겠다. 😥 한 번 알고리즘을 작성하면 다른 알고리즘이 잘 안 떠오른다 ㅠ 극복하자,, 

 

최종 알고리즘

# 마지막날부터 제일 맛있는 거 선택
import sys

n, t = map(int, input().split())    # 당근 종류, 일수
sweet = []
for i in range(n):
    w, p = map(int, sys.stdin.readline().split())   # 기본 맛, 영양제 
    sweet.append([p, w])     # 영양제, 기본 맛 순서로 리스트 저장 (리스트 형태로)

sweet.sort()	# 영양제를 기준으로 오름차순 정렬
max_eat = 0

for i in range(n):
    eat = sweet.pop()
    max_eat += eat[1] + (eat[0] * (t-(1+i)))
    
print(max_eat)

 

list 연산자의 시간 복잡도 (Big-O)

Operation	Example	Big-O	Notes
Index	l[i]	O(1)
Store	l[i] = 0	O(1)
Length	len(l)	O(1)
Append	l.append(5)	O(1)
Pop	l.pop()	O(1)	l.pop(-1) 과 동일
Clear	l.clear()	O(1)	l = [] 과 유사
Slice	l[a:b]	O(b-a)	l[:] : O(len(l)-0) = O(N)
Extend	l.extend(…)	O(len(…))	확장 길이에 따라
Construction	list(…)	O(len(…))	요소 길이에 따라
check ==, !=	l1 == l2	O(N)	비교
Insert	ㅣ.insert(i, v)	O(N)	i 위치에 v를 추가
Delete	del l[i]	O(N)
Remove	l.remove(…)	O(N)
Containment	x in/not in l	O(N)	검색
Copy	l.copy()	O(N)	l[:] 과 동일 - O(N)
Pop	l.pop(i)	O(N)	l.pop(0):O(N)
Extreme value	min(l)/max(l)	O(N)	검색
Reverse	l.reverse()	O(N)	그대로 반대로
Iteration	for v in l:	O(N)
Sort	l.sort()	O(N Log N)
Multiply	k*l	O(k N)	[1,2,3] * 3 » O(N**2)

출처 : 파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그 (wayhome25.github.io)

 

백준 #2606 바이러스

 

2606번: 바이러스 (acmicpc.net)

2606번: 바이러스

global count
count = -1
def dfs(adjList, n, v, visited):
    global count
    count += 1
    visited[v] = True
    for i in range(len(adjList[v])):
        w = adjList[v][i]
        if visited[w] == False:
            dfs(adjList, n, w, visited)
    

n = int(input())    # 컴퓨터 수
m = int(input())    # 선의 수
g = [[] for _ in range(n)]  # 네트워크
for i in range(m):
    v1, v2 = [int(i) for i in input().split()]
    g[v1-1].append(v2-1)
    g[v2-1].append(v1-1)      

visited = [False for _ in range(n)]
dfs(g, n, 0, visited)
print(count)

 

한 정점이 주어졌을 때 그 정점과 같은 연결 요소(connected component)에 속하는 모든 정점을 방문하는 너비우선탐색이나 깊이우선탐색의 성질을 알면 빠르게 풀 수 있는 문제다. 정점들을 방문하면서 방문한 정점들의 개수를 세어 모든 정점을 방문했을 때 최종 개수를 출력하기만 하면 된다.

 

그래프 형태를 떠올릴겸 쉬운 문제를 선택했는데 당연히 바로 맞을 줄 알았던 문제가 runtime error가 나서 당황스러웠다. 복붙을 잘못 했나 싶어 다시 복붙을 했는데 진짜 에러였다 ㅋㅋㅋㅋ 내 프로그램에선 잘 돌아가던 게 오류가 나니 원인을 알 수가 없었다 ㅜ

백준 런타임 에러에 대해 검색한 결과

1. 배열에 할당된 크기를 넘어서 접근했을 때
2. 배열 인덱스를 잘못 참조했을 때
3. 전역 배열의 크기가 메모리 제한을 초과할 때
4. 지역 배열의 크기가 스택 크기 제한을 넘어갈 때
5. 0으로 나눌 떄
6. 라이브러리에서 예외를 발생시켰을 때
7. 재귀 호출이 너무 깊어질 때
8. 이미 해제된 메모리를 또 참조할 때

이러한 이유로 에러가 난다 한다.

 

내 코드를 다시 보니 문제에서 정점이 1번부터 시작하는 것을 보고 내가 그래프의 크기를 n+1로 할당해준 것이 문제인 것 같았다. 0번은 그냥 비워둔 채로 1번 정점부터 개수만 세면 될 거라고 생각했는데 안 되나보다 ㅜ 그래프의 크기를 다시 n으로 주고 정점들을 연결할 때 정점 번호를 -1씩 해서 넣어주었다. 그리고 0번을 시작 정점으로 정점 개수를 세주었더니 에러 없이 잘 출력되었다.

 

runtime error는 언제나 당황스럽다. 저번 학기 알고리즘 과제 할 때도 내 프로그램에선 잘 돌아가던 게 구름에선 에러나서 교수님께 메일 보내고 그랬었는데 ,,  휴