본문 바로가기

programming study/Computer Science

 (28)
자료구조와 알고리즘 - 그래프 본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다. 1. 그래프란? 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조 정점(Node) 집합과 간선(Edge) 집합으로 표현 특징 여러개의 간선을 가질 수 있음 방향 그래프, 무방향 그래프로 나눌 수 있음 간선은 가중치를 가짐 사이클이 발생 가능 2. 그래프의 종류 무방향 그래프 간선으로 이어진 정점끼리는 양방향으로 이동이 가능 (A, B), (B, A)는 같은 간선 취급 방향 그래프 간선에 방향성이 존재하는 그래프 , 는 다른 간선으로 취급 연결 그래프 모든 정점이 서로 이동 가능한 상태인 그래프 특정 정점 -> 다른 정점까지의 모든 경우의 수가 이동 가능해야 함 비연결 그래프 특정 ..
자료구조와 알고리즘 - 해시 테이블 본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다. 1. 해시 테이블이란? 해시테이블은 한정된 배열 공간에 key를 index로 변환하여 값을 넣음 key와 value를 받아 Hasing하여 나온 index에 값을 저장하는 선형 자료구조 삽입은 O(1) 키를 알고 있으면, 삭제, 탐색도 O(1)로 수행 Bucket: 각 테이블에 해당하는 index 테이블의 각 요소는 key, value를 둘 다 저장 빠르게 값을 찾아야하는 경우, 해시 테이블을 사용하기 JavaScript에서의 Array, Object가 Hash Table JavaScript Map의 경우도 Hash Table 다양한 자료형도 key로써 사용 가능 JavaScript Set의 ..
자료구조와 알고리즘 - 큐 본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다. 1. Queue란? 선형 자료구조 First In First Out 먼저 들어온것이 먼저 나감 Linear Queue, Cicular Queue Front: Queue의 맨 앞 Rear: Queue의 맨 뒤 DeQueue: Queue의 요소를 빼는 것 EnQueue: Queue의 요소를 넣는 것 대기열이라고 할 수 있음 2. Linear Queue 선형 큐 Array로 표현 가능 한정된 공간인 Array에서 구현하기에는 어려움이 있음 앞요소가 DeQueue가 되어도 그 만큼 배열을 더 사용할 수는 없음 EnQueue가 해당 배열의 length만큼만 가능 JavaScript에서는 위 문제는 없지..
자료구조와 알고리즘 - 스택 본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다. 1. 스택이란? Last In First Out이라는 개념을 가진 선형 자료구조 나중에 들어온 것이 가장 처음에 나오게 됨 맨 위에 있는 요소 Top 2. 스택의 동작 원리 push: 요소 넣기 pop: 요소 빼기 가장 맨 위에 있는 요소만 컨트롤함 스택 메모리: 함수가 호출되며 생성되는 지역 변수, 매개 변수가 저장되는 메모리 3. 스택 구현 Array로 구현 스택을 배열로 구현할 수 있음 배열은 순차적으로 요소가 추가 됨(push) 가장 끝의 요소를 뺄 수 있음(pop) JavaScript의 배열은 스택을 구현하는 것에 유리 Reference 프로그래머스의 코딩테스트 광탈 방지 A to Z..
자료구조와 알고리즘 - 연결 리스트 본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다. 1. 연결 리스트란? 각 요소를 포인터로 연결하여 관리하는 선형 자료구조 각 요소는 노드라고 불리고 데이터 영역과 포인터 영역으로 구성 2. 연결 리스트의 특징 메모리가 허용하는한 요소를 제한없이 추가할 수 있음 탐색은 O(n)이 소요 추가와 삭제가 반복되는 로직에서 사용하면 유용 O(1)이 소요 Singly Linked List, Doubly Linked List, Circular Linked List 3. 배열과 차이점 메모리에서의 차이 배열은 순차적으로 요소들을 관리하므로 메모리 영역을 연속적으로 사용 연결 리스트는 각 데이터가 퍼져 있음 연결 리스트는 퍼져있는 메모리 영역을 알기 위해 ..
자료구조와 알고리즘 - 객체 본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다. 1. 객체란? 객체는 여러 값을 key-value로 결합시킨 복합 타입 2. JavaScript에서의 객체 생성 방법 // 1. 생성자 함수를 사용하여 만들기 const exampleObj1 = new Object(); ​ // 2. 객체 리터럴 const exampleObj2 = {}; 객체 요소 추가 방법 const exampleObj = {}; ​ // 1. 중괄호를 사용하기 exampleObj["name"] = 'siru'; ​ // 2. 점 사용하기 exampleObj.isCat = true; 객체 요소 삭제 방법 const exampleObj = { name: 'siru', isCa..
자료구조와 알고리즘 - 배열 본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다. 1. 배열이란? 순차 리스트라고도 불림 연관된 데이터를 연속적인 형태로 구성 배열의 원소는 순서 대로 번호(index)가 붙음 2. 배열의 특징 고정된 크기를 가짐 보통은, 동적으로 크기를 늘릴 수 없음 반면, JS와 같은 스크립트 언어는 동적으로 크기가 증감 index를 사용하여 해당 index에 해당하는 원소에 접근할 수 있음 상수시간이 걸림(O(1)) 원소를 삭제하면, 해당 index의 자리는 비게 됨 빈 자리를 채우기 위해서 뒤의 요소들 하나하나를 순차적으로 앞으로 당겨 채우게 됨 삭제 후 순서를 맞추려면 O(n)이 소요됨 배열의 요소를 추가하는 경우도 이와 같아, O(n)이 소요 됨 ..
자료구조와 알고리즘 - 자료구조와 알고리즘이란, 자료구조의 종류, 시간 복잡도 본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다. 1. 자료구조와 알고리즘이란 자료구조와 알고리즘을 올바르게 사용하면 좋은 프로그램을 만들 수 있음 자료구조 메모리를 효율적으로 사용하고 안정적으로 데이터를 처리 스택, 큐, 그래프, 트리 등 특정 상황에서 유용한 자료구조가 있음 상황에 맞게 적절하게 선택 알고리즘 특정 문제를 효율적이고 빠르게 해결하는 것이 궁극적인 목표 정해진 일련의 절차와 방법을 공식화한 형태로 표현 이진탐색, 최단거리 탐색, DFS, BFS 2. 자료구조의 종류 단순 구조 정수, 실수, 문자열, 논리 선형 구조 배열, 연결 리스트, 스택, 큐 비선형 구조 트리, 그래프 선형 구조 자료들이 선형으로 나열 배열, 연결 리스트..

티스토리툴바