매일코딩

그래프 - Vertex, edge로 구성된 자료구조 - Vertex == Node 그래프 Graph - 네비게이션 길찾기 - 게임 내 캐릭터 이동 - 지식 그래프 쾨니히스베르크의 다리 문제 - 한 다리를 두번 이상 건너지 않고 모든 다리를 건널 수 있나? -> 불가능함 방향 그래프 Directed Graph 가중치 그래프 루프 loop 순환 그래프 Cyclic Graph 그래프의 구현 - 인접 행렬 - 2차원 배열로 구현 단점은 메모리를 많이 써야한다, 새로운 노드 생기면 연산량이 늘어난다. 인접 리스트 - Vertex 갯수 만큼의 list 사용 효율적인 메모리 공간 생성 추가 수월함 인접행렬보다 edge를 찾는데 오래 걸릴 수 있음 그래프 순회 - 그래프 탐색 - 위상 정렬 - 그래프의 최단거리 DFS..

힙 - 완전 이진 트리 - 최대 힙 -- 부모 노드의 값은 항상 자식 노드보다 크거나 같음 -- 루트노드 = 트리의 최댓값 - 최소 힙 -- 부모 노드의 값은 항상 자식 노드 보다 작거나 같음 -- 루트 노드 = 트리의 최솟 값 힙 - 최대/최소를 기준으로 데이터를 찾는 연산을 빠르게 할 수 있음 -> O(1) - 삽입 O(logN) - 삭제 O(logN) 우선순위 큐 - 일반 큐 -- 먼저 들어온 데이터가 먼저 나가는 FIFO 데이터 구조 - 우선순위 큐 -- 데이터가 들어온 순서에 상관없이 -- 우선순위가 높은 데이터 순으로 처리 -- ex: 작업 스케줄링 힙 정령 Heap SORT - 힙 자료구조의 특성을 이용한 정렬 방법 Heap을 배열로 표현하기 - 완전 이진 트리이기 때문에 빈 값이 없는 일차..

트리 - 한 노드가 여러 노드를 가르킬 수 있음 - 비 선형적 자료구조 - 그래프 - 데이터 구조의 계층적인 표현 - root는 단 한개만 존재 - 부모 자식 관계 존재 - 트리 안에 트리가 있는 sub tree 구조 트리 - 이진 트리 - AVL 트리, 레드-블랙 트리 - B-트리, B+트리 - 세그먼트 트리 - 트라이 이진 트리 - 각 노드가 최대 2개의 자식 노드를 가지는 트리 정 이진 트리 (full binary tree) - 모든 노드가 2개의 자식을 가지거나 자식이 없을 때 포화 이진 트리 (Perfect Binary tree) - 모든 노드가 2개의 자식을 가지고 leaf 노드가 같은 레벨일때 - 높이가 h인 포화 이진 트리에서 노드 개수는 2^h -1 (root때문에 1개 빼줌) - Lea..

이진탐색 오름차순 정렬돼있는 리스트 내에서 특정 값의 인덱스를 찾는 알고리즘 7이라는 숫자의 인덱스를 빠르게 찾는 방법은 리스트의 절반 인덱스 값을 확인하고 그 값보다 작으면, 그 앞의 절반 리스트만을 남기고 또 그 리스트의 절반 인덱스 값을 확인하고 또 그 값보다 작으면 절반의 리스트만을 남기는 절차를 계속 진행한다. 장점 빠른 속도 시간복잡도 O (logN) 단점 정렬된 리스트에서만 사용 가능 정렬 - 안정정렬 vs 불안정 정렬 -- 중복된 값의 순서 보장 여부 In-place정렬 vs Out-of-place정렬 - 원본 데이터 내 정렬의 여부 Bubble SORT - 인접한 두 원소를 비교 - 두 값이 정렬되지 않았다면 SWAP - 정렬이 완료된 원소를 제외하고 위의 과정을 반복 - O(N^2) -..

해시의 예시 회원정보 사진 : 홍길동의 사진 이름 :홍길동 나이 :20 전화번호 : 01012345678 이렇게 12칸의 서랍중 홍길동의 회원정보가 담긴 곳을 항상 매번 찾으면 힘드니까 홍길동의 사진 -> 고유의 회원정보 찾아주는 함수 -> 항상 일정한 12가지 색 중 하나로 반환 따라서 KEY : 홍길동의 사진 VALUE: 홍길동의 회원정보가 들어있는 서랍 해시 테이블 - Key, Value로 값을 저장 - 데이터간 순서 존재 X Hashing - Key - 키를 기준으로 값을 매핑 - 고유한 값 (중복 X) Hashing Function -> 임의의 데이터를 특정 값으로 매핑시키는 함수 좋은 해시 함수? - 키 값을 고르게 분포 시킨다 - 빠른 계산 - 충돌을 최소화 해시 충돌? - 키 값이 다른데 ..

