본문 바로가기
반응형

자료구조7

[JavaScript] ListNode (연결리스트 - linked list) 코딩테스트 문제를 풀다보니 ListNode를 사용해야하는 문제를 접하게 되어 다시 정리할 겸 포스팅하려 합니다. ListNode란? 자바스크립트에서 ListNode란 연결 리스트(linked list)의 기초 구성 요소인 노드(node)를 의미해요. 연결 리스트는 배열과 마찬가지로 선형적인 데이터를 다루지만, 배열과는 구조가 다르다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(또는 참조)를 포함하고, 메모리에서 연속적인 위치를 차지하지 않아, 덕분에 데이터의 삽입과 삭제가 효율적이지만, 특정 요소를 검색할 때는 배열보다 느릴 수 있다. ListNode 구현하기 Node 클래스: 데이터와 다음 노드를 가리키는 포인터를 속성으로 가지는 간단한 클래스입니다. class Node { constructor(.. 2024. 3. 7.
코딩테스트란? 코딩테스트란? 주로 IT 및 프로그래밍 관련 채용에서 사용되는 시험 기업에서 채점 시스템을 도입하여 응시자 수를 줄이는 효과도 존재 기술역량 + 문제 해결 능력 + 코드 구현 능력 확인 2. 코딩테스트 유형 1. 온라인 HackerRank, LeetCode, 대체로 인터넷 검색을 허용, 자신의 개발환경에서 진행 2. 오프라인 회사(시험장)에 방문하여 응시, 대체로 인터넷 검색이 허용되지 않고, 회사에서 제공하는 환경에서 진행, 감독관이 라이브로 지켜보기도 함 3. 기업별 코딩 테스트 유형분석 ex) 삼성전자 3시간 2문제 중 커트라인 1문제(상황에따라 바뀜), 완전 탐색, 구현, DFS/BFS, 시뮬레이션, 오프라인 카카오 5시간 7문제 중 커트라인 3-4문제, 그리디, 구현, 문자열, 자료구조, 온/오.. 2023. 12. 11.
[Javascript] 자료구조 - 그래프(Graph) 그래프(Graph) 사물의 정점(vertex)과 간선(edge)으로 나타내기 위한 도구 그래프는 두가지 방식으로 구현 1. 인접 행렬(adjacency matrix) : 2차원 배열을 사용하는 방식 (각각 노드에서 노드로 움직일 때 드는 비용) 인접행렬 - 무방향 무가중치 그래프 모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다. 모든 간선에 가중치가 없는 그래프를 무가중치 그래프라고 한다. 무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 행렬로 출력 인접 행렬 - 방향 가중치 그래프 모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다. 모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다. 방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 행렬로 출.. 2023. 11. 24.
[Javascript] 자료구조 - 큐(Queue) 큐(Queue) : 먼저 삽입된 데이터가 먼저 추출되는 자료구조 => 탐색 활용빈도에서 많이 사용 연결리스트로 큐 구현 큐를 연결리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장할 수 있다. 연결 리스트로 구현할 때는 머리(head)와 꼬리(tail) 두개의 포인터를 가진다. 머리(head) : 남아있는 원소 중 가장 먼저 들어온 데이터를 가리키는 포인터 꼬리(tail) : 남아있는 원소 중 가장 마지막에 들어온 데이터를 가리키는 포인터 삽일할 때는 꼬리 위치에 데이터 추가 삭제할 때는 머리 위치에서 데이터 삭제 큐 동작 속도 비교 (배열 vs 연결 리스트) 다수의 데이터를 삽입 및 삭제할 때에 대해 수행 시간을 측정 단순히 배열 자료형을 이용할 때보다 연결 리스트를 사용할 때 수행 시간 관점에서.. 2023. 11. 24.
[Javascript] 자료구조 - 스택(stack) 스택 : 먼저 들어온 데이터가 나중에 나가는 자료구조 새로운 원소를 삭제할 때는 마지막 원소가 삭제 전체 연산: 삽입 3 - 삽입 5 - 삭제 - 삽입 1 - 삭제 - 삽입 8 - 삽입 9 => 3, 8, 9 연산 시간 복잡도 설명 1 삽입(Push) O(1) 스택에 원소 삽입 2 추출(Pop) O(1) 스택에서 원소 추출 3 최상위 원소(Top) O(1) 스택의 최상위 원소 확인 4 Empty O(1) 스택이 비어 있는지 확인 Javascript 배열 자료형 - 일반적으로 스택을 구현할 때, Javascript의 배열 자료형을 사용 1. push() : 마지막 위치에 원소를 삽입, 시간 복잡도 O(1) 2. pop() : 마지막 위치에서 원소를 추출, 시간 복잡도 O(1) let stack = []; .. 2023. 11. 24.
[Javascript] 자료구조 - 배열(Array)과 리스트(List) 배열(Array) 가장 기본적인 자료구조 여러개의 변수를 담는 공간 배열은 인덱스(index)가 존재, 인덱스는 0부터 시작 특정한 인덱스에 직접 접근 가능 -> 수행시간: O(1) 배열의 특징 컴퓨터의 메인메모리에서 배열의 공간은 연속적으로 할당 장점: 캐시 히트 가능성이 높으며 조회가 빠르다. 단점: 배열의 크기를 미리 지정해야하는것이 일반적이므로, 데이터의 추가 및 삭제에 한계가 있다. 연결 리스트(Linked List) 연결 리스트는 컴퓨터의 메인 메모리상에서 주소가 연속적이지 않다. 배열과 다르게 크기가 정해져있지 않고, 리스트의 크기는 동적으로 변경 가능 장점: 포인터(pointer)를 통해 다음 데이터의 위치를 가리킨다는 점에서 삽입과 삭제가 간편하다. 단점: 특정 번째의 원소를 검색 할 때.. 2023. 11. 23.
반응형

티스토리툴바