zzugest1

트리란 정점(Node)와 간선(edge)를 이용하여 데이터의 배치 형태를 추상화한 자료구조를 말한다. 위 트리는 10개의 노드와 9개의 간선을 가진다. 트리에 대한 용어들을 정리하자면 루트(Root) 노드 : 트리의 맨 위에 있는 시작점 노드를 뜻한다. 위 트리에서 루트 노드는 A이다. 리프(Leaf) 노드 : 더 이상 아래로 간선을 가지지 않는 트리의 맨 아래에 있는 노드를 뜻한다. 위 트리에서 리프 노드는 G,H,I,E,J이다. 내부(Internal) 노드 : 루트, 리프 노드가 아닌 중간에 있는 노드를 뜻한다. 위 트리에서 내부 노드는 B,C,D,F이다. 부모,자식 노드 : 한 간선으로 연결된 두 노드를 기준으로 위에 있는 노드를 부모 노드, 아래에 있는 노드를 자식 노드라고 한다. 노드 D는 G,..

우선순위 큐란 기존의 선입선출의 특성을 따르지 않고, 원소들의 우선순위에 따라 큐에서 빠져나오는 방식을 가진 큐이다. 큐의 원소가 3,6,8,5로 무작위 순서로 구성되있을 우선순위를 숫자가 작은 원소가 먼저 빠져나온다 가정하면 3,5,6,8 식으로 빠져나올 것이다. 우선순위 큐를 구현할 때 두가지 경우가 가능한데 1. enqueue할 때 우선순위를 유지하도록 2. dequeue할 때 우선순위 높은 것을 선택하도록 이 두 방법 중 시간적 측면에서 유리한 방법은 첫번째이다. 그 이유는 두번 째 경우는 삭제할 원소를 찾으려면 모든 원소를 들여다봐야하기 때문에 큐의 길이에 비례하는 시간을 가진다. 하지만 첫번 째 경우는 삽입 시 모든 원소를 들여다볼 필요는 없기 때문에 조금 더 유리하다. 큐를 구현할 때 배열 ..

환형 큐란 정해진 개수의 저장 공간을 원형으로 돌려가며 사용하는 큐이다. 그림과 같은 환형큐가 있고, 시작점이 A 위치일 때 enqueue(A)를 하면 위와 같이 삽입이 된다. 그 후 위와 같은 방향으로 enqueue(B),enqueue(C)를 하면 B,C가 삽입이 된다. 큐의 삭제 연산 dequeue()를 실행하면 먼저 삽입된 A는 삭제될 것이다. 그 후 연산으로 위와 같은 그림이 되었을 때 데이터를 삽입하는 부분은 rear, 데이터를 꺼내는 부분은 front라는 포인터를 가진다. 환형 큐는 정해진 개수의 저장 공간을 이용하므로 큐가 가득 차있다면 삽입 연산을 실행할 수 없다. 이러한 특성이 반영된 환형 큐의 핵심 연산은 다음과 같다. size() : 큐에 들어 있는 원소 개수 추출 isEmpty() ..

큐란 자료를 보관할 수 있는 선형구조이며, 단 데이터를 넣을때에는 한 쪽 끝에서 밀어 넣어야하고 꺼낼 때에는 반대쪽에서 꺼내야 하는 제약이 있다. 이러한 특성을 선입선출(first-in first-out)이라 한다. 그림을 통해 설명하면 위와 같이 아래쪽 방향으로 A를 집어넣으면 앞으로 데이터는 같은 방향으로만 넣을 수 있다. 다음 B를 넣으면 위와 같이 A위에 위치하게 된다. 이러한 큐의 삽입 연산을 enqueue()라고 한다. 데이터를 삭제하면 먼저 삽입된 A가 먼저 삭제되고 기존 A의 위치에는 B가 자리잡게 된다. 즉 큐에서 데이터가 삭제되면 맨 앞 데이터가 삭제되고 나머지 데이터는 한 칸씩 앞으로 가게된다. 이러한 큐의 삭제 연산을 dequeue()라고 한다. 큐의 핵심연산은 5가지가 있다. si..

