Brute force Study

2023년 2학기 유닉스 프로그래밍 과목에서 진행했던 프로젝트. 시스템 콜(System Call)을 이용하여 프로그램을 만드는 프로젝트였다.교수님께서 리눅스 서버에서 프로그램 시연을 할 것이기 때문에, CLI로 구현하라고 하셨다 시스템 콜은 read(), open(), write() 부터 fork(), execve() 등등 굉장히 많기 때문에 사실 저수준에서 어떤 것을 구현하는 것이 과목의 목표와 조금 더 맞긴 하지만, 우리 팀은 기존에 C의 high level로 구현되어 있던 코드들을 system call을 이용하여 구현하는 것으로 프로젝트의 방향을 잡았다. 최대한 수업시간에 배운 시스템 콜을 이용하여 만들만한 프로그램을 찾다가, 편의점 Pos System을 만들기로 하였다.프로젝트 진행 기간은 약 2..

2021년 1학기 디지털논리회로 과목에서 진행했던 프로젝트. 굉장히 허접(?)스럽다Logisim이라는 논리 회로 에뮬레이터로 원하는 기능을 구현하여 프로젝트를 완성하는 것이 목표였다. 이 과목이 개정되고 처음 수강했던지라 이전에 선배들이 했던 프로젝트가 없었기 때문에, 어떤 주제를 선정할까 고민하다가 숫자야구를 고르게 되었다. (해가 지날 수록 프로젝트 레거시들이 쌓이면서 기준점이 높아진 탓인가 이제는 로지심으로 캐치마인드를 구현할 수준이라고 한다...)  보통 숫자야구는 숫자 4개를 가지고 4 Strike를 달성하면 게임이 종료되지만, a~z 문자 3개를 가지고 3 Strike를 달성하도록 조건을 바꿔보았다.   https://github.com/DawnGlow/NumberBaseball_LogicCi..

2021년 1학기에 Object Oriented Programming(Java 강의)에서 진행했던 프로젝트. GUI로 만든 첫 프로그램이다. 이 프로젝트 제한 조건이, 반드시 JavaFx를 이용해서 프로젝트 결과물을 만들어 제출해야 했다. 사실 이 때 내 기억으로 JavaFx를 배우는데 너무 어려웠다. 컴포넌트, 컨테이너에 대한 개념부터, 외우기 힘든 Label, CheckBox와 같은 클래스들을 배우면서 어떻게 프로그램을 만들까 고민을 했었다. 고민하던도중 SceneBuilder라는 툴이 있다는 것을 알았고, SceneBuilder의 도움을 받아서 GUI 구현을 수월하게 할 수 있었다. 이 때 OOP 과목 말고 프로젝트를 진행하는 과목이 하나 더 있어서 복잡하지 않지만 JavaFx의 클래스를 적당히 사..

2020년 2학기 진행했던 프로젝트 EV3 로봇 키트라는게 있는데, 각 부품을 조립할 수 있고, 코딩을 할 수 있다. 코딩을 통해서 부품의 동작을 제어하고, 원하는 결과물을 내는 것이 이 프로젝트의 목표였다. 이 당시에 코로나 19가 유행했던지라, 공공장소에서 손 세정제를 분사해주는 디스펜서에 불편함을 느끼고, 비접촉형 자동 분사기를 만들어봐야 겠다는 아이디어를 가지고 자동 디스펜서를 만들어봤다. 이 때 작성했던 보고서 내용은 아래에 적어둘게요 프로젝트 목적/필요성최근 코로나 19로 인한 손세정제, 손소독제 사용량이 증가하였다.  공공장소에서 손세정제, 손소독제를 사용할 시 펌프부분을 많은 사람들이 세정되지 않은 손으로 만지게 된다. 세저오디지 않은 손이 펌프에 접촉되다 보면 펌프 부분이 청결하게 유지되..

지금으로부터 4년 전인 2020년에 진행했던 프로젝트 1학년 새내기때 C언어도 제대로 다루지 못했지만, 나름 성공적(?)으로 마무리했던 C언어 프로젝트 이다.지금 돌아보면 이 프로젝트가 지금까지 대학교 생활하는데 큰 도움이 되지 않았나 싶다. 첫 단추를 잘 끼운 느낌이다. 동아리 내 2명이 팀을 이뤄서 C언어를 이용해서 자유 주제로 프로그램 하나를 만드는 것이 목표였다. 구현했던 기능은도서 검색도서 대출도서 반납도서 삭제도서 추가정도 였다. 이때는 GUI를 이용할 생각도 못했다. 그냥 구조체, 포인터만 조금 다룰 줄 아는 수준에서 개발을 시작했었는데, 개발을 하면서 마스터 할 정도로 공부를 열심히 했다.      https://github.com/DawnGlow/BookRental_C GitHub - D..

