공부 기록용 블로그

접근 속도는 빠르지만 기억 공간이 많이 요구됨. 다른 방식에 비해 검색속도 빠름. 삽입 삭제 작업 빈도가 많을 때 유리. 대부분 탐색방법들은 탐색키를 저장된 키 값과 반복적으로 비교하여 탐색하고자하는 항목에 접근하지만, 해싱은 키 값에 산술적 연산을 적용해 해당 항목이 저장되어있는 테이블의 주소를 계산하여 접근한다. : 자료를 꺼내기 위해 전체 배열을 탐색하지 않음. *키 값의 연산에 의해 직접 접근이 가능한 구조 : 해시테이블 *해시테이블을 이용한 탐색 : 해싱 키들의 비교에 의한 탐색은 정렬이 안되어있으면 O(n), 정렬되어있으면 O(logn₂ N). 보통 사전과 같은 자료구조를 구현할 때 최상의 선택이 됨. 사전 구조(dictionary)는 맵이나 테이블로 불리기도 한다. 탐색 키/키와 관련된 값으..

우선순위 큐는 배열이나 연결리스트, 힙으로 구현이 가능하다. 그 중 가장 효율적인 구조가 Heap, 이유는 시간복잡도가 O(log n) 데이터가 우선순위를 가지는 것이 특징이다. 우선순위가 높은 것 부터 먼저 나가고 최대힙/최소힙이 있음. 우선순위큐를 위한 것이 Heap Heap은 완전 이진트리이다. 그니까 완전이진트리가 아니면 힙ㄴㄴ 최댓값과 최솟값을 빠르게 찾는 것이 목적이기 때문에 전체 정렬이 필요 없다. 반정렬상태(느슨한 정렬 상태)를 유지하는데, 부모가 자식키보다 항상 큰 이진트리인 정도만 정렬한다. 가장 중요한 것은 중복값을 허용한다는 것! BST에서는 허용하지 않았다. priority queue 사례 : 시뮬레이션 시스템, 네트워크 트래픽 제어, OS 작업 스케줄링, 수치해석적 계산, 이산이..

트리를 알아보자,, 우선 트리하면 대표적인게 컴퓨터의 File System. 이외에 HTML Tag구조, 도-시군구-읍면동 주소체계, DBMS, 라우터 통신 알고리즘, 검색엔진에 사용된다. 트리는 아래로만 흐르는 방향그래프(Directed Graph)이다. 만약 그런 제약이 없다면 그래프. Binary Tree 이진트리는 자식의 갯수가 무조건 두개로 고정되어있다. *모든 노드가 2개의 서브트리를 갖고 있음. *공집합도 이진트리임. 일반 트리와 이진 트리의 차이점 1) 이진트리의 모든 노드는 차수가 2 이하, 즉 자식 노드의 갯수가 2 이하. 일반 트리는 자식 노드의 갯수 제한 없음. 2) 일반 트리와 달리 이진트리는 노드를 하나도 갖지 않을 수도 있음. 3) 서브트리간 순서가 존재함. : 왼쪽 서브트리,..

Stack - 후입선출(LIFO) : 입출력은 맨 위에서만 일어남, 중간부분 데이터는 삭제 못함. 입출력이 이뤄지는 부분을 stack top, 바닥을 stack bottom, 스택에 저장되는 것을 elememt라고 함. element가 없을 때는 empty stack이라 함. push연산중에 stack이 가득차서 입력이 불가능하면 오류 발생. pop연산중에 stack data가 없어서 출력이 불가능하면 역시 오류 발생 stack.empty()연산으로 비었는지 확인 후 pop 자료가 역순으로 출력되어야 하거나, 괄호검사에 이용. 배열과 연결리스트로 구현 가능. Stack 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..

*inflearn 김영한님의 스프링 입문 - 코드로 배우는 스프링 부트, 웹 MVC, DB 접근 기술 웹 개발은 크게 3가지 방법 있다. 1. 정적 컨텐츠 서버에서 뭐 하는 거 없이 파일을 그대로 web browser에 보여주는 것. 2. MVC와 템플릿 엔진 가장 많이 하는 방식. jsp,php같은 것들이 소위 말하는 템플릿 엔진임. html을 그냥 주는 게 아니라 서버에서 프로그래밍해서 html을 동적으로 바꿔주는 걸 템플릿 엔진이라고 하고, 그걸 하기 위해 컨트롤러, 모델, 화면, 해서 Model View Controller = MVC임. 정적컨텐츠는 그냥 파일을 그대로 브라우저에 전달해준다면, 이건 서버에서 HTML을 뭔가 변형해서 바꿔서 전달 3. API 안드나 아이폰클라이언트랑 개발을 해야된다..

인프런 김영한님의 강의 wellcom page를 만들어보자. resources > static : 변하지 않는 정적 파일 에다가 index.html을 추가하자. 1 2 3 4 5 6 7 8 9 10 11 Hello Hello hello Colored by Color Scripter cs 그리고 서버를 다시 키면, 이런 페이지가 뜬다. spring boot는 spring생태계를 감싸서 편리하게 사용할 수 있도록 도와주는데, 어마어마하게 커서 필요한 걸 찾는 능력이 중요함. spring.io에 들어가서 Projects>Spring Boot>LEARN가면 버전에 따라 선택한 뒤 Reference Doc.를 뒤져보자 spring은 ..

start.spring.io/ spring에서 스프링 부트 기반 프로젝트를 만들어주는 사이트. Project Maven Project Gradle Projeck 라이브러리를 땡겨오고, 빌드하는 life cycle까지 다 관리해주는 툴. 과거엔 1을 많이 썼지만 요즘엔 2를 더 많이 씀. spring라이브러리 관리 자체도 2로 많이 넘어옴. Spring Boot 버전을 선택해야하는데, SNAPSHOT : 아직 만들고 있는 버전. M1 : 아직 정식 릴리즈된 버전이 아님. 정식 릴리즈된 버전중에 가장 최신꺼 선택하자 Project Metadata Group : 보통 기업명 Artfact : 빌드된 결과물(프로젝트명) ADD DEPENDENCIES★ 스프링 부트 기반으로 프로젝트를 시작할건데, 어떤 라이브러리..

입력받은 n의 수와, n보다 큰 수부터 차례로 2진수를 구했을 때 1의 갯수가 같은 것을 return시켜주면 되는 문제 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include #include using namespace std; int cnt (int num){ int result = 0; while(num){ if(num%2==1) result++; num/=2; } return result; } int solution(int n) { int answer = 0; int n_cnt = cnt(n); while(1){ int tmp = cnt(++n); if(n_cnt == tmp) return..

작은수 * 큰수를 하게끔 A는 오름차순, B는 내림차순으로 정렬하여 각각 답을 구해주면 되는 문제 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include #include #include using namespace std; int solution(vector A, vector B) { int answer = 0; sort(A.begin(), A.end()); sort(B.rbegin(), B.rend()); for(int i=0;i

문제 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 따라서 한자리, 두 자리 수 숫자는 모두 한수이다. =>아래 예제 출력에서도 알 수 있음. 입력 조건이 1000보다 작거나 같은 N이므로 1000은 어차피 fals..