본문 바로가기

컴퓨터 일반

 (28)
자료구조 문제 정리 (6) 탐색, 해싱 1. 이진 탐색 (Binary Search)정렬된 배열에서 값을 효율적으로 찾는 알고리즘배열의 중간 요소를 선택하고, 찾고자 하는 값과 비교하는 과정이 반복된다과정:중간 요소와 찾고자 하는 값을 비교중간 값이 찾는 값보다 크면 왼쪽 절반으로, 작으면 오른쪽 절반으로 검색 범위를 좁힌다이 과정을 범위가 하나의 요소로 좁혀질 때까지 반복하거나, 찾는 값이 없다고 판별될 때까지 반복한다시간 복잡도는 O(log⁡n)을 보장하며, 정렬된 데이터에서 빠르게 값을 찾을 수 있다.이진 탐색은 배열이나 리스트와 같은 선형 자료구조에서 주로 사용된다. 2. 이진 탐색 트리 (Binary Search Tree, BST)이진 탐색 트리는 이진 트리의 특수한 형태로, 모든 노드가 특정 정렬 기준에 맞게 정렬되어 있다.특징:각 ..
자료구조 문제 정리 (5) 정렬 정렬 알고리즘 시간 복잡도정렬종류평균최악버블정렬O(n^2)O(n^2)선택정렬O(n^2)O(n^2)삽입정렬O(n^2)O(n^2)퀵정렬O(nlogn)O(n^2)2-way merge 정렬O(nlogn)O(nlogn)힙 정렬O(nlogn)O(nlogn)기수 정렬O(n)O(n)*삽입 정렬과 버블 정렬의 경우 이미 정렬된 입력 데이터로 O(n)의 시간복잡도를 얻을 수 있다 1. 버블 정렬(Bubble sort)버블 정렬은 가장 기본적인 알고리즘 중 하나로, 인접한 데이터와 비교하면서 가장 큰 데이터를 맨 뒤로 옮긴다.맨 뒤에서부터 저장을 완료해나가는 방식이다안정적인 정렬이다.void Bubble_Sort(int arr[], int len) { int i, j, tmp; for (i = 0; i arr[j + ..
자료구조 문제 정리 (4) 그래프 [그래프의 순회 : BFS, DFS] (1)다음 그래프를 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 방법으로 방문할 때각 정점을 방문하는 순서로 옳은 것은? *시작 정점은 A이다, 알파벳 순서대로 방문한다.너비 우선 탐색(BFS)시작정점 A와 인접한 노드 B,F를 모두 삽입해야 하므로 A B F가 큐에 삽입되고 이 순서대로 방문한다A B F C D E 순서대로 방문한다깊이 우선 탐색(DFS)시작 정점 A의 인접한 노드 중 하나만 선택하는데 알파벳 순서대로 선택하게 되면 A,B가 된다.A B C D E F 순서대로 방문한다  그래프의 깊이 우선 탐색은 스택을, 너비 우선 탐색은 큐를 이용한다. (2)다음 그래프의 정점 A에서부터 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 수행할 때, 방..
자료구조 문제 정리 (3) 트리 1. 이진트리이진트리(BST) 부모를 중심으로 좌측에는 모두 부모보다 작은 데이터가 우측에는 모두 부모보다 큰 데이터가 위치한다(데이터가 위에서부터 들어와서 루트노드를 거쳐서 위치를 찾아감)https://www.youtube.com/watch?v=Smmz7MT4oxM 일반 트리와 다르게 공집합을 허용한다.각 노드는 최대 2개의 자식 노드를 갖는다.어떤 노드에서 루트 노드에 이르는 경로는 유일하다.n개의 노드를 가진 이진 트리는 n-1개의 간선을 갖는다.노드(node)가 11개 있는 트리의 간선(edge) 개수 = 10개이진트리와 일반트리의 차이점이진트리의 모든 노드는 차수가 2 이하이다.일반트리는 자식 노드의 개수에 제한이 없다.일반 트리와는 달리 이진트리는 노드를 하나도 가지고 있지 않을 수도 잇다.서..
자료구조 문제 정리 (2) 스택, 큐 1. 스택(1)자료의 삽입과 삭제가 포인터에 의해 정해진 위치에서 수행되는 것을 제한된 자료구조라 하고, 스택과 큐가 해당된다.스택은 후입선출(LIFO) 형태로 포인터 top이 가리키는 곳에서만 삽입과 삭제를 수행한다큐는 선입선출(FIFO) 형태로 삽입은 포인터 rear가 가리키는 곳에서, 삭제는 포인터 front가 가리키는 곳에서 수행한다.스택은  같은 쪽에서 삽입과 삭제가 수행되고, 큐는 서로 다른 쪽에서 삽입과 삭제가 수행된다.스택과 큐의 주요 작업은 삽입(push) 삭제(pop)이며 시간복잡도는 O(1)이다.스택과 큐 모두 배열이나 연결 리스트로 구현 가능하다.스택은 서브루틴 호출이나 인터럽트 발생 시의 복귀 주소 관리, 순환적 프로그램 처리, 후위 표기 방식, 이진트리 순회, 깊이 우선 탐색 등..
자료구조 문제 정리 (1) 배열, 리스트 1. 자료구조선형구조 (배열, 리스트, 스택, 큐)데이터의 항목 사이의 관계가 1:1이며, 선후 관계가 명확한 1개의 선의 형태를 갖는 리스트 구조를 말한다.각 자료 항목 사이의 관계의 표현 방법과 항목의 입출력 방법에 따라 배열, 연결리스트, 스택, 큐, 데크로 나뉘어진다.비선형 구조 (트리, 그래프)데이터의 항목 사이에 1:n 또는 n:m 관계를 갖는 그래프적 특성을 갖는 형태트리, 그래프가 속한다.그래프는 사이클을 허용하며 트리는 사이클을 허용하지 않는다 2. 알고리즘 컴퓨팅 사고에서 주어진 문제의 중요한 특징만으로문제를 간결하게 재정의함으로써 문제 해결을 쉽게 하는 과정을 말한다.알고리즘의 특성은 다음과 같다.입력 : 외부에서 제공되는 자료가 있을 수 있다(0개 이상의 입력이 존재)출력 : 반드시..
알고리즘 시간복잡도 알고리즘 빅오 표기법컴퓨터가 하는 일 : 데이터 저장, 연산어떻게 하면 데이터를 적은 메모리에 저장할까? → 자료구조어떻게 하면 문제를 빠르고 정확하게 해결할 수 있을까? → 알고리즘알고리즘의 효율성을 판단하는 근거로 시간 복잡도와 공간 복잡도를 들 수 있다.시간 복잡도 : 얼마나 빠르게 결과를 출력할수 있을까? T(n)공간 복잡도 : 메모리를 얼마나 사용하는가? S(n)효율성을 판단하는 표기법으로 빅오 표기법, 빅오메가 표기법, 빅세타 표기법이 있다. 빅오 표기법최악일 때의 성능을 판단하는 것이다. 이보다 더 나쁜 경우는 없어를 기준으로 한다 (상한)가장 많이 사용하는 분석방법이다 ↔ 최상일 때의 경우를 판단하는 것은 빅오메가 표기법이다. 시간 복잡도시간 복잡도는 문제를 해결하는데 몇번의 단계를 거쳐야..
선형 자료구조 자료구조내가 저장하려는 데이터를 효율적으로 저장하고 관리하는 방법이 자료구조입니다.어떻게 하면 적은 메모리를 사용해서 내 데이터를 저장하고 관리할수 있을까? 에 관한 것이며 적절한 자료구조의 선택은 실행 성능의 향상을 기대할 수 있게 됩니다.자료구조를 선택하려면 자료구조에 대한 장점, 단점에 대해 알고 있어야 합니다.자료구조는 순차적인 순서를 갖는 선형 자료구조 / 비선형 자료구조로 나눠집니다. 선형 자료 구조1. 배열(선형리스트)배열은 청크 형태로 연속적인 메모리가 할당되는 공간입니다, 배열은 덩어리로 할당되는 자료구조이며 연속적으로 할당되기 때문에 각각의 원소에 접근할땐 0부터 1씩 증가하는 인덱스로 접근합니다.배열은 가장 큰 장점이 임의 접근(random access)입니다. 내가 배열의 특정 원소..
자료구조 트리 트리란 비선형 자료구조이며, 이름 그대로 나무 형태의 자료 구조이다.자식과 부모 관계로 이루어져있다 트리의 용어루트(root) : 트리의 최상위 노드노드(node) : 각 노드는 널 값이나 자식을 가리키는 두 개의 포인터와 데이터를 가진다간선(edge) : 두 노드를 연결하는 데 사용한다리프(leaf) : 자식이 없는 노드를 말한다자식 : 한 노드로부터 가지로 연결 된 아래쪽 노드이다부모 : 한 노드에서 가지로 연결 된 위쪽 노드를 말한다형제 : 같은 부모를 가지는 노드를 말한다높이(height / depth) : 루트부터 리프까지 가장 긴 경로의 간선수를 말한다레벨 : 루트에서 노드까지의 경로에 있는 간선 수를 말한다. 루트의 레벨이 0이며, 가지가 하나씩 아래로 뻗어 나갈 때마다 레벨이 1씩 늘어난다..
그래프 알고리즘 그래프의 모든 정점들을 빠지지 않고 방문하는 것을 순회라고 한다.순회할 때 정점을 한번 방문하면 두번 방문하면 안된다.모든 정점들을 한번씩 빠짐없이 방문하는 것이 순회이고 깊이 우선탐색(DFS)와 너비 우선탐색(BFS)로 나뉘어지게 된다. 깊이 우선탐색(DFS)DFS 방법은 스택이나 재귀 호출로 다음 방문할 정점을 얻는다.같은 정점을 재방문 하는 것을 막기 위해(한번씩만 방문하기 위해) 불방문 배열을 사용한다DFS 방법은 스택 자료구조가 필요한데, 스택은 한쪽 방향으로 PUSH와 POP이 이루어지는 자료구조이다.먼저 그래프의 출발 정점을 하나 잡아준다.트리의 경우 무조건 루트가 출발 정점이지만, 그래프는 어디에서나 출발할 수 있다. 따라서 어느 정점이나 모두 출발 정점이 될 수 있기 때문에 임의적으로 하..

티스토리툴바