🐇꾸준히, 한걸음씩☘️

그동안 배웠던 자료구조들을 이제 문제에 적용해 보자. 1) 해시 [programmers-Lv1] 완주하지 못한 선수 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 개요 마라톤 경기에 참여한 사람과 완주한 선수의 명단이 주어질 때, 완주하지 못한 선수의 이름을 반환해라.(완주하지 못한 선수는 1명이다) 풀이 선수의 이름을 key로 선수의 숫자를 value로 하는 dict를 만들어 저장(동명이인이 있을 수 있으므로) 완주 명단의 이름이 나오면 해당 dict[key]값을 1 감소 값이 0이 아닌 key 값을 반환(=완주하지 못한 선수이다) def solu..

1) 힙(Heap) 힙은 완전 이진트리 중 하나로 루트 노드가 전체 트리의 최솟값(=최솟값 힙)이나 최댓값(=최댓값 힙)을 갖는 자료구조이다. 어떤 노드에서도 왼쪽 서브트리, 오른쪽 서브트리도 모두 최소 혹은 최대 힙이여야 하므로 재귀적으로 정의 할 수 있다. 저번 시간에 배웠던 이진 탐색 트리와 비교해 보면 키의 크기순으로 정렬되어 있지 않고 이 때문에 빠른 탐색도 어려우며 완전이진트리이기 때문에 삽입, 삭제가 마지막 노드에서 이루어져야 한다. 자료구조의 해당 특성에서 비롯하여 정의되는 함수는 다음과 같다. insert(item) : item을 마지막 노드에 삽입한뒤, 루트 노드와의 크기비교를 통해 적절한 위치를 찾아나간다. remove() : 루트 노드를 삭제한 뒤, 알맞은 노드를 해당 자리로 이동시..

더보기 TIL을 쓰는데 너무 오랜 시간이 걸리기 때문에, 매일 기록하기 위해선, 조금 단순화하기로 하였다. 스택과 큐의 개념에 대해서는 기존의 글을 참고하자. [파이썬 기본 데이터 구조] 1. 스택과 큐 * 이 글은 네이버 부스트 코스의 인공지능(AI) 기초 다지기 강의를 수강하며 정리한 글입니다. 사담) 얼마전 인턴 모의면접에 우연히 참여할 기회가 생겼는데 스택과 큐를 헷갈려버렸다. 프로젝 steady-eschoi.tistory.com 1) 스택 후위표기법 후위표기법은 대표적으로 스택을 활용하여 푸는 문제이다. 중위 표기법(infix notation) : 연산자가 피연산자들 사이에 위치 (A+B)*(C-D) 후위 표기법(postfix notation) : 연산자가 피연산자들 뒤에 위치 AB+CD-* :..

0) 추상적 자료구조(ADT) 자료구조의 내부구현은 제공하지 않고, 데이터의 형태를 선언하고 기능(연산)을 정의하는 것 1) 연결리스트란? 노드와 노드가 연결된 형태이다. 노드는 값을 담는 부분과 주소를 담는 부분으로 구성되어 있다. 일반 리스트에 비해 값을 접근하는 데는 오래 걸리지만(시간복잡도 : O(1) vs O(n)), 데이터를 자유롭게 삽입 삭제 할 수 있다는 장점이 있다. 오늘 살펴볼 연결리스트는 기본 연결리스트, head가 더미노드를 가리키는 연결리스트, 양방향 연결리스트이다. 🥄기본 연결리스트 연결리스트는 노드가 연결된 형태이며, head, tail, nodeCount로 구성된다. Head : 제일 앞 노드를 가리키는 포인터 Tail : 제일 뒷 노드를 가리키는 포인터 nodeCount :..

자료구조의 필요성 상황에 알맞은 자료구조를 선택하면, 시간 단축의 이점을 얻을 수 있음 알고리즘 자료구조와 연산을 알맞게 선택하는 것 0) 알고리즘 복잡도 시간, 공간 자원을 얼마나 필요로 하는지에 대해 표현하는 것 - 선형 시간 복잡도 O(${n}$) - 로그 시간 복잡도 O(${log n}$) ex) 정렬된 수목록에서 특정값을 찾기 위해 이진트리 알고리즘을 사용 - 이차 시간 복잡도 O(${n^2}$) ex) 삽입정렬 cf) 가장 적은 시간복잡도를 갖는 정렬 알고리즘 : 병합정렬 (divide and conquer) 나눌 때 O(${log_n}$) * 합칠 때 O(${n}$) ex) 배낭문제 1) 선형배열 (List) 연산 - 원소 추가 L.append(value) - 원소 삭제 del(L[index..