중위 표기법은 연산자가 두개의 피연산자 사이에 있는 표기법이고, 후위 표기법은 연산자가 두개의 피연산자 뒤에 있는 표기법이다. 후위 표기법으로 되어있는 식을 스택을 이용해 계산하는 방법은 다음과 같다. ex) AB+CD+* 1. 식을 왼쪽부터 한글자씩 읽어나가는 방식으로 우선 피연산자는 스택에 push한다. 2. 연산자 +를 만나면 스택에 있는 두 피연산자를 pop한 후 계산을 한다. 그 뒤 계산된 값을 다시 스택에 push한다. 3. CD+부분도 위와 마찬가지 방식이고 A+B위에 push될 것이다. 마지막 연산자 *를 만났는데 마찬가지 방식으로 C+D와 A+B를 pop한 후 계산한 뒤 스택에 푸쉬 한다. 4. 수식을 다 읽고 난 후 스택에 남아있는 값을 pop한 후 출력하면 원하는 계산값이 나온다. 위..

중위 표기법은 우리가 일상에 쓰는 수식 표기법으로 연산자의 두개의 피연산자 사이에 있는 표기법을 말한다. ex) A*B+C 후위 표기법은 연산자를 두개의 피연산자 뒤에 표기하는 기법이다. ex) A*B+C -> A B * C + 위 중위 표기법이 어떤 과정을 통해 후위 표기법으로 바뀌는 지 그림으로 표현하면 A*B+C 1. 후위 표기식을 담을 빈 리스트가 있고, 연산자를 넣을 스택이 있다고 가정하자. 중위 표기식의 왼쪽부터 차례대로 읽어나가는데 피연산자인 경우 후위 표기식 리스트에 넣는다. 그 다음 연산자 *는 빈 스택에 push한다. 2. B는 피연산자이기 때문에 후위 표기식 리스트에 넣고, +를 스택에 push하기전 연산자의 우선순위를 비교한다. *는 +보다 연산의 우선순위이기 때문에 우선 *를 스택..

https://school.programmers.co.kr/learn/courses/30/lessons/151139 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 CAR_RENTAL_COMPANY_RENTAL_HISTORY 테이블에서 대여 시작일을 기준으로 2022년 8월부터 2022년 10월까지 총 대여 횟수가 5회 이상인 자동차들에 대해서 해당 기간 동안의 월별 자동차 ID 별 총 대여 횟수(컬럼명: RECORDS) 리스트를 출력하는 SQL문을 작성해주세요. 결과는 월을 기준으로 오름차순 정렬하고, 월이 같다면 자동차 ID를 기준으로 내림차순 정..

https://school.programmers.co.kr/learn/courses/30/lessons/151138 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 CAR_RENTAL_COMPANY_RENTAL_HISTORY 테이블에서 대여 시작일이 2022년 9월에 속하는 대여 기록에 대해서 대여 기간이 30일 이상이면 '장기 대여' 그렇지 않으면 '단기 대여' 로 표시하는 컬럼(컬럼명: RENT_TYPE)을 추가하여 대여기록을 출력하는 SQL문을 작성해주세요. 결과는 대여 기록 ID를 기준으로 내림차순 정렬해주세요. 예시 예를 들어 CAR_RENT..

스택이란 자료를 보관할 수 있는 어떤 구조를 의미하는 데 데이터를 넣을 땐 한쪽 끝에서 밀어 넣어야 하고 꺼낼 때에도 넣은 방향에서 빼야하는 조건이 있다. 이러한 특성을 후입선출(Last-In First-Out)이라 한다. 그림으로 표현하자면 위와 같은 스택이 있고 A가 맨 처음 삽입된 원소라 가정하자. 그 다음 삽입연산 push(B)를 실행하면 원소 B가 A위에 삽입이 된다. 그 다음 제거(또는 반환) 연산 pop()을 실행하면 가장 최근에 삽입된, 맨 위에 있는 원소 B가 제거된다. pop()연산은 특정 원소를 지정하지 않는 것을 볼 수 있는데 스택의 특성상 무조건 맨 위 원소를 제거하기 때문이다. 스택의 추상적 자료구조를 배열로 표현한 코드는 다음과 같다. from doublylinkedlist i..

양방향 연결 리스트란 아래와 같이 앞뒤의 노드가 서로 연결되어있는 리스트를 말한다. 양방향 연결 리스트의 단점은 메모리 사용량이 커진다. 장점으로는 데이터를 앞뒤방향으로 읽을 수 있다는 점이 있다. 그래서 코드 작성이 단방향 연결 리스트보다 쉬워진다. 양방향 연결 리스트의 노드 클래스 class Node: def __init__(self, item): self.data = item self.prev = None self.next = None 양방향이기 때문에 prev,next를 None으로 지정해 노드의 방향을 양쪽으로 구현한다. 단방향 연결 리스트의 연산과 바슷하게 적용하기 위해 양방향에서도 더미 노드를 만들어야 한다. 이 때 head의 이전과 tail 다음에 두개의 더미 노드를 만들어 양방향을 구현해..