프로그래밍 언어/자료구조 검색 결과

해당 글 8건

단순 연결 리스트

단순 연결 리스트 연결 리스트는 각 데이터들을 포인터로 연결하여 관리하는 구조입니다. 연결 리스트에는 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트 등이 있습니다. 우선 단순 연결리스트에 대해서 배워보도록 하겠습니다. 말 그대로 단순하게 한 방향으로 전개되고 끝이 존재합니다. 구현을 할 때 더미노드가 있으면 굉장히 편리합니다 . 왜냐하면 더미노드가 있을 경우 더미노드 이후 데이터가 들어가기 때문에 일관 된 형태로 추가, 삭제 ,조회등을 할 수 있습니다. 1)더미노드 생성과 초기화 즉 위의 사진처럼 헤드가 더미노드를 가리키게 하면 됩니다. 우선 단순 연결 리스트를 표현하는데 있어서 필요한 도구들을 살펴보겠습니다. 노드의 구조체를 표현해야합니다. 즉 Node라는 구조체로 리스트를 표현합니다. he..
프로그래밍 언어/자료구조 2018. 8. 22. 17:12

힙 정렬

힙 정렬(Heap Sort) 힙 정렬은 힙을 이용하여 정렬을 합니다. 루트 노드에 있는 값이 정렬 순서상 가장 앞서는 원리를 이용합니다. 그러기 위해선 힙을 이용해야겠죠. 힙은 간단히 얘기하자면 트리중에 하나인데 완전 이진 트리입니다. 즉 모든 노드 저장된 값들이 자식 노드 보다 크거나 같아야합니다. 루트노드가 가장 큰것이죠. 값은 우선순위가 될 수도 있고 그 자체 Value(값)일 수도 있습니다. 최대 힙과 최소 힙이 있습니다. 최대 힙은 루트노드로 갈 수록 값이 커지는 트리이고 최소 힙은 루트노드로 갈 수록 값이 작아지는 트리입니다. 즉 힙을 이용해서 정렬 대상을 힙에 삽입을 하고 차례대로 삭제하여 꺼내면 정렬 완료입니다. (우선순위 큐) 힙 정렬 함수 우선 정렬 대상을 인자로 전달합니다. arr[]..
프로그래밍 언어/자료구조 2018. 8. 17. 14:42

퀵 정렬

퀵정렬(Quick Sort) 퀵 정렬은 매우 빠른 속도를 보입니다. 퀵 정렬은 간단히 말해서 pivot을 정해서 low 와 high가 서로 교차 할 때 까지 교환하며 교차될 때 high를 pivot과 교체하고 전 pivot을 기준으로 반을 나눠서 왼쪽 영역과 오른쪽 영역에서 이 과정을 반복합니다. 그림으로 설명 드릴게요. 총 필요한 변수는 left, right, low, high, pivot 총 5개입니다. 우선 초기 세팅 결과는 초기 세팅 left 와 right는 각자 맨 왼쪽과 맨 오른쪽을 담당합니다. pivot은 아무 기준으로 삼아도 되지만 우선 맨 왼쪽 5를 pivot으로 삼겠습니다. low는 pivot을 제외한 맨 왼쪽을 담당하고 hight는 맨 오른쪽을 담당합니다. low와 high의 이동 l..
프로그래밍 언어/자료구조 2018. 8. 16. 14:10

기수정렬

기수정렬 기수정렬은 다른 정렬들과는 달리 유일하게 비교연산이 없습니다. 정렬 알고리즘들의 성능 한계인 O(nlog2N)을 유일하게 뛰어 넘을 수 있는 알고리즘입니다. 하지만 단점으로는 적용 범위에 한계가 있습니다. 1 5 4 2 3 6 이런 것은 정렬 가능 하지만 11 23 333 2 4 이런 것들은 정렬 불가합니다. 즉 자릿 수가 다를 경우 정렬 불가능 하다는 겁니다. 하지만 이를 위해 여러 알고리즘을 모색하였습니다. 기본적인 한자리 숫자 기수 정렬의 원리를 알아보겠습니다. 우선 버킷에 정렬 숫자들을 담습니다. 버킷은 양동이입니다. 즉 1 4 2 3 이라는 숫자가 있으면 1은 버킷 1에 4는 버킷 4에 2는 버킷 2에 3은 버킷 3에 들어갑니다. 이것을 버킷 순서대로 꺼냅니다.!! 그럼 1 2 3 4 ..
프로그래밍 언어/자료구조 2018. 8. 13. 19:31

병합정렬

