목록전체 글 (105)
책 읽다가 코딩하다 죽을래
📚 BFS (Breadth-First Search) 란? 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서 넓이 우선 검색을 적용한다. DFS는 인접한 한 노드를 끝까지 탐색했다면 BFS는 인접한 모든 정점을 방문합니다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모드 노드들을 저장하고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 됩니다. 처음에 넣은 노드이므로 큐를 이용해서 BFS를 구현할 수 있다. 📋 BFS 전체 과정 BFS의 알고리즘 방식을 설명하면 다음과 같다. 1. 루트 노드를 큐에 넣는다 2. 현재 큐의 노드를 빼서 visited에 추가한다. 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않..
📚 DFS란(Depth First Search)? DFS는 자료의 검색 트리나 그래프를 탐색하는 방법 중 하나이다. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. DFS는 이름에 나와있는 그대로 끝까지 탐색하는 거에 초점을 맞춥니다. 그래서 그래프의 최대 깊이만큼의 공간을 요구하며, 이는 공간을 적게 쓰는 것입니다. 그러나 최단 경로를 탐색하기는 쉽지 않다. 모든 경로를 탐색하는 것이 아니기 때문입니다. 📋 DFS 전체 과정 DFS의 알고리즘 방식을 설명하면 다음과 같다. 1. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다. 2. 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다. 3. 만약 끝에 도달했다면 리턴한..
📚 병합 정렬이란? 병합 정렬은 정렬할 배열을 더 이상 쪼개질 수 없는 상태까지 나눈 다음 합치면서 정렬을 하는 방법이다. 📋 병합 정렬 전체 과정 병합 정렬은 2가지 과정을 거친다. 정렬할 배열을 나누고(merge sort) -> 합친다(merge) 📋 merge sort 병합 정렬은 더 이상 쪼개질 수 없는 상태 즉, 쪼개진 배열의 길이가 1이 될 때까지 나눈다. 왜냐하면 배열의 길이가 1이면 그 속에 무슨 숫자가 들어있는 정렬이 모두 완료된 상태이기 때문입니다. 시간복잡도를 계산해가면서 배우는 게 낫기 때문에 시간복잡도 관점에서 과정을 설명해드리겠습니다. 다음과 같은 배열을 정렬해봅시다. 처음 배열의 개수는 N 개라고 합시다. 그다음은 N인 배열을 반으로 나눕니다. 그러면 길이가 N/2개인 배열 2..
📚 그래프 정의 그래프는 연결되어 있는 정점과 정점 간의 관계를 표현할 수 있는 비선형 자료구조이며, 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조이다. 그래프는 TCP 라우팅 알고리즘과 페이스북 관계망 등에서 자주 쓰이는 자료구조이다. 🧬 그래프 구조 노드(Node) : 연결 관계를 가진 각 데이터를 의미한다. 정점(Vertex)라고도 한다. 간선(Edge) : 노드 간의 관계를 표시한 선 인접 노드(Adjacent Node) : 간선으로 직접 연결된 노드(또는 정점) 📝 그래프 표현 방법 그래프를 코드로 표현하는 방법은 LinkedList와 Array가 있는데 ☝ LinkedList는 각 정점간의 관계를 노드로 연결하여 표현한다. head를 3으로 가리..
📚 힙 정의 힙은 데이터에서 최댓값과 최솟값을 찾기 위해 고안된 완전 이진 트리이다. 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조이다. 즉 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다. 그러면 가장 큰 값이 모든 자식보다 크기 때문에 가장 위로 간다. 바로 루트 노드로 말이다. 이렇게 아래로 갈수록 작고 위로 갈수록 커지는 힙은 Max Heap이라 하고 이와 반대인 경우는 Min Heap이라 한다. 그런데 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 하는 규칙이 있다. 🤔 그러면 힙에 새로운 노드를 삽입하거나 이미 존재하는 노드를 삭제할 때 규칙을 어기지 않게 하려면 어떻게 해야 할까? 지금부터 노드 삽입과 노드 삭제 과정을 훑어보자 ..
개발자 취업 필수 개념 3주 차에는 주로 보안과 관련된 얘기를 다루었다. 🧾 목차 1. 대칭 키와 비대칭 키 2. 프로토콜, HTTP 3. HTTPS, SSL 4. SSL의 원리 5. 쿠키 6. 세션 1. 대칭 키와 비대칭 키 더보기 📖 개요 우리는 실생활에서 애플리케이션이나 웹을 통해 자신의 정보와 수많은 데이터들을 다른 서버들과 송수신을 합니다. 하지만 송수신하는 과정에서 누군가가 내 데이터를 도청하거나 위변조를 한다면 대단히 위험해질 것입니다. 그래서 우리는 제 3자가 도청하더라도 무슨 데이터인지 모르게 하기 위해 평문을 암호화해서 암호문으로 바꿔야 하며, 목적지에 도착하면 보내준 데이터를 읽을 수 있도록 암호문을 복호화해서 다시 평문으로 바꿔줘야 합니다. 📖 암호 알고리즘의 종류 암호 알고리즘은 ..
🧾 목차 1. 쿠키(Cookie) 2. 세션(Session) 3. 쿠키와 세션 차이 정리 1. 쿠키(Cookie) 🍪 쿠키 정의 사용자가 방문한 웹페이지에서 이용된 환경설정 및 기타 정보를 사용자의 컴퓨터에 저장하는 작은 파일입니다. 🔗 GoogleAds 고객센터 쿠키는 웹사이트를 방문할 때마다 읽히고 수시로 새로운 정보로 바뀔 수 있는 매개체입니다. 페이티 탐색을 하거나 지역 및 언어, 성능에 대한 보고 혹은 마케팅 용 등 다양한 용도로 사용됩니다. 이처럼 쿠키는 유저들의 효율적이고 안전한 웹 사용을 보장하기 위해 웹 사이트에 많이 사용되고 있습니다. 쿠키는 웹사이트의 접속 시 접속자의 개인장치에 다운로드되고 브라우저에 저장되는 작은 텍스트 파일입니다. 웹사이트는 쿠키를 통해 웹사이트를 접속자를 인식하..
📚 트리의 정의 트리는 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조이다. 트리는 대표적인 사용 예시는 컴퓨터의 폴더 구조이다. 파일이 어느 경로에 있는지 그 경로에는 어떤 폴더들이 포함되는지 나타내야 하기 때문이다. 트리의 구조는 다음과 같다 🧬 트리의 구조 Node : 트리에서 데이터를 저장하는 기본 요소 Root Node : 트리 맨 위에 있는 노드 Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node : 어떤 노드의 상위 레벨에 연결된 노드 Child Node : 어떤 노드의 하위 레벨에 연결된 노드 Leaf Node(Terminal Node) : Child Node가 하나도 없는 노드 S..