COMPUTER SCIENCE/Algorithmic & Data Structure (31) 썸네일형 리스트형 [Section 6] 검색 알고리즘의 종류와 특징 자료구조와 알고리즘 목차 보기 [INTRO] 자료구조와 알고리즘 자료구조와 알고리즘에 대해서... 자료구조는 프로그래밍에서 사용되는 데이터를 어떻게 표현하는 것인가에 대한 컴퓨터 과학 분야이다. 그리고 알고리즘은 표현된 데이터를 계산하는 방법에 hookspedia.tistory.com 0. INTRO 검색 알고리즘은 자료 구조에서 특정 조건의 데이터를 추출하거나 찾는 데 사용하는 알고리즘이다. 자료구조에 따라 어떤 알고리즘이 효율적인지 그 종류와 특징에 대해 간략히 알아보자. 1. 간단히 구현 가능한 선형 검색 선형 검색(Linear Search)은 자료가 리스트 혹은 기타 선형 자료구조에서 단순히 구현 가능한 검색 알고리즘이다. 예를 들어, 배열의 데이터가 어떤 조건을 가지지 않고 무작위로 저장되어 있.. [Section 5] 탐색의 기본 _ 너비 우선 탐색 기법(Breadth First Search) 자료구조와 알고리즘 목차 보기 [INTRO] 자료구조와 알고리즘 자료구조와 알고리즘에 대해서... 자료구조는 프로그래밍에서 사용되는 데이터를 어떻게 표현하는 것인가에 대한 컴퓨터 과학 분야이다. 그리고 알고리즘은 표현된 데이터를 계산하는 방법에 hookspedia.tistory.com 0. INTRO 너비 우선 탐색 기법은 이전에 배운 트리의 레벨 순회 알고리즘과 아주 유사하다. 그래프에서도 계층을 우선으로 하여 탐색하기 위해서는 큐를 이용해야 하고 때때로 깊이 우선 탐색 기법보다 우수한 성능을 보이기도 한다. 이 BFS 알고리즘에 대해 배워보자. 1. 너비 우선 탐색의 이해 _ 모든 꼭짓점 노드를 방문하는 방법 다음의 예시 그래프를 참고하도록 하자. 너비 우선 탐색(Breadth First Search.. [Section 1] 알고리즘의 분석 _ 세타 표기법 자료구조와 알고리즘 목차 보기 [INTRO] 자료구조와 알고리즘 자료구조와 알고리즘에 대해서... 자료구조는 프로그래밍에서 사용되는 데이터를 어떻게 표현하는 것인가에 대한 컴퓨터 과학 분야이다. 그리고 알고리즘은 표현된 데이터를 계산하는 방법에 hookspedia.tistory.com 0. INTRO 상한, 하한, 최고 상태, 최악 상태의 관계를 명확히 이해하기 위해서는 세타 표기법에 대해 알아야 한다. 평균 런타임을 의미하는 세타 표기법을 알아보고, 알고리즘의 분석 메커니즘을 파악하자. 1. 세타 표기법의 정의 세타 표기법의 수학적 정의는 다음과 같다. "Θ(f(n)) = {g(n): 양의 정수 c1, c2와 n0가 존재하여, 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n) 을 만족하는 경우에 대해서 .. [Section 1] 알고리즘의 분석 _ 빅-오메가 표기법 자료구조와 알고리즘 목차 보기 [INTRO] 자료구조와 알고리즘 자료구조와 알고리즘에 대해서... 자료구조는 프로그래밍에서 사용되는 데이터를 어떻게 표현하는 것인가에 대한 컴퓨터 과학 분야이다. 그리고 알고리즘은 표현된 데이터를 계산하는 방법에 hookspedia.tistory.com 0. INTRO 사실 알고리즘 분석에 있어서 빅-오메가 표기법은 그리 중요한 사항이 아니다. 하지만, 빅-오메가 표기법의 의의는 하한의 이해를 기반으로 자료구조의 알고리즘을 분석하는 데에 있다. 하한을 이해하면, 알고리즘의 최고 상태와 최악의 상태가 무엇인지 감이 올 것이다. 1. 빅 - 오메가 표기법의 정의 빅-오 표기법과 마찬가지로 빅-오메가 표기법의 수학적 정의를 먼저 보자. " Ω(f(n))={g(n): 양의 정수 .. [Section 6] 정렬 알고리즘의 종류와 특징 자료구조와 알고리즘 목차 보기 [INTRO] 자료구조와 알고리즘 자료구조와 알고리즘에 대해서... 자료구조는 프로그래밍에서 사용되는 데이터를 어떻게 표현하는 것인가에 대한 컴퓨터 과학 분야이다. 그리고 알고리즘은 표현된 데이터를 계산하는 방법에 hookspedia.tistory.com 0. INTRO 정렬(Sorting) 알고리즘의 의의는 문제의 복잡성(Complexiy)을 획기적으로 줄여준다는 점에 있다. 그리고 데이터 베이스를 구축하는데 중요한 이 정렬 알고리즘의 분류와 대표 알고리즘을 간단히 알아보자. 1. 정렬 알고리즘의 분류 _ 어떤 수단을 이용하는가? 어떤 리스트 내에 존재하는 데이터의 특정한 순서를 수 관점에서 낮은 수부터 높은 수로 나타내는 것을 오름차순(Ascending) 정렬, 높은 수.. [Section 8] 알고리즘 설계 기초 _ 분류(Classification) 자료구조와 알고리즘 목차 보기 [INTRO] 자료구조와 알고리즘 자료구조와 알고리즘에 대해서... 자료구조는 프로그래밍에서 사용되는 데이터를 어떻게 표현하는 것인가에 대한 컴퓨터 과학 분야이다. 그리고 알고리즘은 표현된 데이터를 계산하는 방법에 hookspedia.tistory.com 0. INTRO 알고리즘의 설계를 위해서는 내가 구현하고자 하는 문제가 어떤 유형인지 알아내고, 문제에 맞는 알고리즘 구현 방법을 체계적으로 분류할 필요가 있다. 분류된 방법들에는 어떤 종류가 있는지 간단히 알아보기로 하자. 1. 구현 방법에 따른 분류 가장 먼저 구현 방법에 따른 분류로는 재귀(Recursion) 및 반복(Iteration) 알고리즘이 존재한다. 명령의 반복에 의해서 구현되는 이 알고리즘들은 쉽게 구현될 .. [Section 5] 탐색의 기본 _ 깊이 우선 탐색(Depth First Search) 자료구조와 알고리즘 목차 보기 [INTRO] 자료구조와 알고리즘 자료구조와 알고리즘에 대해서... 자료구조는 프로그래밍에서 사용되는 데이터를 어떻게 표현하는 것인가에 대한 컴퓨터 과학 분야이다. 그리고 알고리즘은 표현된 데이터를 계산하는 방법에 hookspedia.tistory.com 0. INTRO 이진트리의 순회 알고리즘과 유사하게 그래프에도 꼭짓점 노드에 대한 탐색 알고리즘이 존재한다. 가장 먼저 알아볼 탐색 알고리즘은 깊이 우선 탐색(Depth First Search) 알고리즘이다. 이는 코딩 테스트의 주요 기출문제로 자주 나오기도 한다. 1. 깊이 우선 탐색 기법의 이해 _ 모든 꼭짓점 노드를 방문하는 방법 깊이 우선 탐색기법을 위해 다음의 예시 그래프를 참고하도록 하자. 예시 그래프에서 보이는.. [Section 4] 그래프와 큐의 혼합 _ 방문 상태 체크 자료구조와 알고리즘 목차 보기 [INTRO] 자료구조와 알고리즘 자료구조와 알고리즘에 대해서... 자료구조는 프로그래밍에서 사용되는 데이터를 어떻게 표현하는 것인가에 대한 컴퓨터 과학 분야이다. 그리고 알고리즘은 표현된 데이터를 계산하는 방법에 hookspedia.tistory.com 0. INTRO 방문 순서를 저장하는 알고리즘은 이후의 탐색 기법 중 DFS, BFS라는 알고리즘에서 필요한 알고리즘이다. 이 방문 순서 알고리즘은 큐와 그래프 알고리즘을 응용하여 생성이 가능하고 다양한 자료구조를 응용의 필요성에 대해 알려준다. 1. 배열 큐에 저장된 방문 순서 _ 예시 그래프와 큐 먼저 다음의 그래프 예시를 보자. 위의 행렬에서 0으로 표기된 정보가 접근 가능하다는 의미를 나타낸다. 그리고 위 경우에서는.. [Section 4] 그래프 알고리즘 _ 인접 리스트(Adjacency List) 자료구조와 알고리즘 목차 보기 [INTRO] 자료구조와 알고리즘 자료구조와 알고리즘에 대해서... 자료구조는 프로그래밍에서 사용되는 데이터를 어떻게 표현하는 것인가에 대한 컴퓨터 과학 분야이다. 그리고 알고리즘은 표현된 데이터를 계산하는 방법에 hookspedia.tistory.com 0. INTRO 이번에는 인접 리스트 알고리즘을 생성해보자. 여기에서는 이전에 생성했던 단일 연결 리스트 알고리즘을 이용할 것이다. 1. 인접 리스트 방식 _ 구현 그래프 먼저 다음의 그림을 참고하자. 왼쪽은 예시 그래프이고 오른쪽은 구현할 자료 구조를 리스트 형태로 나타낸 것이다. 개인적으로 인접 행렬 방식보다 연결 리스트 방식이 그래프의 연결 상태를 확인하기에 깔끔해 보이긴 한다. 생성 예시: 2. 인접리스트 알고리즘 .. [Section 3] 파이썬 큐 모듈 사용법 _ 복잡도 분석&비교 자료구조와 알고리즘 목차 보기 [INTRO] 자료구조와 알고리즘 자료구조와 알고리즘에 대해서... 자료구조는 프로그래밍에서 사용되는 데이터를 어떻게 표현하는 것인가에 대한 컴퓨터 과학 분야이다. 그리고 알고리즘은 표현된 데이터를 계산하는 방법에 hookspedia.tistory.com 0. INTRO 큐 자료 구조는 이전에 제시한 원형 배열 이외에도 리스트 자료구조를 사용하거나, 큐 모듈을 이용하는 방법이 있다. 어떤 자료를 사용하느냐에 따라 효율이 달라지니, 큐 모듈을 사용하는 방법을 알아 두도록 하자. 1. 큐 모듈 호출하기 _ import queue 파이썬에는 큐 모듈이 내장되어있어서, 간단한 큐 자료구조는 큐 모듈 호출을 이용하여 사용하기로 하자. 큐 모듈을 호출하는 코드는 import queue.. [Section 3] 큐(Queue) 구현 알고리즘 _ 원형 배열(Circular Array) 자료구조와 알고리즘 목차 보기 [INTRO] 자료구조와 알고리즘 자료구조와 알고리즘에 대해서... 자료구조는 프로그래밍에서 사용되는 데이터를 어떻게 표현하는 것인가에 대한 컴퓨터 과학 분야이다. 그리고 알고리즘은 표현된 데이터를 계산하는 방법에 hookspedia.tistory.com 0. INTRO 원형 배열로 큐는 고정된 사이즈라는 단점을 가지고 있다. 하지만, 그 구현이 매우 단순하고 이해하기 쉽다는 장점을 가지고 있다. 가장 쉬운 큐를 구현함으로써 원형 배열 알고리즘을 이해해보자. 1. 원형 배열 큐의 복잡도 분석 큐의 핵심은 인큐(EnQueue)와 디큐(DeQueue)이다. 그리고 이 자료구조의 공간 복잡도가 O(n)이지만, 자료가 적을 때 적절히 사용해주면 아주 효과적이다. 왜냐하면, 자료구조.. [Section 2] 연결 리스트 _ 중간 삽입& 삭제 구현 자료구조와 알고리즘 목차 보기 [INTRO] 자료구조와 알고리즘 자료구조와 알고리즘에 대해서... 자료구조는 프로그래밍에서 사용되는 데이터를 어떻게 표현하는 것인가에 대한 컴퓨터 과학 분야이다. 그리고 알고리즘은 표현된 데이터를 계산하는 방법에 hookspedia.tistory.com 0. INTRO 지금까지 연결 리스트의 노드 생성과 삽입, 그리고 삭제를 통해서 어떻게 연결 리스트가 구성되는지 알아보았다. 이번에는 중간 삽입 기능을 구현하여, 연결 리스트 자료구조를 완전히 이해하도록 하자. 1. 중간 삽입 방법 _ 위치 함수의 필요성 리스트에 중간 삽입을 하는 방법은 의외로 간단하다. 연결된 링크를 끊어주고 새 노드를 붙이면 된다. 하지만 지금까지 구현한 SLL함수는 위치를 나타내는 기능이 없기 때문에.. 이전 1 2 3 다음