병합정렬(merge sort) 병합 정렬에 대해서 설명드릴게요. 말 그대로 분할 해서 병합 시키는 정렬입니다. 총 3단계로 나누어 보면 Divide : 분할 한다. Sol: 해결 한다. Combine: 결합 한다. 이런 3단계가 기본 원리입니다. 이를 알고리즘에 적용 시켜서 그림으로 보겠습니다. 8 2 3 7 1 5 4 6이라는 숫자가 무작위로 배열 되어 있습니다. 이를 반으로 나눠서 정렬을 해보도록 해보죠. ↓ 1단계 우선 반으로 절반 쪼갰습니다. 분할을 했죠. 8 2 3 7 과 1 5 4 6으로 말이죠. ↓ 2단계 그 다음 각 부분에서 정렬을 시도 합니다. 즉 문제를 해결 합니다. ↓ 3단계 적절 하게 정렬을 하면서 결합을 완료 짓습니다. 정렬 완료입니다. 실제로는 훨씬 더 작게 분할을 해야합니다. ..
프로그래밍 언어/자료구조 2018. 8. 9. 19:06

계수정렬(심화)

계수정렬 앞서 배운 선택정렬, 삽입정렬, 버블정렬은 쉽고 간단한 알고리즘입니다. 따라서 성능을 더 개선 시키고자 심화된 알고리즘 정렬 방식이 나왔습니다. 계수정렬, 힙정렬, 병합정렬, 기수정렬, 퀵정렬이 있습니다. 이번은 계수정렬 (counting Sort)에 대해서 설명드리도록 할게요. 계수정렬 계수정렬은 정렬되지 않은 숫자들을 가지고 횟수를 셉니다. 각 숫자별로 횟수들의 합을 구하여 누적합니다. 누적 된 숫자를 인덱스로하여 삽입하고 누적 숫자를 감소시킵니다. 계수정렬의 특징은 뒤에서부터 앞으로 정렬 배열에 넣습니다. 즉 누적된 숫자가 정렬 배열에 들어갈 위치입니다. 제가 그려본 예로 한번 봅시다. 우선 정렬 되지 않은 숫자(not_Sort): 1 3 2 2 4 *인덱스는 1부터 시작 인덱스 1 2 3..
프로그래밍 언어/자료구조 2018. 8. 6. 18:58

선택정렬&삽입정렬

선택정렬&삽입정렬 1)선택정렬 선택정렬은 앞서 배운 버블보다 더 간단합니다. 원래 정렬대상을 선택해서 별도 메모리 공간에 차근차근 넣어야 해요. 하지만 최근에 메모리 공간을 별도로 사용하지 않구 있어요 그러기 위해서 가장 우선순위가 높은 즉 최소값을 탐색을 해서 그것을 가장 왼쪽으로 이동 시킵니다. 가장 왼쪽에 있던 데이터는 빈 자리에 갖다 놓습니다. 반복 합니다. 이렇듯 교환처럼 보이지만 빈 자리를 이용한 다는 것을 알아야합니다. 그래서 선택정렬 인겁니다. 단순 교환이 아니지요 그림으로 확인해보죠 이런 식으로 최소값 1이 빈자리를 만들고 맨앞으로 가고 3이 그 빈자리를 채웁니다. 1은 고정입니다. 그 다음 최소값을 탐색하여 고정 자리 제외한 가장 왼쪽으로 이동시킵니다. 반복합니다. 이 과정을 코드로 봐..
프로그래밍 언어/자료구조 2018. 8. 5. 18:01

버블정렬

버블 정렬 버블 정렬은 구현하기 쉽습니다. 쉽게 말하면 버블 정렬은 인접한 두개 데이터를 계속 비교해서 크기에 따라 서로 바꿔주면서 정렬을 해주는 알고리즘입니다. 그림을 통해서 우선 이해를 해봅시다. 1. 이런식으로 비교를 해가면서 진행해 나갑니다. 3과 2중에 2가더 작기때문에 2와 3을 바꿔 줍니다. 또 3과 4를 비교합니다. 3이 더 작기때문에 이때는 교체하지 않습니다. 다음 인덱스로 넘어가면서 4와 1을 비교합니다. 이때 1이 더 작기 때문에 1과 4를 교체합니다. 큰 숫자가 마지막에 가있습니다. 건드릴 필요 없겠죠. 자 끝난 것 같죠?? 아닙니다. 아직 2 3 1 4 로 정렬이 되지 않았습니다. 다시 처음 인덱스0인 값 2로 이동을 해서 위의 과정을 정렬이 끝날 때 까지 반복합니다. 2와 3을 ..
프로그래밍 언어/자료구조 2018. 8. 4. 18:41