블룸 필터(bloom filter)블룸 필터는 해시 테이블에 비해 공간 효율이 매우 높은 방법이지만, 결정적(deterministic) 솔루션 대신 부정확한 결과를 얻을 수 있다.거짓-부정(false-negative)dl 이 없다는 것은 보장하지만, 거짓-긍정(false-positive)는 나올 수 있다.즉, 특정 원소가 존재한다는 긍정적인 답변을 받을 경우, 이 원소는 실제로 있을 수도 있고 없을 수도 있다.그러나 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면 이 원소는 확실히 없다뻐꾸기 해싱과 마찬가지로 블룸 필터도 여러 개의 해시 함수를 사용한다정확도를 위해 세 개 이상을 사용해야 한다블룸 필터는 실제 값을 저장하지는 않으며, 대신 특정 값이 있는지 없는지를 나타내는 부울 타입 배열을 사용..

C++ 해시 테이블해시 구현에서 항상 양의 정수만 취급할 수는 없다.오히려 문자열 데이터를 다루게 되는 경우가 더 많다영어 사전을 구현하려면 영어 단어를 키로 사용하고, 뜻을 값으로 사용해야 한다모듈로 함수는 문자열에는 적용할 수 없다간단한 해결책은 문자열의 모든 문자에 대한 ASCII 코드 값을 모두 더한 후에 모듈로 연산을 하는 것이다.위 방법은 충돌이 빈번하게 발생할 수 있다C++은 문자열로부터 해시 값을 생성하는 용도로 std::hash>(std::string) 함수 객체를 제공한다이 함수 객체 내부에는 해시 함수 알고리즘이 구현되어 있다.C++은 문자열 이외에도 모든 기본 데이터 타입에 대한 해시 값을 생성하는 기능도 제공한다"체이닝을 사용하는 해시 테이블"에서 구현했던 해시 테이블 코드를 템플..

해시 테이블에서 충돌다수의 키를 저장할 수 없는 문제를 해결해보자체이닝앞에서는 하나의 해시 값에 대해 하나의 원소만을 저장했다.따라서 특정 해시 값 위치에 이미 원소가 존재한다면 새로운 값과 예전 값 중 하나를 버릴 수밖에 없었다.체이닝(chaining)은 두 값을 모두 저장할 수 있는 여러 방법 중 하나이다이 방법은 해시 테이블의 특정 위치에서 하나의 키를 저장하는 것이 아니라, 하나의 연결 리스트를 저장한다새로 삽입된 키에 의해 충돌이 발생하면, 리스트의 맨 뒤에 새로운 키를 추가한다따라서 다수의 원소를 원하는 만큼 저장할 수 있다벡터 대신 연결 리스트를 사용하는 이유는, 특정 위치의 원소를 빠르게 삭제하기 위함이다Example) 체이닝을 사용하는 해시 테이블#include #include #incl..

해시 테이블lookup(룩업, 조회)는 특정 원소가 컨테이너에 있는지 확인하거나 또는 컨테이너에서 특정 키(key)에 해당하는 값(value)를 찾는 작업을 의미한다DB에서 원하는 자료를 찾거나, 사전에서 단어의 뜻을 찾는 문제들이 이에 해당모든 원소를 선형으로 검토하여 원하는 값을 찾는 작업은 일반적으로 매우 많은 시간이 소요된다O(N) 시간 복잡도를 가짐이 작업을 훨씬 빠르게 수행할 수 있는 효과적인 알고리즘이 필요하다.해시 테이블과 블룸 필터라는 효과적인 구조에 대해 살펴본다.해시 테이블O(N)을 갖는 선형 검색보다 더 나은 검색 방법은 BST와 같은 속성을 갖도록 높이 균형 트리에 데이터를 저장하는 것이다.시간 복잡도가 O(log N)이므로 선형 검색보다 훨씬 빨라진다검색 횟수가 증가하면 이 정도..

그래프(graph)트리는 원형 또는 순환적인 종속성을 표현할 수 없다.하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에도로망을 생각해보자. 특정 노드에서 다른 노드로 이동하기 위한 다양한 경로가 존재할 수 있다.이러한 경우에는 그래프(graph) 구조를 사용해야 한다그래프 구분 - weight그래프는 노드 데이터뿐만 아니라 노드 사이의 에지 데이터도 저장해야 한다.도로망을 예로 들면 각각의 노드에 다른 어떤 노드들이 연결되어 있는지에 대한 정보를 가지고 있어야 한다.이런 방법으로 필요한 모든 노드와 에지가 있는 그래프를 만들 수 있다.이러한 그래프를 비가중 그래프(unweighted graph)라고 한다.에지에 가중치 또는 더 많은 정보를 부여할 수 있다.도로망에서 에지에 노드와 노드 ..