728x90 TIL - 프로그래밍/Python 알고리즘198 파이썬 시간 복잡도 in 연산자 list, tuple Average: O(n) 하나하나 순회하기 때문에 데이터의 크기만큼 시간 복잡도를 갖게 됩니다. set, dictionary Average: O(1), Worst: O(n) 내부적으로 hash를 통해서 자료들을 저장하기 때문에 시간복잡도가 O(1)가 가능하고 O(n)의 경우에는 해시가 성능이 떨어졌을(충돌이 많은 경우) 때 발생합니다. 2023. 4. 2. 파이썬 구간 합 구하기 (accumulate) accumulate 누적된 합을 뽑아준다. for문을 활용하여 더해주는 것보다 확실히 빠르다 from itertools import accumulate a = [1,2,3,4,5] accu_a = list(accumulate(a)) print(accu_a) # [1, 3, 6, 10, 15] 2023. 4. 2. 이것이 취업을 위한 코딩 테스트다 CHAPTER 5 DFS/BF 탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 데이터를 표현하고 관리하고 처리하기 위한 구조 오버플로 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생 즉, 저장 고안을 벗어나 데이터가 넘처흐를 때 발생 언더플로 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태 DFS Depth-Frist Search 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 Stack O(N) BFS Breadth Frist Search 너비 우선 탐색 가까운 노.. 2023. 3. 24. [백준] 18405. 경쟁적 전염 - Python (BFS 사용 X) https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 접근법 (X,Y)에 바이러스 i가 전염되었다 == 바이러스 i가 (X,Y)에 가장 먼저 도착하였다. 그러므로, S초 후 (X,Y)에 존재하는 바이러스 == S초 이내에 가장 먼저 도착한 바이러스 i 바이러스 i와 (X,Y)와의 거리를 각각 구한 후 거리가 S 이내이면서 거리가 가장 가깝고 바이러스 번호가 가장 작은 것이 답 코드 import sys input = sy.. 2023. 3. 23. 이것이 취업을 위한 코딩 테스트다 CHAPTER 4 구현 구현 완전 탐색 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 문제에서 제시한 알고리즘을 한단계씩 차례대로 직접 수행 알고리즘 팁 리스트를 여러개 선언하고, 그중에서 크기가 1000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 기억 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다. 알고리즘 문제를 풀 때는 확인(탐색)해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색 사용 문제 2. 왕실의 나이트 ''' Chapter 4. 왕실의 나이트 접근법 1 이동할 수 있는 경우의 수가 8가지 모두 다 확인 ''' import sys i.. 2023. 3. 21. 이것이 취업을 위한 코딩 테스트다 CHAPTER 11 그리디 문제 Q 01. 모험가 길드 ''' Chapter 11. 모험가 길드 접근법 1 공포도가 낮은 모험가부터 그룹을 결성해보기 그룹을 최대한 많이 만들어야하므로 그룹 내 사람 수 가 적어야 함 그룹 결성 조건 == (마지막에 그룹에 들어간 사람의 공포도)가 (그룹 사람 수)보다 작을 때 ''' import sys input = sys.stdin.readline # 모험가의 수 N = int(input()) # 모험가의 공포도 fear = list(map(int,input().split())) fear.sort() answer = 0 cnt = 0 for i in fear: cnt += 1 # 그룹이 결성이 되는가? == 방금 그룹에 들어간 사람의 공포도가 그룹사람수보다 작아야 결성 if cnt >= i: answ.. 2023. 3. 21. 이전 1 2 3 4 5 6 7 ··· 33 다음 반응형