티스토리

성장의 발자취

검색하기

블로그 홈

성장의 발자취

kood-dev.tistory.com/m

godkoo 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

알고리즘 문제 풀이에 접근하는 방법 문제 접근 방법에 대해서 알고리즘에서 10의 8승 (10^8)이란? 일반적으로 연산을 10^8번하면 1초 정도로 생각합니다. 이것만으로 코테문제의 알고리즘을 추론할 수 있습니다. 시간 복잡도의 중요성 1부터 n까지 더하는 알고리즘이 있다고 가정하겠습니다. 1 + 2 + 3 + ... + n = ? 코드로 구현 한다면 forloop를 돌며 1부터 n까지 더하면 됩니다. def sum(n): answer = 0 for i in range(n+1): answer += i return answer 하지만 n이 크다면 ? 1 + 2 + 3 + ... + 10^8 = ? 위 코드는 n이 클 경우에는 시간이 매우 오래걸리기 때문에 수학적 공식을 구해서 계산해야 합니다. def sum(n): return n * (n .. 공감수 0 댓글수 0 2023. 8. 30.
이진 탐색(Binary Search) 이란 ? 이진 탐색 ? 이진탐색은 정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색하는 알고리즘 순차 탐색(Sequential Search) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 가장 기본적인 형태의 데이터 탐색 알고리즘 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소의 데이터를 확인해 가며 탐색한다. 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다 이진 탐색(Binary Search) 기본적으로 리스트 데이터가 정렬되어 있어야 사용할 수 있는 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는것이 특징이다. 이진 탐색은 한 번 확인할 때마다 확인할 원소의 개수가 절반씩 줄어든.. 공감수 0 댓글수 0 2023. 6. 14.
퀵 정렬 (Quick sort) 퀵정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정 한다. 퀵 정렬이 빠른 이유 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(N㏒N)를 기대할 수 있습니다. 너비 X 높이 = N * ㏒N = N㏒N 퀵 정렬의 시간 복잡도 퀵 정렬은 평균의 경우 O(N㏒N)의 시간 복잡도를 가집니다. 최악의 경우 O(N²)의 시간 복잡도를 가집니다. array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(arr.. 공감수 0 댓글수 0 2023. 6. 13.
재귀 함수란? 재귀함수란? (Recursive funciton) 자기 자신을 다시 호출하는 함수 예제 재귀함수를 호출합니다 문자열을 무한히 출력 보통 파이썬 인터프리터는 호출 횟수 제한이 있다. def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() 코드를 실행 하면 ‘재귀 함수를 호출합니다.’라는 문자열을 무한히 출력한다. 정의된 recursive_function()이 자기 자신을 계속해서 호출하기 때문에 무한루프에 빠지게 된다. 재귀 함수의 종료 조건 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 한다. 종료 조건을 명시하지 않으면 함수가 무한 호출될 수 있다. d.. 공감수 0 댓글수 0 2023. 6. 12.
DFS(Depth First Search)란? DFS(Depth First Search) 아래 글들은 이것이 코딩 테스트다의 강의를 기반으로 개인의 이해를 돕기 위해 정리한 글입니다. DFS 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 자료구조 혹은 재귀함수를 이용한다. 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 동작 과정 이해 하기 시작 노드인 ‘1’을 스택에 삽입하고 방문 처리를 합니다 스택의 최상단 노드인 ‘1’에 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8.. 공감수 0 댓글수 0 2023. 6. 11.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.