본문 바로가기

전체

 (94)
Algorithm/개념정리 검색 알고리즘(Search Algorithm)의 해시법(체인법과 오픈 주소법) 개념 정리 들어가며 해시법에 대해 다루기 전에 한 가지 경우를 살펴보도록 하자. 만약, 아래와 같은 배열에서 a[2]에 새로운 원소 6를 추가하는 경우, 일반적인 배열에서의 처리 과정은 다음과 같을 것이다. a = [1, 7, 10, 13, 16, 22] a[0](=1)와 a[1](=7)사이에 새로운 값이 추가될 수 있도록 이진 검색으로 검색 a[0](=1) 이후의 모든 원소를 한 칸씩 뒤로 이동 a[1](=None)에 새로운 원소 6을 대입 이와 같이 데이터 추가 또는 삭제 시 배열의 원소가 이동하는데 필요한 복잡도는 O(n)이고, 이는 배열의 크기가 커짐에 따라 그 비용 또한 커질 수 밖에 없다는 것을 의미한다. 해시법 해시법은 간단한 연산을 통해 데이터 저장 위치 = 인덱스를 구하는 방법으로, 데이터 검색 뿐..
Algorithm/개념정리 검색 알고리즘(Search Algorithm)의 선형 검색과 이진 검색 개념 정리 들어가며 어떠한 데이터 집합에서 원하는 값의 원소를 찾아내는 것을 검색이라고 하고, 이를 알고리즘으로 구현한 것이 바로 검색 알고리즘이다. 예를 들어, 우리가 주소록에서 누군가를 검색한다고 가정했을 때 다음과 같은 다양한 조건으로 검색할 수 있다. 성별이 남자인 사람 나이가 20세 이상인 사람 이름에 '영'자가 포함된 사람 위 검색 조건은 성별, 나이, 이름과 같이 특정 항목에 주목하고 있는데, 검색 알고리즘에서는 이를 키(key)라고 하며, 이는 대부분 데이터의 일부이다. 성별 : key와 일치하도록 지정 나이 : key가 포함되도록 범위 지정 이름 : key에 가깝도록 지정 가장 대표적인 검색 알고리즘으로는 배열 검색, 연결 리스트 검색, 이진 트리 검색이 있으나, 본 글에서는 배열 검색에 대해서만 ..
Algorithm/개념정리 [자료구조] 이진트리(Binary Tree) 생성 개념 정리 들어가며 사이버 대학교 특성 상 직장을 다니면서 자유롭게 학습할 수 있는 환경을 제공해준다. 그러나, 직장에서 야근, 주말 출근이 잦은 경우에는 출석체크 정도만 할 수 있고, 제대로 된 공부를 할 수 없다는 큰 단점이 있다. 필자 또한 약 2년 6개월 간의 직장생활을 하는 동안 잦은 야근, 거의 매주 출근으로 인해 시험을 보기 위한 벼락치기 외에는 제대로 된 학습을 수행하지 못했다. 현재는 퇴사하고 시간이 남아돌아서 토이 프로젝트를 하며, 공부하던 중 이진트리에 대해 제대로 학습하자는 취지로 본 글을 작성하였다. 1. 이진트리 이진트리에 대한 정의는 구글에 검색하면 긴 글과 다양한 전문 용어로 잘 나와있기 대문에 따로 언급하지 않겠으나, 쉽게 말하자면 아래 그림과 같이 크게 두 갈래로 나뉜 트리라고 할 ..
Development/Python 주피터 노트북(Jupyter Notebook) 설치 및 사용 방법 들어가며 주피터 노트북(Jupyer Notebook)은 IPython과 같이 상호작용 형식의 라이브 코드를 제공하는 웹 베이스 애플리케이션이다. 주피터 노트북을 사용하면 웹 브라우저 안에서 실행하고자 하는 코드를 입력하고, 그 결과를 바로 확인할 수 있다. 또한, 웹 브라우저에서 일반 프로그램으로는 구현하기 어려운 수학 공식을 표현할 수 있고, 다양한 그래프를 통해 데이터를 시각적으로 확인할 수도 있다. 뿐만 아니라, 나레이션 텍스트나 이미지 등을 추가하여 별도의 문서를 만든 후 공유할 수 있기 때문에 파워포인트, 키노트(Key Note)와 같은 프레젠테이션 프로그램으로도 많이 사용된다. 설치 방법 주피터 노트북은 오픈 소스 프로그램이므로, 무료로 다운로드하여 사용할 수 있다. 단, 주피터 노트북을 설치..
Development/Python IPython 설치 및 실행 방법 들어가며 파이썬을 공부하거나, 간단한 코드를 테스트할 때 Python Shell(파이썬 쉘)을 주로 사용한다. 파이썬 쉘은 파이썬 인터프리터를 더욱 편리하게 사용할 수 있도록 해주는 애플리케이션이다. 윈도우(Windows) 운영체제의 커맨드(CMD, 명령프롬프트)나 맥(Mac) 운영체제, 리눅스(Linux) 운영체제의 터미널(Terminal)과 비슷한 개념이다(자바스크립트로 개발을 해본 경험이 있는 경우 크롬 브라우저의 콘솔창이라고 생각하면 된다). 설치 및 실행 방법 아나콘다 파이썬을 설치하고 사용중인 경우 파이썬 환경에 이미 IPython 패키지가 설치되어 있을 것이다. 만약에 공식 사이트를 통해 파이썬을 설치한 경우에는 명령 프롬프트에 pip package manager를 입력하여 설치할 수 있다...
Algorithm/Baekjoon 2869번(달팽이는 올라가고 싶다) 파이썬(Python) 풀이 공유 들어가며 문제의 내용을 보기 전에 꽤 낮은 정답률(28.049%)을 보고 흥미가 더 생겼던 문제이다. 그런데, 생각보다 매우 간단한 문제라서 허무하게 끝난 것 같다. 아래 그림은 어려울 것 같은 문제는 비교적 쉽게 풀리고, 쉬울 것만 같은 문제는 생각하지 못한 곳에서 오류가 발생하는 상황을 너무나도 잘 나타내주어 정말 공감된다. 문제 2869번 달팽이는 올라가고 싶다 시간 제한 메모리 제한 0.15 초(추가 시간 없음) 128 MB 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구..
Algorithm/Baekjoon 2292번(벌집) 파이썬(Python) 풀이 공유 들어가며 나를 알 수 없는 늪으로 빠지게 한 문제이다. 문과 출신이라 그런지 수학이랑 그다지 친하지는 않은데도 불구하고 가우스 공식을 코딩에 접한 이후로 공식 만드는 재미에 빠져서 공식을 세우기 위해 약 한 시간 가량을 삽질했지만, 결국에는 whlie 문으로 해결하였다. 1. 문제 2292번 벌집 시간 제한 메모리 제한 2 초 128 MB 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3..
Development/Web React 개발 환경 구축 및 GitHub Pages 배포 방법 들어가며 리액트(React)는 페이스북에서 효율적인 UI를 만들기 위해 개발한 Javascript 기반의 라이브러리이다. 웹 페이지는 많고 복잡한 HTML 태그로 구성되어 있는데, React는 이와 같이 복잡한 HTML 구조를 별도의 컴포넌트(Component)로 구분하여 코드 가독성, 재사용성, 유지보수성을 높여줌으로써 효율적인 웹 개발 환경을 제공해준다. 프로젝트 생성 리액트는 create-react-app이라는 라이브러리를 통해서 새로운 앱을 생성할 수 있다. 공식문서에 따르면, npm이 아닌 npx 이용을 권장하고 있는데, npm은 로컬에 라이브러리를 설치하는 반면, npx는 라이브러리를 임시로 설치하여 단 한 번만 실행시키고 바로 삭제하는 일회성 모듈이므로 npx를 이용하면 저장공간 낭비를 줄일..
Algorithm/Baekjoon 1712번(손익분기점) 파이썬(Python) 풀이 공유 들어가며 처음 문제에 접근했을 때에는 while 문으로 수량을 파악하려고 하였으나, 세 번째 테스트케이스를 보고난 이후에는 생각이 완전히 바뀌었다. 세 번째 테스트케이스를 적용하는 경우 약 20억 번의 반복을 수행해야 하는데, 이럴 경우에는 문제에서 요구하는 시간 제한(0.35초)를 초과하기 때문이다. 따라서, 문제에서 요구하는 손익분기점의 의미를 먼저 파악한 다음에 규칙을 찾고, 코드를 작성하였다. 1. 문제 1712번 손익분기점 시간 제한 메모리 제한 0.35초 128 MB 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다..
Algorithm/Baekjoon 1316번(그룹 단어 체커) 파이썬(Python) 풀이 공유 들어가며 문제를 이해하자마자 문자열을 구성하는 모든 문자의 인덱스를 알아내면 문제를 풀 수 있을 것 같았다. 하지만, 3차원 리스트, 여러 반복문 사용으로 구현하기에는 꽤나 복잡할 것으로 예상되는 문제였는데, 생각보다 쉽게 통과하였다. 1. 문제 1316번 그룹 단어 체커 시간 제한 메모리 제한 2초 128 MB 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. 1.1..

티스토리툴바