Stack - 후입선출 (Last in First Out LIFO) - 인터넷 브라우저 뒤로가기 - Ctrl + z - 다시 되돌리기 먼저들어간게 먼저나간다. Stack - push : 데이터 추가 - pop : 데이터 제거 - top : 맨 위 데이터 가져오기 - peek : 맨 위 데이터 가져오기 Queue - 선입선출 (First in Fast Out -FIFO) - 순서가 보장된 처리 - 사용자가 몰린 서버 - 놀이공원 Queue - push, offer, add : 큐 추가 - pop, poll : 큐 삭제 - peek : 큐 가져오기 Queue의 구조 Queue는 배열로 구현한다면,,, 매우 비효율적이다 - 값을 하나만 삭제해도 모든 원소들을 앞으로 당겨야 하기 때문에 (O (n)) - Lin..

Double Linked List의 생김새는 다음과 같다. prev 라는 포인터가 생기므로 사용하는 자원은 늘어났다. 공간을 더 사용함에도 분명한 장점이 있다. double Linked list를 초기화 하면 더미노드를 다음과 같이 2개를 갖게 된다. Linked List에서 맨 마지막에 값을 하나 추가하는게 O (n) 의 시간이 걸렸지만 double Linked List에서는 Tail 의 노드가 있기 때문에 O (1) 만에 뒤에 값을 추가할 수 있게 된다. 또한 double Linked list는 값을 검색할때 TAIL에서도 시작 가능하기 때문에 뒤에 가까운 값들은 TAIL로 부터 시작하여 값을 검색하여 가지고 온다. 따라서 O (1/2 * n) 이지만, 점근법을 쓰면 O (n)임 Double Link..

LinkedList 삽입, 삭제, 검색 LinkedList의 생김새 LinkedList 검색 - 연결리스트는 인덱스를 접근할 수 없기 때문에 검색하기 위해서는 next로 n번 움직여야 한다. LinkedList 추가 LinkedList 삽입 LinkedList 삭제 LinkedList의 장점 - 배열의 복사나 재할당없이 데이터 추가 가능 - 유연한 공간 LinkedList의 단점 - 데이터 접근에 대한 시간이 늘어남 읽는데 유리한 자료구조는 Array 삭제하고 변경하는데 유리한 자료구조는 LinkedList LinkedList 구현 - Head 더미 노드를 두면 연결 리스트를 구현하는데 편리하다. - 연결리스트는 노드 기반이다. - 노드는 class로 만들어준다. Linked List의 데이터 삽입 - ..

자료구조와 알고리즘을 해야하는 이유 - 취업 - 코딩테스트 - 면접 --arraylist와 linkedlist의 차이를 내부 구현관점에서 설명하시오 --merge sort의 시간복잡도를 증명하시오 (O(nlogn)) - 컴퓨팅적 사고 능력 현업에서 - 알고리즘과 자료구조르르 모르면 해결할 수 없는 문제들이 존재 - 자료구조의 내부 구현을 모르면 잘못 사용하기 쉽다. - 수억개의 데이터 중 내가 원하는 결과를 빠르게 찾으려면? - 한정된 자원(시간, 공간)으로 최적의 결과를 내려면? 자료와 자료 구조 - 자료를 어디에 어떻게 관리할까 --검색, 순회, 저장, 삭제, 변경, 스왑 - 자료를 담는 추상적인 틀 Data Data Structre - 컴퓨터의 자원은 한정적 - 제한된 제약조건 내에 정확한 결과를 ..

Algorithm - 목표 달성, 결과물 생성, 수학, 논리 해결 - 얼마나 더 효율적으로 문제를 푸느냐 - 최적의 방법으로 문제를 풀어야 https://www.hackerrank.com/ HackerRank HackerRank is the market-leading technical assessment and remote interview solution for hiring developers. Learn how to hire technical talent from anywhere! www.hackerrank.com https://leetcode.com/ https://programmers.co.kr/ 알고리즘 조건 - 외부 인풋 - 1개 이상 결과 - 명백함 - 무한 루프가 아니며 - 단순 명로 Cl..