반응형 자료구조 프로그래밍/알고리즘 2020. 4. 20. Quick Sort (퀵 정렬) 개념 - 분할해서 정렬 - 주어진 값에서 기준이 될 값을 정하고 기준이 되는 값보다 작은 값은 왼쪽, 높은 값은 오른쪽으로 우선 정렬한다. 이후 왼쪽은 왼쪽대로 정렬하고, 오른쪽은 오른쪽대로 정렬한다. - 랜덤 배열에서 빠름 - 순열이나 역순의 경우 매우 느림 (기준값을 선정하는 방법에 따라 속도가 다름) 1. 최소 값이나 최대 값으로 할 경우 2. 이미 정렬된 배열을 정렬할 경우 - 재귀함수 기반으로 구현할 경우 복잡해질 수 있다. 기준값이 3라고 정했을 경우 (5,4,'3',2,1) -> (2,1,'3',5,4) 왼쪽 값 정렬 : (2,1) -> (1,2) 오른쪽 값 정렬 (5,4) -> (4,5) 최종적으로 (1,2,3,4,5)로 정렬 된다. 퀵정렬의 단점을 보안하기 위해 여러 기법들이 .. 프로그래밍/알고리즘 2020. 4. 19. Insertion Sort (삽입정렬) 개념 - 두번째 값부터 차례대로 앞의 숫자들과 비교하면서 알맞는 위치에 삽입하여 정렬하는 방식 - 값 교환에는 두가지 방식이 있음 1. 앞의 숫자들과 교환하면서 위치를 찾아가는 방법 2. 위치만 찾은 다음 자신의 위치와 찾은 위치 사이의 값들을 하나씩 뒤로 민 다음 넣는 방법 (4,3,2,1) -> (3,4,2,1) - 두번째 값인 3과 앞의 값인 4를 비교한다. (3,4,2,1) -> (3,2,4,1) -> (2,3,4,1) - 세번째 값인 2와 앞의 값인 3,4를 비교한다. (2,3,4,1) -> (2,3,1,4) -> (2,1,3,4) -> (1,2,3,4) - 마지막으로 네번째 값인 1과 앞의 값인 2,3,4를 비교한다. RememberCook 9월 28일 정식 출시! 두번째 게임인 .. 프로그래밍/알고리즘 2020. 4. 19. Selection Sort (선택정렬) 개념 - 주어진 값에서 가장 작은 값 (또는 큰 값)을 찾아 정렬하고 나머지 값들에서 또 가장 작은 값을 찾아 정렬하는 방식이다. 아래 내용은 선택정렬을 통해 정렬되는 모습을 순서대로 나열한 것이다. 주어진 값 : 4,3,2,1 정렬기준 : 오름차순 (4,3,2,1) -> (1,4,3,2) - 주어진 값에서 가장 낮은 값을 찾아 맨 앞으로 가져온다. (1,4,3,2) -> (1,2,4,3) - 마찬가지로 주어진 값에서 이미 정렬된 1을 제외하고 가장 낮은 값을 찾아서 맨 앞으로 가져온다. (1,2,4,3) -> (1,2,3,4) - 반복해서 가장 낮은 값을 앞으로 가져오면 정렬이 종료된다. RememberCook 9월 28일 정식 출시! 두번째 게임인 RememberCook이 출시되었습.. 프로그래밍/알고리즘 2020. 4. 19. Bubble Sort (버블정렬) 개념 - 인접한 요소와 순서를 비교하여 정렬한다. - 첫번째 값과 두번째 값을 비교하여 정렬하고, 두번째 값과 세번째 값을 비교하여 정렬하는 식으로 단계별로 정렬한다. (4,3,2,1) -> (3,4,2,1) - 첫번째 값인 4와, 두번째 값인 3을 비교한다. (3,4,2,1) -> (3,2,4,1) - 두번째 값인 4와 세번째 값인 2를 비교한다. (3,2,4,1) -> (3,2,1,4) - 세번째 값인 4와 네번째 값인 1을 비교한다. (3,2,1,4) -> (2,3,1,4) - 다시 첫번째 값인 3과 두번째 값인 2를 비교한다. (2,3,1,4) -> (2,1,3,4) - 두번째 값인 3과 세번째 값인 4를 비교한다. (2,1,3,4) -> (1,2,3,4) - 마지막으로 첫번.. 프로그래밍/기본기ㆍ자료구조 2020. 4. 19. Map (맵) Key와 Value 형식을 가지고 있다. 아이디와 비밀번호를 연상하면 이해하기 쉽다. 가장 기본적인 특징 - Key와 Value는 한 묶음이다. - Key는 중복될 수 없다. - Value는 중복될 수 있다. 그 외 특징 - C#의 Dictionary와 거의 동일하다. - Map은 iterater로 순차접근을 할 수 있다. - Dictionary는 KeyValuePair로 foreach문을 이용한 순차접근을 해야한다. - Red-Black Tree 알고리즘을 이용해서 구현되어 있다. (이진탐색트리의 일종이며 자가균형이진트리 중 일부이다. Balanced Binary Search Tree) 참고 출처 Map (맵) Key와 Value 형식을 가지고 있다.아이디와 비밀번호를 연상하면 이해하기 쉽다.. 프로그래밍/기본기ㆍ자료구조 2020. 4. 15. Graph (그래프) 노드와 간선(노드와 노드를 잇는 선)으로 이루어진 자료구조이다. 트리와 그래프의 관계 - 큰 범위 안에서는 트리는 그래프의 일종이다. 트리 - 방향성이 있는 비순환 그래프 - 한 개의 루트 노드만이 존재 (자식 노드는 하나의 부모 노드만을 가진다.) - 전위, 중위, 후위 순회 및 계층 순회(level-Order) - 노드가 N개이면 항상 N-1개의 간선을 가짐 그래프 - 노드와 간선으로 이루어짐 - 방향성, 무방향성 그래프 모두 존재 - 루트 노드의 개념이 없다 - 깊이 우선 탐색(DFS : Depth First Search), 너비 우선 탐색(BFS :Breadth First Search) - 그래프에 따라 간선의 수가 다르다 그래프의 종류 a. 무방향 그래프(Undirected Graph.. 프로그래밍/기본기ㆍ자료구조 2020. 4. 15. Tree (트리) 그래프의 일종. 데이터 항목의 한 묶음을 세그먼트라고 하는데, 이 세그먼트 사이의 연결을 나뭇가지처럼 표현한 것이 트리 구조다. 1. 트리 종류 a. 이진 트리 (binary tree) - 자식노드가 최대 2개면 이진 트리라고 한다. - 이진 탐색 트리, 힙 등을 구현하기 위해 사용된다. b. 삼항 트리 (ternary tree) - 자식노드가 최대 3개면 삼항 트리로 구분된다. c. 완전 이진 트리 (complete binary tree) - 노드들이 왼쪽부터 차곡차곡 쌓여있는 형태의 트리 d. 포화 이진 트리 (full binary tree) - 단말 노드까지의 깊이가 동일하면서 모든 노드의 자식 노드가 2개인 이진 트리를 말한다. 2. 노드 종류 a. 노드 - 그래프를 구성하는 하나의 요소... 프로그래밍/기본기ㆍ자료구조 2020. 4. 14. DeQueue (데큐,데크) 개념 - Double Ended Queue의 약자 - 리스트의 양쪽 끝에서 노드의 삽입과 삭제가 모두 가능한 선형 리스트 자료구조 - 스택과 큐를 복합한 방식 - 링크드리스트로 구현하거나, 스택 두개를 이어 구현하는 방법이 있다. *입력제한 데크(Scroll) - 출력은 양방향에서 가능, 입력은 한 방향만 가능 *출력제한 데크(Shelf) - 입력은 양방향에서 가능, 출력은 한 방향만 가능 RememberCook 9월 28일 정식 출시! 두번째 게임인 RememberCook이 출시되었습니다. 귀여운 캐릭터들이 나오는 간단한 게임이며 플레이어의 공간인지능력을 테스트하는 게임입니다. 아래 링크를 통해 다운 받으실 수 있으니 많은 관�� chipmunk-plump-plump.tistory.com 이전 1 2 3 4 다음 반응형
