컴퓨터 과학
수학으로 곡선을 그려보기 Part.1 [Hermite Curve]
2018. 6. 9.학교에서 들었던 컴퓨터 그래픽스 수업은 정말 지루했습니다... (지금까지 대학교생활에서 가장 재미없던 강의로 손에 꼽을 듯) 그래도 그중에서 재미있었던 파트를 꼽자면 과 를 고를 수 있을 것 같습니다. 좌표계 변환은 이다음에 알아보기로 하고 지금은 에 관련해서 정리해보려 합니다. 수학적인 곡선곡선은 수학적으로 어떻게 표현할 수 있을까요? 꺼무위키를 인용해 보면 다음과 같습니다. ...좀 더 엄밀하게 말하자면 연속적인 순서쌍의 집합이나 선으로 동형사상이 있는 위상 공간 정도일 것이다. 조금 더 이해하기 쉽게 우리에게 친숙한 xy-평면인 $R^{2}$ 공간으로 생각한다면, 평면 위의 곡선은 어떠한 연속함수 $\varphi:\left[0,1\right]\to R^2$가 있어서 $S=\left\{\left(x,..
해시 테이블 [Hash table] Part 2 : 빠르게 자료 넣고 찾자
2016. 8. 3.지난번 포스팅까지는 해시 테이블에 대한 소개와 동작 방식, 충돌 문제를 해결하는 방법으로 Close-Addressing 기법인 Chaining을 소개했다. 이번 포스팅에서는 Open-Addressing 기법에 속하는 3가지 방법을 소개하고, 지금까지 소개했던 해결법들을 간단하게 비교해 본 뒤 해시 테이블의 장단점을 정리해 보도록 하려 한다. Open-Addressing?! Open-Addressing 기법은 해시 함수로 얻어낸 주소를 그대로 이용하지 않고 상황에 따라 변경할 수 있는 기법이다. 물론 추적 가능하게 변형하는 기법을 사용한다. 이 기법을 사용하면 Close-Addressing에서는 보지 못했던 "클러스터링 문제"가 발생하게 되고 클러스터가 많이, 크게 일어나면 성능상 문제가 생기기 때문에 그..
해시 테이블 [Hash table] Part 1 : 빠르게 자료 넣고 찾자
2016. 8. 3.자료구조를 배우면서 가장 감명 깊게(?) 배웠던 자료구조가 바로 해시 테이블이라는 자료구조이다. 자료를 빠르고 효율적으로 저장하는 것이 자료구조를 연구하는 가장 큰 이유일 것이다. 자료구조의 효율은 자료구조를 이용하는 대표적인 행동인 "삽입", "검색", "삭제" 등의 시간 복잡도와 공간 복잡도를 계산하고 점근적 표기법을 이용하여 나타내면 된다. (주로 Big O 표기법을 사용한다) 자세한 사항은 여기를 통해 공부하기 바란다. 간단하게 말하면 Big O 안의 식의 미지수가 무한에 가까워질 때 즉, Big O 안에 있는 식의 극한값을 이용하여 효율을 나타내고 비교하게 된다. 보통 시간 복잡도를 이용하여 비교한다. 가장 짧은 시간이 걸리는 자료구조? 지난번에 배웠던 연결 리스트나 스택 같은 자료구조는 삽입하..
유전 알고리즘으로 테트리스 AI 최적화하기
2016. 8. 3.한창 신입생 때 Facebook에서 서비스하던 테트리스 게임이 유행했었다. 같은 동아리 안에서 그 테트리스를 엄청나게 잘하는 형이 있었는데 범접하기 힘든 수준…. 같은 학교 동기였던 나와 정수는 기계의 힘을 빌려서라도 그 형을 이기고 싶어서 유전 알고리즘을 이용하여 Facebook Tetris AI를 만들려 했다. 하지만 프로젝트가 끝날 즈음에 게임 등급 심의 위원회가 태클을 거는 바람에 Facebook이 테트리스 서비스를 종료하게 되면서 프로젝트가 중간에서 멈춰버리게 되었다. 게등위 때문에 프로젝트를 마감하지 못한 것에 부들부들하고 있을 때 그냥 지금까지 한 내용이라도 정리해서 동아리 문서도 만들고 내부 세미나에서 발표를 했는데, 날려버린 줄 알았던 그 자료를 발견하게 되어서 간단하게나마 포스팅을 해보..
스택 [Stack] : 자료를 차곡차곡 쌓아 올려라
2016. 7. 29.이번에 다룰 스택(Stack)이라는 자료구조와 다음 포스팅에서 다룰 큐(Queue)라는 자료구조는 간단하면서도 유용한 특징 덕분에 자주 활용하는 자료구조에 속한다. 스택과 큐만 잘 이해하고 활용할 수 만 있어도 다른 자료구조나 알고리즘을 배울 때 적극적으로 활용할 수 있을 것이다. 스택(Stack)이란?스택이라는 자료구조가 어떻게 이루어져 있는지는 책을 쌓아 올린 모습을 보면 편하게 이미지화할 수 있다. 차곡차곡 쌓아 올린 구조에 책이 무너지지 않게 하려면 위에서부터 차근차근 책을 제거해야 한다. (중간에 있는 책을 뽑으면 책이 무너지겠지) 스택이 이런 구조로 되어 있다. 밑에서부터 하나씩 차곡차곡 데이터를 쌓아 올리고 쌓아올린 데이터에 접근하려면 맨 위에 올려져 있는 데이터부터 꺼내 사용해야 한다. 이..
연결 리스트 [Linked List] : 자료들을 한 줄로 늘어놓는다
2016. 7. 29.앞서 말했었지만 처음 배운(과제로 나온) 자료구조들은 정말 기초적이고 간단한 형태의 자료구조들이었다. 한마디로 앞으로 구현해볼 자료구조들은 구현하기 매우 간단한 편에 속하니 부담없이 따라오다보면 구현할 수 있을 것이다. 연결 리스트(Linked List)란?우리가 해야 할 일을 쭉 적어 ToDo 리스트를 만들고, 장을 볼 때 사야 하는 물건을 쭉 적어서 쇼핑리스트를 만들어 사용하듯이 연결 리스트란, 데이터들을 쭉 나열하듯이 저장하는 자료구조를 말한다. 언뜻 보면 그럼 그냥 배열에 저장하는 것과 무엇이 다르냐고 물어볼 수 있다. 배열은 한번 선언하고 만들면 배열의 크기가 변하지 않는다. 프로그램을 만들면서 100개의 데이터가 들어올 것이라고 예상하여 100개의 배열을 만들었다고 하자. 하지만 200개의 데..
초심자를 위한 자료구조를 포스팅하면서
2016. 7. 29.자료구조를 배우게된 이유?학교에서 자료구조를 1학년 2학기에 수강했으니 1년 반쯤 되었다. 그때 당시 다른 학생들처럼 1학년은 대부분 교양필수과목을 수강했기 때문에 학교에서 배운 전공 지식은 NXT와 간단한 C++ 지식이 전부였다. (물론 따로 Web front 공부를 했지만) 아는게 별로 없던 1학년 때 소프트웨어 마에스트로 5기에 지원해서 떨어진 이유가 전공 지식과 경험이 부족했기 때문이라고 생각이 들었다. 내년에는 꼭 붙어보겠다는 생각으로 컴퓨터 공학과 다운 과목을 한번 배우고 싶어졌다. 1학년 때는 거의 학교에서 시간표를 정해주다시피 하지만 다행하게도 1학년 1학기를 빡세게 보내서 4학점을 넘겨 남들보다 3학점 정도 추가로 수강할 수 있었기 때문에 2학년 과목인 자료구조를 들을 수 있었다. 자료구..