본문 바로가기

Programming

[Algorithm] 비트마스킹(Bit Masking) 비트마스킹(Bit Masking) 이란? 1. 비트란 ? - 데이터를 나타내는 최소 단위 - 모든 데이터는 0과 1의 조합으로 구성되고, 0 또는 1이 하나의 비트가 됨 - 1개의 비트는 2가지 상태를 나타낼 수 있다 -> n 개의 비트로는 2 ^ n 가지의 상태를 나타낼 수 있다. 2. 비트마스킹이란 ? - 컴퓨터가 내부적으로 모든 자료를 이진수로 표현하는 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법 - 비트 마스크를 이용하면, 더 빠른 수행 시간 + 더 간결한 코드 + 더 적은 메모리 사용 효과를 얻을 수 있다. - 집합의 배열을 인덱스로 표현할 수 있다. 비트 연산자(논리 연산자) 연산자 표기 역할 예시 AND a & b a 와 b 두 비트 모두 1이면 1, 아니면 0 a = 4 = 1.. 더보기
[Algorithm] 프로그래머스 전화번호 목록(해시) 문제 해당 문제를 풀 때 단순히 각 리스트 원소가 다른 리스트 원소의 앞 부분에 위치하는지, 그 원소로 시작하는 지를 따지려면 반복문을 2번 써야 하는 것. 풀이 문제 해결 아이디어는, "어떤 번호가 다른 번호의 접두어라면, 이 둘을 정렬했을 때 앞 뒤에 위치"하게 된다는 것이다. 즉, ["1235", "123", "12345", "012"] 라는 리스트를 정렬하게 되면 문자열 리스트는 대문자에서 소문자 순서로, 알파벳 순서로 정렬되므로, ["1012", "123", "12348", "1235"] 가 된다. 1. 따라서, i 번째 원소를 i+1번째 원소와 비교하며, 2-1. i + 1번째 원소의 [앞에서부터 ~ i번째 원소의 길이 만큼]이 i번째 원소와 같은지를 확인한다. 2-2. 여기서, i번째 원소가.. 더보기
[Algorithm] 프로그래머스 완주하지 못한 선수(해시) 문제 해당 문제는 해시 알고리즘으로 분류된 문제이며, 겉으로 봤을 땐 단순히 participant 내에 있는 원소 중 completion 에 존재하지 않는 원소가 있다면, 즉 참가자 이름에는 있지만 완주자 리스트에는 없는 이름을 리턴하면 되는 문제이다. 처음 풀이 단순히 문제를 보자마자 리스트 원소 존재 유무에 따라서 다음과 같이 코드를 작성하고 채점을 했더니, 효율성 부분에서 시간초과가 떴다. def solution(participant, completion): answer = '' for i in participant: if i in completion: completion.remove(i) else: answer = i return answer 다른 풀이 1 - 정렬 후 비교 - 리스트 내의 모든 .. 더보기
[Algorithm] 백트래킹(Backtracking) BOJ 1987번 알파벳 문제를 단순히 DFS로 풀다가, dx, dy로 나아가는 방향 선정에 따라 답이 달라지는 것을 느껴 관련 알고리즘인 백트래킹에 대해 정리하려고 한다! 백트래킹(Backtracking) 알고리즘의 정의 - ' 가능한 모든 방법을 탐색한다 ' 라는 아이디어를 가진 알고리즘 - 백트래킹(Backtracking)이란, 현재 상태에서 가능한 모든 후보군을 따라 들어가며, 해결책에 대한 후보를 구축해 나아가다, 가능성이 없다고 판단되는 즉시 후보를 포기하면서 정답을 찾아가는 알고리즘이다. - 즉, 해를 찾는 도중 해가 아니어서 막히게 되는 경우 -> '다시 되돌아가서' 해를 찾아가는 기법 - 최적화 문제와 결정 문제를 푸는 방법 DFS와 백트래킹 1. 깊이 우선 탐색(DFS) - DFS는 가.. 더보기
[Web/DL] Django 기반의 자연어 처리 서비스 구현 System Architecture - Django 와 Pytorch 를 이용한 자연어 처리 서비스를 구현한다고 할 때, 생각하는 시스템의 아키텍처는 아래와 같다. 현재 루트 디렉토리 파일 구조 - 우선, Django 프로젝트 생성 과정에 대한 설명 전 프로젝트 구성 후의 루트 디렉토리 파일구조는 아래와 같다. pyDjango 디렉토리 내에 pyDjango (루트 디렉토리) ├── sampleDjango (프로젝트 설정과 웹 실행에 필요한 파일이 있는 디렉토리) └── djangoApp (생성한 앱) └── djangoVenv (가상환경 폴더) Django 설치 1. Django 프로젝트 폴더 생성 - 클론 받은 프로젝트 폴더 내에서 테스트용 flask 웹 어플리케이션을 생성할 디렉토리(pyDjango).. 더보기
[Web Server] Django와 Web Server Django 를 통해 간단한 pytorch 자연어 처리 모델 배포를 위해 정리한 내용 우선, Django 는 Web Framework 라는 생각으로, 그럼 Django 를 사용할 때 웹 서버는 무엇인지에 대한 의문으로 검색을 시작했다. 우선, 결론적으로 말하자면 Django 는 웹 서버가 아니다!! Django 란 ? 1. Django 개념 - 파이썬으로 작성된 오픈 소스 웹 프레임워크이다. 즉, Web Server 가 아닌 ' Web Application Framework ' 이다. - Django는 모델-뷰-컨트롤러의 MVC 패턴을 따르고 있다. 2. Django 서버 실행 - Django 프로젝트 생성 후 서버를 실행할 때, 아래 명령어를 사용하는데 ./manage.py runserver (= py.. 더보기
[Data Structure] 힙(Heap) 연산 힙(Heap) 자료구조란 ? 1. 힙(Heap) 자료구조의 정의 - 힙 자료구조는 '완전 이진 트리' 를 기초로 하는 자료 구조 - 이때, 완전 이진 트리는 '마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진 트리' 이다. 2. 의의 - 힙은 수의 집합에서 가장 작은 수나, 가장 큰 수만을 꺼낼 때 유용한 자료 구조이다. 힙(Heap) 의 특징 1. 힙 = [최대 힙(Max Heap)] + [최소 힙(Min Heap)] 으로 나누어 진다. 1) 최대 힙 - 부모 노드의 값 > 자식 노드의 값 2) 최소 힙 - 부모 노드의 값 힙은 항상 느슨한 정렬 상태(반 정렬 상태)를 유지한다. 2. 힙은 '중복 값' 을 허용 - 힙은 최댓값 or 최솟값을 쉽게 뽑기 위한 자료구조로, 중.. 더보기
[Data Structure] 트리(Tree) 자료구조 트리(Tree) 자료구조란? 1. 트리(Tree) 의 개념 - 트리는, 노드로 이루어진 자료구조로 비선형 자료구조이다. cf) 선형 자료구조 : 스택, 큐 - 트리는 계층적 관계를 표현하는 자료구조이다. 2. 트리의 특징 1) 트리는 하나의 루트 노드를 갖는다. 2) 루트 노드는 0개 이상의 자식 노드를 갖는다. 3) 자식 노드 또한 0개 이상의 자식 노드를 갖는다. 4) 노드(Node)와, 노드들을 연결하는 간선(Edge) 들로 구성되어 있다. 3. 트리 자료구조 성립 조건 1) 트리에는 '사이클(Cycle)이 존재할 수 없다' - 이때, 사이클(Cycle) 이란, 시작 노드에서 출발해 -> 다른 노드를 거쳐 -> 다시 시작 노드로 돌아올 때 사이클이 존재한다고 한다. - 트리는 사이클이 없는 하나의 .. 더보기

티스토리툴바