gaori

그래프 정점과 간선으로 이루어져 있다 방향성이 없는 그래프를 가리켜 무방향 그래프 방향정보가 포함된 그래프를 가리켜 방향 그래프, 다이그래프 그 중에서 각각의 정점에서 다른 모든 정점을 연결한 그래프 완전 그래프 간선에 가중치 정보(두 정점 사이의 거리, 두 정점 사이의 걸리는 시간...)를 둔 가중치 그래프 그래프의 표현 그래프 G의 정점 집합 V(G) 그래프 G의 간선 집합 E(G) 으로 표시할때 정점 A 에서 정점 B 간의 간선 하나있는 무방향 그래프는 V(G) = {A, B} E(G) = {} 로 나타낼 수 있다 방향 그래프에서 와 는 다른 간선 이다 그래프의 구현 인접 리스트 배열 또는 해시테이블로 구현하여 각 인덱스마다 존재하는 또 다른 리스트는 연결리스트, 배열 어떤 것으로 구현해도 상관없다..

힙 차곡차곡 쌓아 올린 더미 루트노드로 갈 수록 값이 커지면 최대 힙 루트노드로 갈 수록 값이 작아지면 최소 힙 최대 힙, 최소 힙 둘 다 우선순위에 맞게 데이터를 저장하고 삭제한다 힙은 우선순위 큐 구현에 어울리는 완전 이진 트리의 일종이다 힙 구현 저장과 삭제 연산 힙은 새로운 노드를 추가한 이후에도 완전 이진 트리를 유지해야 하기 때문에 연결 리스트로 구현 하게되면 새로운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않다 그래서 배열로 구현해야 한다 배열로 구현 시 배열의 인덱스가 0인 위치는 사용하지 않고 노드의 고유번호에 맞게 편의성을 준다 왼쪽 자식 노드의 인덱스 값 = 부모 노드의 인덱스 값 * 2 오른쪽 자식 노드의 인덱스 값 = 부모 노드의 인덱스 값 * 2 + 1 부모 노드의 인덱스 ..

트리 비선형 자료구조 계층적 관계를 표현하는 자료구조 노드 간선 루트 노드 단말 노드 내부 노드 이진 트리 루트 노드를 중심으로 두 개의 서브 트리 나뉘어진 두 서브 트리도 모두 이진 트리 포화 이진 트리 모든 레벨이 꽉 찬 이진 트리 완전 이진 트리 왼쪽에서 오른쪽으로 순서대로 빈틈없이 채워진 이진트리 이진 트리 구현 배열 기반과 연결 리스트 기반이 있다 typescript 이진 트리의 순회 루트 노드를 기준으로 순회한다 전위 순회(Preorder Traversal) : 루트 노트를 먼저 루트 - 왼쪽 - 오른쪽 중위 순회(Inorder Traversal) : 루트 노드를 중간 왼쪽 - 루트 - 오른쪽 후위 순회(Postorder Traversal) : 루트 노드를 마지막에 왼쪽 - 오른쪽 - 루트 순..

큐 FIFO(First-In-First-Out) 순서대로 처리된다 매표소 앞에 서 있는 사람들을 생각하면 된다 너비 우선 탐색(breadth-first search), 캐시를 구현하는 경우에 사용 예를 들어 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장해서 노드를 접근한 순서대로 처리할 수 있게 된다 큐 연산 enqueue(item) : item을 리스트의 끝부분에 추가한다 dequeue() : 리스트의 첫 번째 항목을 제거한다 peek() : 큐에서 가장 위에 있는 항목을 반환한다 isEmpty() : 큐가 비어 있는지 확인 비어 있다면 true 반환 큐 구현 typescript

스택 쌓아 올린다 문제의 종류에 때라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다 LIFO(Last-In-First-Out) 쌓여있는 접시를 생각하면 된다 재귀 알고리즘, 깊이 우선 탐색(depth-first search)알고리즘을 사용할 때 유용하다 스택 연산 pop() : 스택에서 가장 위에 있는 항목을 제거한다 push(item) : item 하나를 스택의 가장 윗 부분에 추가한다 peek() : 스택의 가장 위에 있는 항목을 반환한다 isEmpty() : 스택이 비어 있는지 확인 비어 있다면 true 반환 스택 구현 스택을 구현하기 위해서 연결리스트 자료구조를 사용 typescript

연결리스트 차례로 연결된 노드를 표현하는 자료구조 단방향, 양방향 단방향의 각 노드는 다음 노드를 가리킨다 양방향의 각 노드는 다음 노드와 이전 노드를 가리킨다 구현 간단하게 연결리스트 구현 python class Node: def __init__(self, d): self.data = d self.next = None def appendToTail(self, d): end = Node(d) while(self.next != None): self = self.next self.next = end def allGet(self): while(self.next != None): print(self.data) self = self.next print(self.data) node = Node("0") node.a..

해시테이블 효율적인 탐색을 위한 자료구조 key를 vaslue에 대응 key : value 구현 연결리스트(linked list) 해시 코드 함수(hash code function) 키의 해시 코드를 계산한다 hash(key) % array_length 방식으로 해시코드를 이용해 배열의 인덱스를 구한다 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 있다 충돌을 대비해 연결리스트를 이용 3번째에서 충돌이란 서로 다른 두개의 키가 같은 해시 코드를 가리키거나 서로다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우

단어입력은 되지만 한 사람이 여러번 입력이 가능하고 중복단어가 되는 문제가 있었습니다 이 기능을 추가하기 위해 데이터 베이스가 있으면 좋지만 그럼 너무 커지기 때문에 오로지 서버에서만 데이터를 관리하도록 하겠습니다 계속 진행을 하다보니 클라이언트에서 socket.id가 메세지를 보낼때 마다 바뀌는 문제를 발견해서 처음 접속을 했을때만 소켓아이디를 사용하도록 하겠습니다 중복방지 중복을 방지하는 것을 쉽게 가능합니다 App.js에서 word 를 담는 list가 있었는데 onValid 함수 안에 if (checkedWord === word) { if (list.find((w) => w === wordInput)) { alert("중복단어입니다"); return; } } 인풋 함수에서 배열.find 함수를 써서..

이번에 추가할 내용을 server.js랑 App.js를 나눠서 정리해보면 server.js Map → mdn const userSocketIdMap = new Map(); const wordMap = new Map(); 배열말고 map을 사용해서 데이터를 저장해줄겁니다 데이터베이스에다가 하면 더 편하고 쉬울텐데 너무 커질까바 서버에서만 데이터 저장합니다 socket io.on("connection", (socket) => { socket.on("join", (userId) => { if (userSocketIdMap.size === 0) { userSocketIdMap.set("user1", userId); io.emit("join", `hi user1 ${userId}`); } else { userSo..

계획 코로나 시국에 친구를 자주 만나지 못해서 엄청 간단한 초성게임을 하고 싶다는 생각을 해서 계획하게 되었습니다 javascript만으로도 되지만 react를 배우는 겸 react로 진행하겠습니다 전체적인 구성 CHOSUNG-GAME ├─ .gitignore ├─ node_modules/ ├─ public/ ├─ server/ -서버 └─ index.js ├─ src/ ├─ components/ └─ . . . ├─ utilities/ -초성 검사, 랜덤초성만들기 .. ├─ styles/ └─index.tsx ├─ package.json └─ tsconfig.json 1. 서버에서 react build를 해서 나온 정적인 index.html 파일을 socket.io를 쓸수있게 해서 서버를 구동합니다 들..