무향향수

시간 복잡도(Time Complexity)알고리즘의 효율성을 평가하는 기준을 말한다.알고리즘이 실행되는 데 걸리는 시간을 입력 크기 n에 따라 나타낸 것이다.기본적인 시간 복잡도 종류O(1) - 상수 시간 (Constant Time)입력의 크기와 관계없이 일정한 시간이 걸리는 알고리즘O(n) - 선형 시간 (Linear Time)입력의 크기 n에 비례하여 시간이 걸리는 알고리즘O(n^2) - 이차 시간 (Quadratic Time)입력 크기의 제곱에 비례하여 시간이 걸리는 알고리즘O(log n) - 로그 시간 (Logarithmic Time)입력 크기가 커질수록 실행 시간이 느리게 증가하는 알고리즘O(n log n) - 선형 로그 시간 (Linearithmic Time)선형 시간과 로그 시간이 결합된 알..

1. enumerate() 사용하기- enumerate를 사용하면 반복문에서 인덱스와 값을 쉽게 사용할 수 있다.a = [i for i in range(4)]# 변수를 enumerate()로 감싸 사용한다.for idx, num in enumerate(a): if num > 2: a[idx] = 0# 배열 a에 있는 값이 2보다 작으면 0으로 변경하는 코드  2. for문 대신에 list comprehension 사용하기# [expression for item in iterable if condition] 형식으로 작성한다.data = [i for i in range(10) if i % 2 = 0]# 짝수만 data 배열에 저장된다. 3. Generator comprehension 사용하기gene..

파이썬 힙 자료구조 heapqheapq 모듈을 사용하여 priority queue를 구현할 수 있다.import heapqheapq.heappush(heap, item) # item을 heap에 추가heapq.heappop(heap) # heap에서 가장 작은 원소를 pop하고, 비어 있는 경우 idexError가 호출됨heapq.heapify(x) # 리스트 x를 heap으로 변환 최대힙https://www.acmicpc.net/problem/11279import sysimport heapqN = int(sys.stdin.readline())max_heap = []for i in range(N): x = int(sys.stdin.readline()) if x == 0: if ma..

더보기처음 파이썬으로 문제를 풀었을 때 채점 시간이 엄청 오래 걸리더니 결국 시간초과가 나버렸다. 언제나처럼 이중 for문을 사용한 것이 문제였고 문제를 해결한 다른 블로그를 참조하여 코드를 작성하였다. 이중 for문이 쉽고 좋은데.. 시간이 너무 오래 걸려서 슬프다. 이전까지는 이중 for문이 만능이었는데 시간복잡도나 자료구조, 알고리즘을 배우고 코드를 작성해보니 최악이라는 생각이 들기도 한다. 더 열심히 대응방안을 찾아봐야겠다.   처음에 작성했던 코드 (시간 초과)import sysN = int(sys.stdin.readline()) # 수 입력받기a = [2]for i in range(N, 1000000000000): # while문 대신 for문을 사용 x = 1 for j i..

더보기코딩테스트 백준 1920번: 수 찾기 문제를 풀다가 sys를 사용했음에도 시간초과가 떠서 통과한 다른 사람들의 코드를 참조하였다. 파이썬의 경우 대부분의 사람들이 이진 탐색(이분 탐색)을 사용하여 코드를 작성하였다. 이를 참조하여 코드를 작성하고 테스트를 통과했다. 이전까지 알고리즘을 배울 때는 잘 쓰이지도 않는데 왜 배워야하는지 의문점이 많았는데 코딩테스트에 직접 활용해보니 유용하다는 생각이 들었다.  처음에 작성했던 코드 (시간 초과)import sys# 각각 int와 list로 입력받아 저장하기N = int(sys.stdin.readline())A = list(map(int, sys.stdin.readline().split()))M = int(sys.stdin.readline())B = lis..

목차🍮 1. rstrip() 개행문자 제거 2. list() 문자열을 배열로 3. 백준 10102번 해설 => rstrip(), list() 예시 🍮 1. rstrip() 파이썬에서 사용되는 rstrip()의 경우 개행문제를 제거해준다. 예를 들어 sys.stdin.readline()으로 문자열을 입력받아 배열로 바꿔주려고 하는데, 배열에 '\n'이 저장되어 원하는 값을 얻을 수 없는 경우, 문자열을 배열로 바꾸기 전에 rstrip()를 사용하여 개행문자를 삭제해준다. 🍮 2. list() list()의 경우 문자열을 배열형식으로 변경해준다. 예를들어 문자열 'ABC'가 있을 때, list()를 사용해주면 ['A', 'B', 'C'] 배열로 형식이 바뀐다. 🍮 3. 백준 10102번 import sys ..