코딩 테스트 (Python)/문법

선택 정렬이란? 제자리 정렬(in-place sorting) 알고리즘의 하나 - 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법 - 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다. 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다. 특징 장점..

버블 정렬이란? 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 - 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. - 선택 정렬과 기본 개념이 유사하다. 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 특징 장점 - 구현이 매우 간단하다. 단점 - 순서에 맞지 않..

용어 정리 정점: node 간선 : edge 두 node 를 잇는 요소 방향과 가중치를 가질 수 있음 그래프: 정점과 간선의 집합 서브 그래프: 기존 그래프의 정점 일부와, 간선 일부로 구성된 그래프 최소 신장 트리(Minimum Spanning Tree, MST)란? 최소 스패닝 트리 라고도 많이 불린다. 주어진 그래프의 모든 정점을 지나면서, 간선의 가중치 합이 최소가 되는 트리 그래프의 모든 정점을 포함하고 그래프의 일부 간선을 포함하며 사이클이 없는 (트리의 특징) 위 특징을 가진 서브 그래프 중 간선의 가중치 합이 최소인 트리 원본 그래프 간선에 가중치가 부여되어 있음 간선의 방향 여부에 따라 구하는 방법이 달라짐 코딩테스트에서는 간선의 방향이 없는, 무방향 그래프에 대해서만 나옴 정점이 n 개..

완전 이진 트리 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 트리 구조를 표현하는 방법은 직접 클래스를 구현해서 사용하는 방법이 있고, 배열로 표현하는 방법이 있다. 완전 이진 트리는 왼쪽부터 데이터가 쌓이게 되는데, 이를 순서대로 배열에 쌓으면서 표현할 수 있다. 8 Level 0 -> [8] 첫번째 레벨의 8을 넣고 6 3 Level 1 -> [8, 6, 3] 다음 레벨인 6, 3을 넣고 4 2 5 Level 2 -> [8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣는다. 완전 이진 트리의 높이 트리의 높이(Height)는, 루트 노드부터 가장 아래 리프 노드까지의 길이 이다. 예를 들어 다음과 같은 트리의 높이는..

BFS이란? BFS(Breadth First Search) 또는 너비 우선 탐색이라고 함 시작 정점으로부터 가까운 정점을 먼저 방문하는 그래프 탐색 방법 큐(queue)를 이용해 방문한 정점들을 차례로 저장하고 꺼냄 DFS와 BFS의 차이점 DFS 는 탐색하는 원소를 최대한 깊게 따라가야 한다. 이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 마지막에 넣은 노드를 꺼내서 탐색하면 된다. → 스택 BFS 는 현재 인접한 노드 먼저 방문해야 한다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. → 큐 구현 (Python) 1. 루트 노드를 큐에 넣는다. 2. 현재 큐의 노드를 빼서 visited 에..

DFS란? DFS(Depth-First Search) 또는 깊이 우선 탐색이라고 부름 그래프에서 깊은 부분을 먼저 탐색하는 알고리즘 스택 자료구조 또는 재귀 함수를 이용함 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조입니다. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다. 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다. 위 과정을 반복한다. 구현 (Python) from dfs_bfs.prac import dfs_recursive, dfs_stack # 테스트 코드 assert dfs_recursive(1, []) == [1, 2, 5, 6, 7, 3, 4] # dfs로 방문한 경우 assert dfs_stack(1) == [1, 4, 3,..