Algorithm (19) 썸네일형 리스트형 [Algorithm] 탐색 Searching 탐색 범위를 반씩 좁혀가는 탐색 순차 탐색 Sequential Search : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음. 순차 탐색 소스코드 # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기) print("생성할 원소 개.. [Algorithm] 정렬 Sorting 정렬 sorting : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색 Binary Search가 가능해진다. 정렬은 이진탐색의 전처리 과정이기도 하다. '알고리즘의 효율성' 측면에서 정렬은 중요하다. 선택 정렬 selection sort : 매번 '가장 작은 것을 선택'한다. 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하여 정렬이 완료되는 것을 알 수 있다. 스와프(Swap): 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업. 파이.. [Algorithm] 복잡도 Complexity 복잡도 복잡도는 알고리즘의 성능을 나타내는 척도이다. 동일한 기능을 수행하는 알고리즘이 있다면 복잡도가 낮을수록 좋은 알고리즘이다. 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 중요하다. 따라서 최악의 경우의 시간 복잡도를 우선적으로 고려해야한다. Cf) Memorization 메모이제이션 : 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법 시간 복잡도와 공간 복잡도의 Trade-off 메모리를 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가.. [Algorithm] 알고리즘 설계와 분석의 기초 알고리즘 설계와 분석의 기초 알고리즘이란 문제를 해결하기 위한 단계적 절차를 말한다. 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다. 점근적 분석 점근적 분석이란 입력이 충분히 큰 경우에 대한 분석을 말한다. 컴퓨터는 빠른 처리 능력을 가지므로 입력의 크기가 작을땐 속도의 차이가 뚜렷하지 않다. 하지만, 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다. 좋은 알고리즘 = 성능이 좋은 = 효율적인 = 같은 시간에서 더 빠른 알고리즘이다. 알고리즘 표현법 순서도를 이용한 표현 여러 종류의 상자와 상자를 이어 주는 화살표를 이용해서 명령 순서를 표현 간단한 알고리즘은 쉽게 표현할 수 있지만, 복잡한 알고리즘은 표현하기 어려운 경우가 많.. [백준 4948] 베르트랑 공준 python 문제 풀이 처음에 입력받은 수에 대해서 숫자를 세는 방식으로 문제를 풀었는데 시간 초과가 되었다. 가장 큰 수(123456)까지 소수가 아닌지 기억한 후 입력받은 구간에 대해서 소수의 개수를 세는 방식으로 바꿔서 통과되었다. 통과된 풀이 sosu = [0] * (123456 * 2 + 1) def isPrime(num): if num == 1: return False for i in range(2, int(num ** 0.5) + 1): if num % i == 0: return False return True for i in range(2,len(sosu)): if isPrime(i): sosu[i] = 1 while True: n = int(input()) if not n: break print(su.. [백준 1929] 소수 구하기 (+에라토스테네스의 체) python 문제 풀이 시간초과가 나와서 구글링해보니 에라토스테네스의 체를 이용해야 통과되는 문제이다. 에라토스테네스의 체 : 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 숫자의 제곱근 까지만 약수의 여부를 검증하는 방식이다. 1. 먼저 2를 제외한 2의 배수를 제거 2. 3을 제외한 3의 배수 제거 3. 5를 제외한 5의 배수 제거... 이런식으로 모든 구간에 대해 반복하면 소수만 남는다. 이것은 자신의 제곱근 까지만 약수의 여부를 검증하는 식으로 구현할 수 있다. (구글링을 통해 알게됨) 통과 된 풀이 def isPrime(num): if num == 1: return False else: for i in range(2, int(num ** 0.5) + 1): if nu.. [백준 11653] 소인수 분해 python 문제 풀이 통과된 풀이 가장 작은 수부터 시작 나누어 떨어지지 않을 때 까지 그 수로 나누어주면 그 수의 배수는 앞으로 체크안될테니까 소수로만 나누어짐 N = int(input()) m = 2 # 1은 소수가 아니니까 2부터 시작 while N != 1: if N % m == 0: print(m) N = N // m else: m += 1 시간 초과 풀이 n보다 작은 수 중 가장 작은 소수를 찾아서 계속 나누어주는 방법 error를 두어 소수가 아닌 경우 체크 n = int(input()) # 소인수 분해할 변수 num = 1 # 소수를 저장할 변수 # n보다 작은 수 중 가장 작은 소수부터 찾아 나가기 while n >= num: # num보다 n이 커지면 루프 종료 num += 1 # 1은 소수가 아.. [백준 1011] Fly me to the Alpha Centauri 파이썬 python 문제 나의 풀이 소스코드 t = int(input()) for _ in range(t): x, y = map(int, input().split()) distance = y - x # y와 x사이의 거리 tmp = 0 # 이동 거리 cnt = 0 # 공간 장치 이동 횟수 moving = 0 # 반복 횟수 while tmp < distance: cnt += 1 if cnt % 2 != 0: moving += 1 tmp += moving print(cnt) 해설 백준 단계별 풀어보기 하는 중 안풀려서 며칠 고민했던 문제다. 수학 유형은 직접 나열해보면서 규칙성을 파악해야한다. 특히, 문제에서 종료조건을 제대로 설정안해서 처음에 비효율적이고, 시간 초과가 나오는 코드를 만들었다. 1. 공간 장치 이동 횟수는 (.. 이전 1 2 3 다음
