분류 전체보기120 자료구조(10) 정렬의 7가지 방법 알고리즘을 코드 레벨에서 분석만 한다면 지루할 수 있다. 이보다는 각각의 알고리즘이 갖는 특징에 관심을 두고 공부하는 것이 기억에도 오래 남고 더 의미가 있을것이다. 1-1 버블 정렬 : 이해와 구현 이해하기도 구현하기도 쉽다. 물론 이해와 구현이 쉬운 만큼 성능에는 아쉬움이 있다. 버블 정렬을 구성는 두 개의 for문의 반복조건이 핵심이다. 따라서 바깥쪽 for문의 반복조건과 안쪽 for문의 반복 조건에 대해서 대략적인 이해가 아니라 정확한 이해가 필요하다 1-2 버블 정렬 : 성능 평가 정렬 알고리즘의 성능은 다음 두 가지 근거로 판단하는 것이 일반적이다. "비교연산"과 데이터의 이동을 위한 "대입연산"이 정렬과정의 핵심연산이기 때문이다. 비교의 횟수 : 두 데이터간의 비교연산의 횟수 이동의 횟수 :.. 2022. 3. 16. 자료구조(9) 우선순위 큐와 힙 우선순위 큐는 그 이름이 의미하듯 큐와 관련이 있다. 하지만 공부하다보면 그 관계가 깊지 않다고 느낄지도 모르겠다. 제목만 봐서는 앞서 구현한 "큐"를 확장하는 수준에서 마무리가 될 것 같지만 "큐"의 구현과 "우선순위 큐"의 구현에는 많은 차이가 있다. 큐의 핵심 연산 두가지 enqueue : 큐에 데이터를 삽입하는 행위 dequeue : 큐에서 데이터를 꺼내는 행위 우선순위 큐의 핵심 연산 두가지 enqueue : 우선순위 큐에 데이터를 삽입하는 행위 dequeue : 우선순위 큐에서 데이터를 꺼내는 행위 반면 연산의 결과에는 차이가 있다. 큐의 연산 결과로, 먼저 들어간 데이터가 먼저 나오지만, 우선순위 큐의 연산결과는 다음과 같다. "들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다" .. 2022. 3. 16. 자료구조(8) 트리 "트리"는 고급 자료구조로 구분이 된다. 그만큼 학습에 있어서 집중을 요한다. 특히 비선형 자료구조이기때문에 많이 다르게 느껴질 수도 있다!" 트리는 계층적 관계를 표현하는 자료구조이다! 자료구조! 하면 보통은 무엇인가를 저장하고 꺼내는 것이 전부인 것으로 이해하는 경우가 많다. 앞서 보인 선형 자료구조들은 이에 초점이 맞춰져 있었으니 무리도 아니다. 하지만 자료구조는 근본적으로 무엇인가를 "표현" 하는 도구이다. 트리는 데이터의 저과 삭제가 아닌 "표현"에 초점이 맞춰져 있다. 때문에 트리의 ADT를 다음과 같이 바라보면 안된다. "데이터의 저장, 검색 및 삭제가 용이하게 정의되어 있나요?" 대신 다음과 같이 바라봐야 한다. "트리의 구조로 이뤄진 무엇인가를 표현하기에 적절히 정의되어 있나요?" 노드(.. 2022. 3. 16. 자료구조(7) 덱 덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조! 덱은 양방향으로 넣고, 양방향으로 뺄 수 있는 자료구조이기에 스택과 큐의 특성을 모두 갖는, 혹은 스택과 큐를 조합한 형태의 자료구조로 이해되고 있다. 덱도 배열을 기반으로, 그리고 연결 리스트 기반으로도 구현이 가능하다. 하지만 우리는 덱의 구현에 가장 어울린다고 알려진 "양방향 연결 리스트"를 기반으로 덱을 구현할 것이다. 그 이유는 다음 함수와 관련이 있다. "Data DQRemoveLast(Deque * pdeq); // 꼬리에 위치한 데이터(노드) 삭제 위 함수는 꼬리에 위치한 노드를 삭제하는 함수인데, 노드가 양방향으로 연결되어 있지 않으면, 꼬리에 위치한 노드의 삭제는 간단하지 않다. 때문에 덱의 구현에 있어서 양방.. 2022. 3. 16. 자료구조(6) 큐 큐는 "선입선출" 구조의 자료구조이다. 때문에 FIFO(First-in , First-out) 구조의 자료구조라 불린다. 큐 역시 스택과 마찬가지로 배열을 기반으로, 그리고 연결 리스트를 기반으로도 구현이 가능하다. 처음 큐를 접하면 다음과 같이 생각하는 것이 보통이다. "스택과 큐의 차이점이 앞에서 꺼내느냐 뒤에서 꺼내느냐에 있으니, 이전에 구현해 놓은 스택을 대상으로 꺼내는 방법만 조금 변경하면 큐가 될 것 같다" 하지만 큐의 구현모델을 알게되면 이보다는 큰 차이가 있다고 느낄 것이다. 큐의 배열 기반 구현 F를 참조하여 dequeue 연산을 하고, R을 참조하여 enqueue연산을 한다 (F=머리, R=꼬리) "뒤로 넣고 앞으로 빼는 자료구조" // 이것만 외워도 큐의 원리가 쉽게이해된다. 잘못된 .. 2022. 3. 16. 이전 1 ··· 19 20 21 22 23 24 다음
