Computer Science7 동빈북 6장 개념정리 정렬(Sort) 정렬의 사전적 의미는 말그대로 요소를 순서대로 놓는것이다. 예를들어 2,5,10,9,8 이라는 숫자들이 나열되어 있을때, 2, 5, 8, 9, 10 등으로 말이다. 정렬에는 굉장히 여러가지 종류가 있는데, 삽입정렬, 선택정렬, 버블정렬, 퀵정렬, 힙정렬, 합병정렬 등 여러가지가 있다. 이 정렬들이 어떻게 구현되어 있고(어떤 방법을 이용하여 정렬했는지) 시간복잡도가 얼마나 되며 왜 그런 복잡도를 가지는지를 아는 것은 매우 중요하다. (사실 나도 삽입 정렬이랑 선택 정렬은 아직도 햇갈린다.) 그래서 정리를 하려고 한다. 선택정렬 저장된 데이터의 요소 중 최소값을(또는 최대 값) 찾고 데이터의 요소 중 첫번째와 뒤집는 방식이다. 삽입정렬 저장된 데이터의 요소를 하나씩 찾아서 올바른 위치에 삽입 해준다. 즉, .. 2020. 11. 13. 동빈북 5장 내용 정리 DFS/BFS DFS/BFS는 결국 그래프를 탐색하는 방법이다. 그래프는 아래 그림처럼 노드와 간선으로 이루어 진다. DFS/BFS는 간선으로 연결된 노드를 탐색하는 방법이다. 즉, 인접해 있는 노드를 탐색하는 알고리즘이다. 나타내는 방법은 인접 행렬 방식과 인접리스트 방식이다. 하지만 방문 순서가 다르다. DFS는 트리에 연결된 노드를 쭉 따라서 깊이에 따라서 탐색하는 방식이고 BFS는 이름 그대로 대상 노드에 연결된 모든 노드를 우선 탐색하는 방식이다. DFS는 Stack으로 BFS는 큐로 구현한다. DFS의 경우 재귀함수가 Stack으로 동작하기 때문에 재귀함수를 이용하여 직관적으로 구현할 수 있다. DFS를 응용한 백트래킹이라는 알고리즘도 존재한다. 트리로 동작이 되었다면 트리의 깊이를 따라서 탐색하다가 그 가.. 2020. 11. 13. 동빈북 3장 그리디 내용 정리 Greedy라는 단어는 한국어로 번역하면 욕심쟁이 기법이다. 단어에서 느껴지는 뉘양스 그대로 그 상황에서만 최선이 되는 경우를 고르는 알고리즘인데 아무생각없이 보면 그 자리에서 가장 유리한 선택을 하는것이 최적의 답일 것 같다고 생각 할 수 있지만.. 인생을 보더라도 항상 그 순간에 최적의 선택을 한다고 그것이 모두 모아놓고 봤을땐 최선이 아니다. 알고리즘도 어찌보면 인생과 비슷하기 때문에 문제마다 전체적으로 보는 것이 중요하다.(물론 인생이 더 복잡하지만..) 아무튼 현재의 선택이 나중에 끼칠 영향을 고려하지 않는다. 그 예제로는 예를들어 배열이 6 10 5 30 6 이렇게 있다고 했을때 연속된 숫자를 고르지 못해 만약 그냥 당장 배열 요소중 하나만 본다고 가정하면 답은 17이 될 것이다. 하지만, 알.. 2020. 11. 3. 이전 1 2 다음
