컴퓨터공학 💻 도서관📚

원소가 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를 이용해서  특정..

DFS 동작 예시:  스택 자료구조인 경우방문 기준: 번호가 낮은 인접 노드부터     DFS 코드 예제 :  재귀함수를 사용한 경우(재귀함수로 구현하고 노드 방문 순서를 출력한 예시)  일반적으로 그래프 문제에서는 노드의 번호가 1번부터 시작하기 때문에 그래프를 초기화할 때 인덱스 0에 대한 내용은 비워두고 1번 인덱스부터 채운다 그렇기에 방문여부를 확인하는 리스트의 요소 개수를 노드 개수보다 1 높은 수로 선언하기  2차원 리스트를 선언할 때 숫자들을 작은 수부터 차례대로 써서재귀함수를 통해 우리가 원하는 대로 출력이 되게 만들 수 있었다.       자바 ArrayList 는 특정 인덱스에 접근하기 위해 상수시간이 소요되기 때문에 일반 배열보다 더 좋다ArrayList를 중첩된 형태로 이용해서 그래..

재귀함수 : 자기 자신을 호출(반환)하는 함수 재귀함수는 종료 조건을 꼭 명시해야 한다  재귀함수 예제 : 팩토리얼, 최대공약수 계산 def factorial(n): # 팩토리얼 계산 if n == 1: return 1 return n * factorial(n-1)N = int(input())print(factorial(N))      모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다  컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓입니다. 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많습니다재귀함수를 이용하여 DFS를 더 간결하..