성댕쓰 똑똑한 생활

문제는 다음과 같다. NxM 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이 있는 부분은 1이다. 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결된 것으로 간주한다. 얼음 틀 모양이 주어질 때 생성되는 총 아이스크림 개수를 구하는 프로그램을 작성하라. 먼저 내가 짠 풀이는 BFS를 사용하여 구현하였다. from collections import deque from typing import List class IceBeverage: def __init__(self, graph : List[List[int]]) -> None: self.m_graph = graph self.m_col = len(graph[0]) self.m_row = len(graph) self.m_r..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 9. 16:44

DFS 깊이 우선 탐색 스택 자료구조 또는 재귀 함수 사용 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. # DFS 기초 # 각 노드가 연결된 정보를 표현 (2차원 리스트) # 1번 노드부터 있다고 가정 graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] # 각 노드가 방문한 정보를 표현 (1차원 리스트) visited = [False] * 9 def DFS(graph, v, vi..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 6. 22:34

1. 알아야할 자료구조 - Stack : FILO python에서 list를 이용 stack = [] stack.append(5) stack.append(7) stack.append(2) stack.pop() stack.append(1) stack.append(4) stack.append(3) stack.pop() # 최상단 원소부터 출력 print(stack[::-1]) # 최하단 원소부터 출력 print(stack) ******** [4, 1, 7, 5] [5, 7, 1, 4] - Queue : FIFO python에서 list로 구현가능하나 시간 복잡도가 증가하므로 deque자료구조를 이용한다. from collections import deque queue = deque() queue.append..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 6. 21:42

문제: 주어진 String s에서 반복되지 않는 첫번째 character의 index를 return하여라 def FindFirstUniqueCharacter(stringParam : str) -> int: hashMap = {} for c in stringParam: if c in hashMap: hashMap[c] += 1 else: hashMap[c] = 1 for idx, c in enumerate(stringParam): if hashMap[c] == 1: return idx return -1 print(FindFirstUniqueCharacter("nocodeprogram")) print(FindFirstUniqueCharacter("nownocodeprogram")) **************..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 4. 22:52

파이썬 수 자료형 정수형, 실수형이 있다. 실수형 데이터는 정확도가 떨어지므로 round함수를 이용한다. a = 0.6 b = 0.3 print(a+b) if a + b == 0.9: print(True) else: print(False) if round(a + b, 4) == 0.9: print(True) else: print(False) **************** 0.8999999999999999 False True 다른 언어와 다르게 / 연산자는 실수형을 반환한다. 몫을 얻고 싶으면 // 를 사용한다. a = 7 b = 3 print(a/b) print(a//b) print(a%b) **************** 2.3333333333333335 2 1 리스트 자료형 데이터를 연속적으로 담는 자..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 4. 22:08

HashTable 자료구조는 insert, delete, find에 O(1) 시간 복잡도를 갖는다. Sort는 안된다. Hash function은 어떠한 input 값을 정수 output으로 바꾸는 함수이다. 다른 input에 같은 output을 return 할 수 있으며 이런 상황을 hash 충돌이라고 한다. 예를 들어 Hash function -> 은 "Apple" -> 23438881, "Banana" ->759342, "aadf" -> 759342 처럼 input을 정수로 return하며 "Banana"와 "aadf"는 hash 충돌 상태이다. Hash 충돌이 발생해도 HashTable 만드는데는 문제 없는데, 값을 array 공간에 각 index마다 linked list로 구성하면 되기 때문이다..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 3. 23:25

특정한 데이터를 레이블링하여 저장하는 컨테이너를 hash table이라고 한다. 문자 A와 문자 B를 서로 다르게 레이블링하여 저장하는 컨테이너가 그 예이다. A의 Ascill 코드는 65이고 B는 66이다. 이들 문자를 10으로 나눈 나머지값에 해당하는 인덱스에 문자를 저장하면 나중에 A를 찾을 때 나머지 연산으로 저장되어있는 위치를 빠르게 알 수 있다. class HashTable: def __init__(self) -> None: self.capacity = 10; self.basket = [""] * self.capacity def Add(self, alpha : str) -> None: self.basket[ord(alpha) % self.capacity] = alpha def Find(self..

똑똑한 개발/Algorithm 과 Data Structure 2022. 1. 3. 22:11

기존 send는 호출할 때마다 buffer를 복사하기 때문에 복사비용이 많이 발생한다. server에서 하나의 client에만 send하는 경우보다 여러 client에 broadcast하는 경우가 훨씬 많으므로 더 적은 비용의 sendbuffer를 구현해보자. SendBuffer.h #pragma once /*----------- SendBuffer -----------*/ class SendBuffer : enable_shared_from_this { public: SendBuffer(int32 bufferSize); ~SendBuffer(); BYTE* Buffer() { return _buffer.data(); } int32 WriteSize() { return _writeSize; } int32 ..

똑똑한 개발/C++ 게임개발 2021. 12. 21. 22:48

이전에 정리한 것처럼 TCP는 경계선 개념이 없기 때문에 데이터가 쪼개져서 들어올 가능성이 있다. 이러한 상황을 대비한 receive buffer를 만들어보자. 1차원 배열 공간의 read위치, write위치를 기억하고 이를 이용한 버퍼를 만든다. packet을 받으면 write 위치를 받은 데이터 크기만큼 이동한다. packet을 읽으면 read위치를 이동한다. 만약 write, read 위치가 동일하면 더 이상 읽을 데이터가 없다는 의미이므로 read, write 위치를 모두 첫 번째 위치로 옮긴다. 다른 경우, 만약 더 이상 write할 공간이 부족하면 read와 write사이의 데이터를 복사하여 처음 위치로 옮기고 write, read 위치를 각각 업데이트 한다. RecvBuffer.h #prag..

똑똑한 개발/C++ 게임개발 2021. 12. 20. 21:17

Connect와 Disconnect 로직을 Session에 구현해보자. 먼저 Discoonect 이벤트를 정의한다. IocpEvent.h enum class EventType : uint8 { Connect, Disconnect, Accept, //PreRecv, Recv, Send }; ... /*----------------- DisconnectEvent -----------------*/ class DisconnectEvent : public IocpEvent { public: DisconnectEvent() : IocpEvent(EventType::Disconnect) {} }; ... Connect, Disconnect를 정의한다. Session.h ... class Session : publi..

똑똑한 개발/C++ 게임개발 2021. 12. 13. 22:40