🗒️ computer science (6)

1. 2022.06.28 [Python] 정렬(Sort) : 선택 정렬, 삽입 정렬, 버블 정렬, 퀵 정렬

   정렬(Sort) 정렬의 기본 정렬의 개념 정렬(Sort) : 자료들을 일정한 순서대로 나열하는 것 순서대로 나열할 때는 작은 것부터 나열하는 방법(오름차순)과 큰 것부터 나열하는 방법(내림차순)이 있다. 오름차순 정렬(Ascending Sort) : 작은 것부터 큰 순으로 나열된 방법 내림차순 정렬(Descending Sort) : 큰 것부터 작은 순으로 나열된 방법 정렬의 대표적인 예 : 사전 정렬 알고리즘의 종류 오름차순 정렬이든 내림차순 정렬이든 결과의 형태만 다를 뿐, 같은 방식으로 처리된다. 정렬하는 방법에 대한 알고리즘은 수십 가지이다. 이해하고 구현하기 쉽지만 속도가 느린 알고리즘 이해와 구현이 어렵지만 속도가 빠른 알고리즘 특수한 상황에서만 효율적인 알고리즘 메모리를 적게 사용하는 알고리즘..
2. 2022.06.05 [Python] 재귀 호출(Recursion)

   재귀 호출(Recursion) 재귀 호출의 기본 재귀 호출의 개념 재귀 호출(Recursion) : 자기 자신을 다시 호출하는 것 재귀 호출은 처음 접하면 상당히 혼란스럽지만 자료구조와 알고리즘을 학습할 때 매우 유용한 방법이므로 꼭 알아두어야 한다. 재귀호출의 동작 파이썬에서는 재귀 호출이 너무 많아지면 반복을 자동 종료한다. def openBox() : print("종이 상자를 엽니다.") openBox() openBox() # 처음 함수를 다시 호출 더보기 종이 상자를 엽니다. 종이 상자를 엽니다. ... RecursionError: maximum recursion depth exceeded while pickling an object 반환 조건을 추가할 경우, 무한 반복에서 빠져나올 수 있다. d..
3. 2022.06.04 [Python] 그래프(Graph)

   그래프(Graph) 그래프(Graph)의 기본 그래프의 개념 그래프(Graph) : 여러 노드가 서로 연결된 자료구조 루트에서 하위 노드 방향으로만 이어지는 트리와 달리, 여러 노드가 연결되어 있을 수 있다. 트리도 그래프의 일종이지만, 트리와 그래프를 구현하는 코드 등이 확연히 다르기 때문에 이 둘은 별도로 생각하는 편이 낫다. 그래프의 종류 그래프는 정점을 연결하는 간선의 방향성 여부에 따라 방향 그래프와 무방향 그래프로 나눈다. 간선에 가중치(Weight)를 부여하여 가중치 그래프도 만들 수 있다. 무방향 그래프 트리의 노드(Node)에 해당하는 용어가 그래프에서는 정점(Vertex)이다. 정점을 연결하는 선은 간선(Edge)이므로 그래프는 정점과 간선의 집합으로 볼 수 있다. 그래프에서 정점은 V..
4. 2022.06.04 [Python] 이진 트리(Binary Tree)

   이진 트리(Binary Tree) 이진 트리(Binary Tree)의 기본 이진 트리의 개념 트리(Tree) 자료구조는 나무를 거꾸로 뒤집어 놓은 형태이다. 트리의 맨 위를 뿌리(Root, 루트)라고 한다. 루트를 레벨 0으로 두고 나뭇잎(Leaf, 리프)에 해당하는 아래로 내려올 수록 레벨이 1씩 증가한다. 트리에서 각 위치를 노드(Node)라고 한다. 각 노드는 선, 즉 에지(Edge)로 연결되어 있다. 위 노드와 바로 아래 노드의 관계를 부모-자식 관계(Parent-Child Relationship)라고 한다. 자식 노드의 개수를 차수(Degree)라고 한다. 차수가 0인 노드를 리프(Leaf)라고 한다. 트리의 차수는 차수가 가장 높은 노드를 기준으로 정한다. 컴퓨터는 데이터를 0과 1로 표현하므..
5. 2022.06.03 [Python] 큐(Queue)

   큐(Queue) 큐(Queue) 선입선출(First In First Out, FIFO)의 특징을 갖는 자료구조 큐는 양쪽이 뚫려 있는 구조이다. 한쪽에서는 삽입만 진행되고, 다른 쪽에서는 추출만 진행된다. 큐에 데이터를 삽입하는 동작을 enQueue(인큐)라고 하며, 데이터를 추출하는 동작을 deQueue(데큐)라고 한다. 큐의 중요한 용어로 front(머리)와 rear(꼬리)가 있다. 머리는 저장된 데이터 중 첫 번째 데이터를 가리킨다. 꼬리는 저장된 데이터 중 마지막 데이터를 가리킨다. 첫 번째 데이터 앞을 front가 가리켜야 한다. 데이터 삽입 : enQueue 데이터 추출 : deQueue 큐의 간단 구현 큐는 배열 형태로 구현할 수 있다. 큐는 초기에 크기를 지정하고 배열로 생성할 수 있다. ..
6. 2020.08.13 탐욕 알고리즘(Greedy Algorithm)

   *탐욕 알고리즘 탐욕 알고리즘(Greedy Algorithm) - 결과값에 대하여 생각하지 않고 최선의 옵션을 선택하여 문제를 해결하는 알고리즘 - 즉, 지역적(locally)의 최선의 선택이 전역적(globally)의 최상의 결과값을 생성하도록 하는 것을 목표로 하는 알고리즘.- 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘 - 탐욕 알고리즘은 해답에 포함될 원소들을 차례로 선택하는 과정을 거치게 됨 - 각 단계에서는 전체적인 상황을 종합적으로 판단하고, 고려하여 결정하는 것이 아니라 현 시점의 정보 를 바탕으로 가장 이익이 되는 원소들을 선택함. - 동적 계획법(Dynamic Programming)과 마찬가지로 최적화 문제(Optimization Problem) 를 푸는데 사..