🥬 상추의 공간

이번 글에서는 컴퓨터 네트워크가 무엇인지 알고, 패킷, 네트워크의 종류인 LAN과 WAN에 대해 알아보고자 한다. 컴퓨터 네트워크란? 컴퓨터 네트워크에 대해 말하기 전, 일단 네트워크가 무엇인지 짚고 가겠다. 네트워크는 두 개 이상의 무언가가 연결되어 정보를 주고 받는 구조를 뜻한다. 일상생활로 예를 들어보자면, 소셜 네트워크 서비스(SNS)가 있다. 이는 온라인 상에서 사람과 사람간에서 정보를 공유하는 구조다. 그 외에도 도로와 철도의 네트워크, 물류 네트워크 등과 같이 다양한 네트워크가 있다. 그럼 이제 컴퓨터 네트워크가 무엇인지 예측할 수 있을 것이다. 두 대 이상의 컴퓨터 간에 정보(데이터)를 공유하는 것, 이것이 컴퓨터 네트워크다. 이제부터 컴퓨터 네트워크를 간단하게 네트워크라고 칭하겠다. 네트..

단순 연결 리스트란? 연결리스트는 데이터를 저장하는 자료구조 중 하나이다. 연결리스트 종류도 여러개 있지만, 지금 살펴보려는 것은 단순 연결 리스트이다. 연결리스트는 여러 개의 노드(Node)로 이루어져 있다. 단순 연결 리스트는 2개의 필드를 가지고 있는데, 데이터 필드와 다음 노드 주소를 가지고 있는 링크 필드(포인터)로 구성되어 있다. create, search, insert, remove 등을 효율적으로 구현하기 위해 사용한다고 한다. 구현 코드 전체적인 구현 코드는 다음과 같다. class LinkedList { constructor() { let init = new Node("init"); this.head = init; this.tail = init; this.currentNode = und..

학교 전공 공부와 더불어 이전부터 네트워크 공부의 필요성을 느껴서 널널한 개발자님의 네트워크 강좌를 듣고 정리하고자 한다. 해당 강좌는 사전 지식으로 운영체제 지식을 알고 있어야하는데, 운영체제도 이제야 막 전공으로 배우기 시작해서 그냥 맨 땅에 해딩하면서 알아가보고자 한다. 완전히 이해가 되지 않아도 일단은 다 기록할거라 글이 좀 더러울 수 있다.. 이 나중에 한번 싹 공부하고 복습할 때 글을 다듬을까 한다. 들어가기 전... 다음 용어들은 다 같은 의미이다. 네트워크 = Internet = IP 프로토콜 = 인터넷 프로토콜 기반으로 작동하는 네트워크 이 중에서 가장 유명한게 4계층 프로토콜인 TCP/IP다. 해당 강좌는 TCP/IP를 이해하는 것을 목표로 두고 있다. 이해가 안돼도 일단 외워서 끝내도..

리스트의 중간 값을 찾아 원하는 값과 비교해서 진행하는 알고리즘이다. 이 알고리즘을 이용하려면 먼저 정렬이 되어있어야한다. 중간값 = (최솟값 + 최댓값) / 2 중간값 위치에 해당하는 값과 검색하고자 하는 값과 비교한다. 만약 찾고자 하는 값이 중간 값보다 크다면 중간 값 이하는 검색하지 않고, 작다면 중간 값 이상은 검색하지 않는다. 이렇게 원하는 값 찾을 때까지 검색 범위를 반씩 쪼개며 찾는다. 이분 검색의 시간 복잡도는O(logN)이다. 아래는 예시 문제 및 풀이코드다. [인프런] Node.js / 섹션7-정렬과 그리디, 결정알고리즘 / 10. 이분검색 문제 임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이..

선택 정렬 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘이다. 제일 작은 원소를 찾아서 탐색 기준점으로부터 가장 앞 원소와 바꾸고 이를 끝까지 반복한다. 시간복잡도는 O(N^2)이다. 데이터 커질수록 엄청 커지므로 최대한 피해야할 시간복잡도다. 아래는 예시 문제 및 풀이방법이다. [인프런] Node.js / 섹션7-정렬과 그리디, 결정알고리즘 / 1. 선택정렬 문제 N개이 숫자가 입력되면 오름차순으로 정렬하여 출력 풀이 function solution(arr) { let answer = arr; let min, tmp, index; for (let i = 0; i < answer.length; i++) { min = Number.MAX_SAFE_INTEGER; for (let j = i; j < ..

스택 마지막에 들어간 데이터가 먼저 나가는 자료구조다. LIFO(Last Input First Out) 구조를 가진다. 실생활 예로는 페이지 뒤로가기, 되돌리기(Ctrl + Z), 책상에 쌓인 책이 있다. 큐 먼저 들어간 데이터가 먼저 나가는 자료구조다. FIFO(First Input First Out) 구조를 가진다. 실생활 예로는 줄을 서는 것이 있다.

슬라이딩 윈도우란? 슬라이딩 윈도우 알고리즘은 투 포인터 알고리즘과 유사하게 부분 배열들을 활용하는 알고리즘이다. 투포인터와 다른 점은 부분 배열의 길이(크기)가 고정적이다. 그래서 포인터 변수가 2개일 필요가 없다. 이름 그대로 고정적인 너비를 가진 창문을 두고 옆으로 한칸씩 이동하며 값을 구하는 방법이다. 예를들어, N개의 원소를 갖는 배열이 있다. 이때 W의 너비를 갖는 창문이 있다. 너비가 3인 창문을 제일 왼쪽에 배치하고, 창문을 왼쪽에서 시작하여 한 칸씩 오른쪽으로 이동한다. 매 순간 창문 안에서의 정보를 활용해 유추해서 값을 구한다. 즉, 같은 너비의 연속 구간들을 연속적으로 처리할 때 주로 사용되는 테크닉이다. 인접한 구간들 사이에 겹치는 정보를 최대한 활용하는 것이 포인트다. 관련 문제 ..

투 포인터란? 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. 여기서 포인터는 C언어의 포인터가 아니라 작업을 처리하기 위해 생성한 변수이다. 포인터라는 변수를 두개를 선언해서 투 포인터라고 부른다. 이분탐색 문제를 투 포인터로도 해결 할 수 있다. 완전 탐색 알고리즘으로 하면 O(N^2)의 수행시간이 나오는데, 투포인터로 시간복잡도를 O(N)으로 줄일 수 있다. 예시 문제: N개의 자연수로 구성된 수열이 있을 때, 합이 M인 부분 연속 수열의 개수 구하기. 수행 제한 시간은 O(N) 투 포인터로 문제 해결하는 방법 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다. 현재 부분 합이 M과 같다면,..