728x90 반응형 전체 글58 자료구조 - 트리 (Tree) 1. 트리란? 트리(Tree)란 자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조로 부모-자식 관계로 표현된다. 트리는 1개 이상의 노드를 갖는 집합으로 루트 노드가 존재하고 트리의 부분트리(SUb Tree) 또한 트리 구조를 따른다. 노드가 N개인 트리는 항상 N-1개의 간선을 가진다. 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 두 개의 정점 사이에 반드시 1개의 경로만을 가진다. 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다. 2. 트리와 관련된 용어 루트 노드(root node) : 트리의 최상위 노드로 유일하다. 깊이 (Depth) : 루트 노드에서 해당 노드까지 도달하는데 사용하는 간선의 개수로 루트 노드는 자기 자신까지 도달하는 간선의 개수가 0.. 2021. 1. 27. 자료구조 - 연결 리스트 (Linked List) 1. 연결 리스트란? 연결 리스트(Linked List)란 불연속적 메모리 공간에 데이터를 빈틈없이 저장하며 노드를 연결하여 만든 리스트로 첫 번째 노드를 헤드, 마지막 노드를 테일이라고 한다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져있다. 크기가 고정되어 있지 않아 크기 제한에서 자유롭다. 인덱스 접근이 불가능하다. 2. 시간 복잡도 1) 삽입 - 리스트의 맨 앞/뒤에 삽입하는 경우 : O(1) - 리스트의 중간에서 삽입하는 경우 : O(n) (탐색) 2) 삭제 - 리스트의 맨 앞/뒤에 삭제하는 경우 : O(1) - 리스트의 중간에서 삭제하는 경우 : O(n) (탐색) 3) 탐색 - O(n) 3. 장단점 1) 장점 - 포인터로 연결되어 있어 포인터가 가리키는 노드만 변경하면 되기 때문.. 2021. 1. 26. 자료구조 - 배열(Array) 1. 배열이란? 배열(Array)은 가장 기본적인 자료구조로 동일한 자료형의 데이터를 일렬로 나열한 자료구조로 연속된 메모리 공간에 순차적으로 저장한다. 배열의 크기는 고정되어 있고, 선언할 때 크기를 정하고 후에 변경할 수는 없다. 2. 시간 복잡도 1) 삽입 / 삭제 - 배열의 맨 앞에 삽입 / 삭제하는 경우 : O(n) - 배열의 맨 뒤에 삽입 / 삭제하는 경우 : O(1) - 배열의 중간에 삽입 / 삭제하는 경우 : O(n) 2) 탐색 - O(n) 3. 장단점 1) 장점 - 인덱스를 가지고 있어 바로 접근 가능하다. (자료의 크기가 클수록 매우 유리) - 연속된 메모리 공간에 존재하기 때문에 관리가 편리하다. - 구조가 간단하여 프로그램 작성이 쉽다. 2) 단점 - 데이터 삽입 / 삭제가 어렵다... 2021. 1. 26. 알고리즘 - 합병 정렬 (Merge Sort) 알고리즘 - 합병 정렬 (Merge Sort) 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 합병 정렬은 분할 - (정복) - 결합의 단계로 이루어진다. 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다. 결합 : 정렬된 부분 배열들을 하나의 배열에 합병한다. 합병 정렬은 추가적인 리스트가 필요하며 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다. 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계이다. .. 2021. 1. 26. 알고리즘 - 이진 탐색 (Binary Search) 알고리즘 - 이진 탐색 (Binary Search) 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘으로, 모든 값을 순회해야하는 일반적인 search보다 더 빠르다. 중앙값을 찾는 값에 비교해서 중앙값이 찾는 값보다 크면 왼쪽을 탐색하고 찾는 값보다 작으면 오른쪽을 탐색한다. 최악의 경우에도 탐색 대상을 절반씩 계속해서 줄여나가기 때문에, 탐색 횟수가 logN이다. 따라서 T(N) = O(logN) [ 예시 ] [ 코드 ] def binary_search(arr, target): low, high = 0, len(arr) - 1 while low target: high = mid - 1 if arr[mid] == target: return mid if arr[mid] < target: l.. 2021. 1. 26. 프로그래머스 Level 2 - JadenCase 문자열 만들기 [문제 설명] JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. [제한 조건] s는 길이 1 이상인 문자열입니다. s는 알파벳과 공백문자(" ")로 이루어져 있습니다. 첫 문자가 영문이 아닐때에는 이어지는 영문은 소문자로 씁니다. ( 첫번째 입출력 예 참고 ) [입출력 예] s return 3people unFollowed me 3people Unfollowed Me for the last week For The Last Week [제출] #include #include #include using namespace std; string solut.. 2021. 1. 22. 이전 1 ··· 5 6 7 8 9 10 다음 728x90 반응형
