방구석 개발자의 놀이터

1. 배열(Array)의 특징 - 배열은 각 원소에 즉시 접근 가능 ex) array[0], array[1] 이런식으로 즉 O(1)내에 접근 가능 - 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 함 (최악의 경우 배열의 길이 N만큼 옮겨야 해서 O(N)의 시간복잡도) - 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 비효율적인 자료구조 2. 링크드 리스트 (LinkedList)의 특징 - 리스트는 크기가 정해지지 않은 데이터의 공간 - 리스트는 특정 원소에 접근하려면 포인터를 따라 탐색 (최악의 경우 모든 노드를 탐색해야 하므로 O(N)의 시간복잡도) - 리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경 (원소 삽입/삭제를 O(1)의 시간 복잡도) Arra..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. �� www.acmicpc.net 보통 처음 생각하는 풀이는 둗도 못한 사람의 수 N개의 이름을 담은 리스트를 입력받고 보도 못한 사람의 수 M개의 이름을 입력받으면서 듣도 못한 사람의 수 리스트에 이미 이름이 있으면 결과 리스트에 담아서 정렬을 하면 된다고 생각한다. 하지만!! 그렇게 하면 시간초과가 뜬다 (N,M이 최대 500000이기 때문에) 그래서 나의 풀이는 다음과 같다 n, m = map(int,input().s..

알고리즘에서 시간 복잡도는 굉장히 중요하다! 따라서 알고리즘 테스트를 볼 때 내 소스 코드가 얼만큼의 시간 복잡도를 가지고 있는지 확인해보는 것도 중요하다. import time array = [1,2,3,4,5]*100 start_time = time.time() #측정 시작 array.sort() #정렬 알고리즘 수행 end_time = time.time() #측정 종료 print("수행 시간 ::",end_time - start_time) #결과값 = 수행 시간 :: 3.0040740966796875e-05 위와 같이 정렬 알고리즘 수행을 예로 확인할 수 있다.