목록Computer Science/Algorithm (10)
재 현
정렬 알고리즘은 데이터의 순서를 재배치하여 정렬된 순서로 데이터를 나열하는 알고리즘입니다. 데이터를 효율적으로 정렬하기 위해 사용되며, 다양한 종류의 정렬 알고리즘이 존재합니다. 문제의 크기, 데이터의 특성, 정렬의 안정성(stability), 메모리 사용량 등을 고려하여 적절한 정렬 알고리즘을 선택하는 것이 중요합니다. 버블 정렬 (Bubble Sort): 인접한 두 개의 요소를 비교, 시간 복잡도는 최악, 평균, 최선 모두 **O(n^2)**입니다. 선택 정렬 (Selection Sort): 최솟값을 찾아 앞으로, 시간 복잡도는 최악, 평균, 최선 모두 **O(n^2)**입니다. 삽입 정렬 (Insertion Sort): 정렬되지 않은 요소를 적절한 위치에 삽입, 시간 복잡도는 최악, 평균의 경우 O..
알고리즘이 실행되는 데 소요되는 시간의 양과 메모리 양을 의미한다. 4가지 질문으로 알아보자. Q1. 시간 복잡도와 공간 복잡도가 무엇이고 왜 중요한가? 시간 복잡도는 알고리즘이 실행되는 데 소요되는 시간의 양을 분석하는 개념입니다. 입력 크기에 대한 함수로 표현되며, 알고리즘의 실행 속도와 관련이 있습니다. 시간 복잡도를 분석하여 알고리즘의 효율성과 성능을 평가할 수 있습니다. 공간 복잡도는 알고리즘이 실행되는 데 필요한 메모리 공간의 양을 분석하는 개념입니다. 입력 크기에 대한 함수로 표현되며, 알고리즘이 사용하는 추가적인 메모리, 데이터 구조, 임시 변수 등을 고려합니다. 공간 복잡도를 분석하여 알고리즘의 메모리 사용량을 평가할 수 있습니다. Q2. 어떤 상황에서 시간 복잡도보다 공간 복잡도가 더 ..
문자열 문제 주의할점 1) 소문자,대문자 파악 2) 'a'~'z' 범위 slice 1. a[start:end] # start부터 end-1까지 item 2. a[start:] # start부터 list끝까지 item 3 a[:end] # 처음부터 end-1까지의 item 4. a[:] #리스트의 모든 item 5. a[:-1] # 맨 뒤의 item 6. a[-2:] # 맨 뒤에서부터 item 2개 7. a[:-n] # 맨 뒤의 item n개 빼고 전부 import string string.ascii_lowercase # 소문자 abcdefghijklmnopqrstuvwxyz string.ascii_uppercase # 대문자 ABCDEFGHIJKLMNOPQRSTUVWXYZ string.ascii_lett..
BFS ( 너비 우선 탐색) - 가까운 노드부터 우선적으로 탐색(최단거리) - 큐 자료구조 이용 1. 탐색노드를 큐에 삽입, 방문처리 2. 큐에서 노드를 꺼낸 뒤에 인접노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다 3. 더이상 큐에서 꺼낼 노드가 없을 때까지 반복한다. - 큐에서 꺼내 인접노드 파악 후 처리한다. #미로 탈출 최소거리 구하기, '1'로 안된 거리 BFS : 시작 지점에서 가까운 노드부터 차례대로 그래프 모든 노드를 탐색, 상하좌우 연결된 모든 노드거리가 1로 동일하다. step 1. 1찾기 step2. 1->2 1260, 2644, 2178, 6593, 5427(★), 3055(★), 2206(★), 7576, 7652, 5012, 1697, 16397, 9019(★), ..