컴퓨터공학 💻 도서관📚

파이썬에서 제공하는 기본 정렬 라이브러리는  ( sort() )병합 정렬을 기본으로 한 하이브리드 형식의 정렬 알고리즘을 제공하고 있다.        자바에서 내림차순 정렬을 할 때는 Collections 라이브러리의 reverseOrder() 메서드를 사용하기

계수 정렬은 가장 작은 데이터부터 가장 큰 데이터까지의 모든 범위를 포함할 수 있는 크기의 배열을 만들어야 하기 때문에 상대적으로 공간 복잡도가 높지만, 조건만 맞다면 다른 방법보다 더 효율적인 알고리즘이다 계수 정렬은 데이터를 정수 형태로 표현할 수 있을 때 사용 가능하다. 계수 정렬은 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 크기의 리스트를 선언해야 한다       계수 정렬 코드에서 중첩 for문을 보면 바깥쪽 for문이 K 번 돌아가고 안쪽 for문은 수행 횟수가 N 번이므로  시간복잡도는 O(K + N) 이다  계수정렬은 동일한 값을 가지는 데이터가 여러 개 나올 때 효과적이다.

원소가 1개인 경우에는 그대로 종료한다     1. 리스트 슬라이싱과  2. 리스트 컴프리헨션을 활용

퀵 정렬 표준 라이브러리를 이용하는 경우에는 기본적으로 NlogN 을 항상 보장한다    퀵 정렬 동작 예시    아주 중요!!! :  위치가 엇갈릴 때는 '피벗'과 '작은 데이터'의 위치를 서로 변경한다.    퀵 정렬의 시간 복잡도     퀵 정렬은 이미 정렬된 배열에서 최악의 시간 복잡도를 가진다(우측에서부터 0보다 작은 데이터가 없기 때문이다)그래서 결국 위치가 엇갈려서 0이 자기 자신과 위치를 바꾸는 상황이 된다그리고 0과 나머지 숫자들의 묶음으로 분할이 된다그 후 계속 가장 작은 수와 나머지 숫자들의 묶음으로 분할이 되서 시간 복잡도가 O(N^^2) 이다.

선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다   내가 쓰던 선택 정렬과 본질은 같지만 형태만 다른 코드본질 :  0번째 인덱스에 가장 작은 수를 넣기여기선 가장 작은 수가 있는 인덱스 번호를 찾는 방식이다 파이썬에서 변수 스와프 하는 방법array[i],  array[min] = array[min],  array[i]   c++ 표준 라이브러리에서 제공하는 swap 함수     삽입 정렬 처리되지 않은 데이터를 하니씩 골라 적절한 위치에 삽입한다 (데이터를 하나씩 확인하면서 이 데이터가 어느 위치에 들어가는게 맞는지 매번 계산한다) 선택정렬에 비해 구현나이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다     i 번째 요소가 좌측..

queue.append((x,y)) :  2차원 튜플을 큐에 추가return graph[n-1][m-1] :  print(bfs(0,0))  (0,0) 을 대입했기 때문에  graph 배열 인덱스도 [n-1][m-1] 처럼 - 1 해줘야 한다     실제로는 bfs 함수가 main 함수 위에 있어야 한다

(파이썬에서는 함수에 사용된 변수or 배열이 함수보다 아래에 있는데 정상적으로 되더라)    ( ex. graph[][] )  (C언어에서는 함수 안에 있는 변수들은 전역변수로 따로 선언하지 않은 이상 다 지역변수여서 다 각각 선언을 해줘야 한다)(C언어에서는 함수에서 main함수에 있는 변수, 배열을 사용하고 싶으면 포인터를 이용해서 매개변수로 받아야 된다)   dfs(x-1, y) 포함 4개 방향 코드 -->  코드 수행하고 혼자 반환하고 끝 --> [ 이 반환은 dfs(i, j)의 반환이 아니기에if dfs(i,j) == True:  이 코드에 영향을 주지 않는다 ] 대신 인접 노드의 값이 0이면 1로 바꾸는 효과가 있음 -->  그래서 그래프 형태에서 0이 인접한 덩어리를 1번만 셀 수 있다(와...

BFS 유형은 최단 거리 유형의 문제에 활용되기도 한다      모든 작업이 끝나면 큐 안은 비워져 있다.     BFS 코드 예제 :  DFS 와 마찬가지로 BFS 도 0번 인덱스를 비워두고, visited 배열의 요소를 9개로 선언한다   파이썬 예제queue = deque([start])   # 시작 노드를 큐에 넣어준다  파이썬 deque 를 출력해보면  deque([1,2])  이런 형태로 출력이 된다.  (큐의 요소 하나가 리스트 하나인 느낌) while queue   # 큐가 참일 때 --> 큐가 0이 아닐 때 --> 큐가 비어있지 않을 때 (popleft 함수는 반환까지 하는 함수인듯)     c++ 예제c++ 에서 인접리스트 방식으로 그래프를 구현하고자 하면 vector를 이용해서  특정..