muntari Log muntari Log

그래프 그래프는 연결 관계에 있는 데이터를 저장하는 자료구조이다. 그래프는 노드라는 가장 작은 단위의 데이터로 이루어져 있는데, 각 노드들의 관계가 동등한 위치에 있을 경우 그래프를 적용하여도 무방할 것 같다. 자료구조를 공부해야 하는 이유는 상황에 맞는 방식으로 데이터를 저장하고 사용하기 위해서이다. 데이터 사이에 어떤 관계가 있는지 파악하고 그에 맞는 적절한 자료구조를 사용하기 위함이다. 앞, 뒤와 같은 순서 데이터를 저장하기 위해서는 배열, 링크드 리스트 같은 선형 자료구조를 상, 하 관계와 같은 계층 데이터를 저장하기 위해서는 트리와 같은 계층 자료구조를 사용하면 된다. 그렇다면 그래프는 언제 사용하는 걸까? 그래프는 연결 관계에 있는 데이터를 저장한다고 하였는데 이는 실제로 우리 생활에서 무궁무..

데이터베이스 객체의 대표적인 테이블 작성, 삭제, 변경 등에 대해 알아보자. 이전까지는 SQL 명령 중 DML(조작하는 명령)을 알아보았다. DML 명령을 내리기 위해선 당연히 테이블이 생성이 되어있어야 하며, 다룰 수 있는 어떠한 데이터가 존재해야한다. 이젠 SQL 명령 중 DDL(정의하는 명령)을 통해 스키마 내의 객체를 관리하는 방법을 알아보자. 테이블 작성 DDL은 모두 같은 문법을 사용한다. CREATE 로 작성, DROP으로 삭제, ALTER로 변경! CREATE TABLE 테이블명( 열 정의1, 열 정의2, ... ) 열 정의 열명 자료형 [DEFAULT 기본값] [NULL|NOT NULL] 정의하는 열의 자료형 (정수, 실수, 문자열...) NULL 허용 여부등 정의하고자 하는 테이블의 명..

데이터베이스 객체 테이블, 뷰, 인덱스 등 데이터베이스 내에 정의하는 모든 것을 일컫는 말이다. 프로그래밍에서의 객체와 혼동하는 경우가 있는데, 보통 데이터베이스 관점으로 바라볼때의 객체는 데이터베이스 객체를 가르킨다. 앞서 알아보았던 SQL 명령은 데이터베이스 객체를 조작하는 SQL 명령일뿐, 데이터베이스 객체라는 개념에 포함되지 않는다. 객체의 이름은 굉장히 중요한 의미를 가진다. 어떤 데이터가 저장되어 있는지 파악하는 기준이 되므로 의미, 관련성이 없는 이름은 붙히지 않는다. 데이터베이스 객체는 이름을 가지며 이름은 아래의 명명규칙을 따른다. 1. 기존 이름이나 예약어와 중복하지 않는다. (foo라는 이름의 테이블을 만들었다면 뷰 또는 모든 객체 역시 같은 이름을 사용할 수 없다.) 2. 숫자로 시..

이진 탐색 트리와 해시 테이블 해시 테이블로 구현하는 딕셔너리와 세트 자료형을 이진 탐색 트리로 구현할 수 있다. 노드 인스턴스를 딕셔너리와 세트의 인스턴스로 지정하여 구현할 수 있다고 한다. 먼저 왜 이진 탐색 트리로 딕셔너리와 세트 자료형을 구현해서 사용하는 이유를 알아보자. 딕셔너리와 세트 자료형은 파이썬 내부적으로 해시 테이블로 구현되어 있다.(해시 테이블 포스팅 참고) 굳이 이진 탐색 트리로 구현하는 이유는 뭘까? 해시 테이블의 경우 데이터의 순서 관계를 저장하지 않는 자료구조이다. 반면에, 이진 탐색 트리의 경우 데이터 사이에 순서를 저장하는 역할 하는 자료구조이며 in-order 방식으로 노드를 순회하면 트리 안에 있는 데이터를 순차적으로 출력할 수 있다. 결국, 세트의 데이터나 딕셔너리의 ..

문제 설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. 제한 사항 scovil..

이진 탐색 트리 트리의 일종으로 이진 트리이면서 이진 탐색 트리의 속성을 만족하는 트리를 이진 탐색 트리라고 부른다. 영어로는 Binary Search Tree 라고 부른다. 이진 탐색 트리를 사용하면 저장한 데이터를 쉽게 찾아 올 수 있다. 이진 트리는 각 노드가 최대 2개의 자식 노드만 가질 수 있는 트리를 말한다. 이진 트리에서는 모든 노드가 2개, 1개, 0개의 자식 노드만 가지고 있다. 여기서 이진 탐색 트리의 속성은 아래와 같다. 1. 특정 노드를 기준으로, 특정 노드의 왼쪽 부분 트리에 있는 모든 노드는 특정 노드의 데이터보다 작아야 한다. 2. 특정 노드를 기준으로, 특정 노드의 오른쪽 부분 트리에 있는 모든 노드는 특정 노드의 데이터보다 커야 한다. 루트 노드가 아닌 모든 루트에 적용되는..

힙을 활용하는 대표적인 2가지 방법 1. 정렬 2. 우선순위 큐를 구현하는 법 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 많이 사용된다! 정렬 알고리즘 데이터를 재배치하는 구체적인 방법을 정렬 알고리즘이라 한다. 삽입 정렬, 선택 정렬, 퀵 정렬, 합병 정렬 + 힙 정렬 등이 있다. 보통 정렬 알고리즘의 경우 O(n logn) 정도만 되도 효율이 좋은 측에 속한다 하니 아래의 시간 복잡도를 서로 비교해보자. 힙 정렬 Tree = [None, 14, 8, 12, 5, 4, 10, 6, 2, 1, 3] 위 예시로 힙 정렬 알고리즘의 방법은 아래와 같이 정리 할 수 있다. 1. 힙을 만든다. (이때 최댓값을 구하고 싶으면 max heap을 반대의 경우 min ..

문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. 제한 사항 phone_book의 길이는 1 이상 1,000,000 이하입니다. 각 전화번호의 길이는 1 이상 20 이하입니다. 같은 전화번호가 중복해서 들어있지 않습니다. 문제 접근 방법 ..