삽입 정렬이란? - 처리되지 않은 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입하는 정렬 알고리즘. - 필요할 때만 위치를 바꾼다. - 데이터가 거의 정렬되어 있을 때 엄청 효율적이다. # 삽입 정렬 numbers = [3, 5, 7, 6, 4, 19, 2, 10, 8] # 0 위치에 있는 항목은 정렬이 되어있다고 가정. for i in range(1, len(numbers)): # i번째 숫자와 그 앞의 숫자들과 비교 for j in range(i, 0, -1): # 뒤의 숫자가 더 작으면 앞과 바꿈. if numbers[j - 1] > numbers[j]: numbers[j - 1], numbers[j] = numbers[j], numbers[j - 1] else: break print(n..
선택 정렬이란? -> 매번 '가장 작은 것'을 선택하는 알고리즘. -> 앞에서부터 차례대로 가장 작은 숫자로 채워나가는 기법이다. -> 가장 작은 숫자를 만나면 그 인덱스와 기존 앞의 인덱스를 바꿔주는 방식을 사용한다. -> 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복. # 선택 정렬 numbers = [3, 7, 1, 9, 11, 10, 5, 4, 2] for i in range(len(numbers)): # 현재 위치(i)와 바꿀 가장 작은 숫자의 인덱스 min_index = i # i까지는 이미 정렬 됐으므로 그 다음부터 검사 for j in range(i + 1, len(numbers)): if numbers[min_index] > numbers..
DFS란? -> 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. DFS의 특징 - 스택 자료구조(또는 재귀 함수)를 이용한다. DFS의 동작 과정 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 노드를 스택에 넣고 방문 처리를 한다. 2-1. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 2번의 과정을 수행할 수 없을 때까지 반복한다. # 재귀함수를 이용한 dfs구현 def dfs(graph, v, visited): # 현재 노드를 방문처리 visited[v] = True print(v, end=" ") # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 # 해당 노드의 행의 노드 ..
운영체제의 의미 -> 컴퓨터 하드웨어의 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층 협의의 운영체제(커널) -> 일반적인 의미 -> 운영체제의 핵심 부분으로 메모리에 상주하는 부분 -> 좁은 의미의 운영체제 광의의 운영체제 -> 커널 뿐 아니라 각종 주변 시스템 유틸리티를 포함한 개념 -> 넓은 의미의 운영체제 운영체제의 목표 -> 컴퓨터 시스템의 자원을 효율적으로 관리(자원관리자) (프로세서, 기억장치, 입출력 장치 등의 효율적 관리) -> 컴퓨터 시스템을 편리하게 사용할 수 있는 환경을 제공 - 각 프로그램은 가상 머신에 의해 자신의 프로그램만 실행되는 듯하게 보인다. - 하지만 이는 운영체제가 자원을 잘 분배해서 그렇게 보이게 하는 것. 운영체제의 분류 ..
그래프란? 노드와 간선으로 이루어진 자료구조 그래프의 종류 - 무방향 그래프(Undirected Graph): 방향성이 없고 노드(정점)이 연결된 그래프 - 방향 그래프(Directed Graph): 무방향 그래프에서 방향성이 추가된 그래프 - 완전 그래프(Complete Graph): 각 정점에서 다른 모든 정점을 연결하여 최대 간선 수를 가진 그래프 -> 정점이 n개인 무방향 그래프에서는 최대 간선 수 = n(n-1)/2 -> 정점이 n개인 방향 그래프에서 최대 간선 수 = n(n-1) - 가중(치) 그래프(Weight Graph): 간선에 가중치를 담아서 표현(방향 여부 상관X) - 부분 그래프(Sub Graph): 일부 정점과 간선으로 구성된 그래프(가중치 그래프에서 조금 떼어낸 그래프) 그래프의..
테이블 자료구조란? -> 데이터가 키-값 형태로 저장된 구조 테이블 자료구조의 특징 - key를 이용해 원하는 데이터를 찾을 수 있다. - key는 중복될 수 없고 의미있는 값을 가진다. - 탐색 연산은 O(1)의 시간복잡도를 가지지만 메모리의 효율성이 낮고 적용 범위가 제한적이다. - 사전(dictionary)구조 혹은 맵(map)이라고 함. supermarket = {"bread": 1, "juice": 5, "snack": 18} # key 있는지 검사 if "snack" in supermarket: print("snack!") # value 있는지 검사 if 5 in supermarket.values(): print("juice!") # key 출력 print(supermarket.keys()) ..
우선순위 큐란? -> 우선순위를 근거로 데이터를 뽑는 구조 우선순위 큐의 특징 - 들어간 순서와 나가는 순서가 아무런 상관이 없다. - 데이터를 뽑을 때 우선순위를 근거로 뽑는다. - 우선순위를 판단하고 결정하는 건 프로그래머이다. - 같은 우선순위를 가진다면 먼저 들어온 원소를 처리한다. - 보통 힙을 통해 우선순위 큐를 구현한다. (배열이나 링크드리스트는 best와 worst의 편차가 크기 때문) 힙이란? - 완전 이진 트리(Complete Binary Tree)이다. - 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap) 작아야(Min Heap)한다. - 힙으로 우선순위 큐를 구현할 때는 노드에 저장된 값을 우선순위로 본다. - 힙은 루트 노드에 우선순위가 높은(숫자가 큰-Max ..
트리란? -> 계층적 관계를 표현하는 자료구조 -> 하나의 중심을 기점으로 뻗어나가는 구조 트리 용어 - 노드(Node): 트리의 구성 요소(기본 단위) => A, B, C, D, E, F, G, H, I, J - 간선: 노드와 노드를 연결하는 선 - 루트 노드(Root): 트리 구조에서 최상위에 존재하는 노드 => A - 단말 노드(Leaf Node): 아래로 또 다른 노드가 연결되어 있지 않은 노드 => H, I, J, F, G - 내부 노드: 단말 노드를 제외한 모든 노드 => A, B, C, D, E - 서브 트리(Sub-tree): 트리에서 일부를 떼어낸 트리 - 레벨(level): 루트 노드를 기준으로 레벨 0부터 자식 노드로 가면서 레벨이 증가한다. - 높이: 최대 레벨의 값(0부터 셌을 때..
