본문 바로가기

자료구조

[TIL] 2주차_Day5: 자료구조/알고리즘 풀기(5) 💡Today I Learned 자료구조/알고리즘에 대한 다섯 번째 이론 및 실습 강의를 진행했습니다. 코딩테스트 연습 _ 프로그래머스 코딩테스트 연습 문제 풀이 해시, 그리디, 정렬 알고리즘을 사용하는 대표 문제 풀이 1. 힙(Heap) 대표 문제: #더 맵게 - 최악의 경우: 수가 하나 남을 때까지 섞어야하는 경우 → n-1 회 - 각 단계(=섞는 일)에서 요구되는 계산량: 섞은 아이템을 정렬된 리스트 내에 삽입 → O(N) → 전체 문제의 복잡도: O(N^2) 느림 → 최대/최소 원소를 빠르게 꺼내기를 원함 = max/min heap 자료구조 사용 - 연산별 복잡도 heapify → O(NlogN) _ 빈 힙에 N개의 원소를 하나씩 넣어가며 heap을 유지 insert → O(logN) remove .. 더보기
[TIL] 2주차_Day4: 자료구조/알고리즘 풀기(4) 💡Today I Learned 자료구조/알고리즘에 대한 네 번째 이론 및 실습 강의를 진행했습니다. 코딩테스트 연습 _ 프로그래머스 코딩테스트 연습 문제 풀이 해시, 그리디, 정렬 알고리즘을 사용하는 대표 문제 풀이 1. 해시(Hash) - [key: value] pair → hash function을 통해 → hash table의 각각의 칸(hash bucket)에 저장 - hash collision(해시 충돌): 두 개 이상의 서로 다른 key가 서로 같은 bucket에 hash될 때(=사상될 때) - 파이썬의 dictionary가 해시로 구현 → dict 아이템에 접근 → O(1) 상수 시간에 이뤄짐 - #완주하지 못 한 선수 → O(N) 2. 탐욕법(Greedy) - 알고리즘 각 단계에서, 그 순.. 더보기
[TIL] 2주차_Day3: 자료구조/알고리즘 풀기(3) 💡Today I Learned 자료구조/알고리즘에 대한 세 번째 이론 및 실습 강의를 진행했습니다. 큐, 트리, 힙 자료구조의 개념 및 실습 1. 큐(queue) - 선입선출(FIFO, First In First Out) - 큐를 추상적 자료구조로 구현: 1) 배열 2) 연결 리스트(LL) - 배열로 구현한 큐의 연산 복잡도 size, isEmpty, enqueue, peek: O(1) dequeue: O(N) → 맨 앞의 원소를 꺼낸 후, 뒤의 원소들을 앞으로 당겨와야 함 - Doubly LL로 구현한 큐의 연산 복잡도 size, isEmpty, peek, enqueue, dequeue: O(1) → head와 tail을 이용해 head dummy node의 뒤에 enqueue, tail dummy n.. 더보기
[TIL] 2주차_Day2: 자료구조/알고리즘 풀기(2) 💡Today I Learned 자료구조/알고리즘에 대한 두 번째 이론 및 실습 강의를 진행했습니다. 연결 리스트, 양방향 연결 리스트, 스택 자료구조의 개념 연결 리스트, 양방향 연결 리스트의 삽입/삭제 멤버 메소드로 구현 스택을 활용한 후위 표기법 변환, 계산 알고리즘 구현 1. 추상적 자료 구조 - 내부 구현을 숨겨두고 데이터+연산은 외부에서 사용 가능 2. 연결 리스트 (Linked List, LL) - Node들이 연결됨 - Node(구조체) 속성: data(문자열, 레코드, 또다른 연결 리스트 etc..) link / next (다음 노드 가리킴) - 리스트 속성: head: 연결 리스트의 맨 앞 노드를 가리키는 포인터 tail: 연결 리스트의 맨 끝 노드를 가리키는 포인터 num_of_node.. 더보기
[TIL] 2주차_Day1: 자료구조/알고리즘 풀기(1) 💡Today I Learned 자료구조/알고리즘에 대한 첫번째 이론 및 실습 강의를 진행했습니다. 배열 / 정렬, 탐색, 재귀 알고리즘 / 알고리즘의 복잡도 관련 이론 리스트, 탐색, 재귀 알고리즘에 관한 실습 문제 풀이 1. 자료구조 & 알고리즘 - 자료구조 = data + data에 대해 행할 수 있는 연산 - 알고리즘: 주어진 문제를 해결하기 위한 자료구조와 연산 방법을 선택 - ex) List 내 특정 item을 찾을 때 → 정렬된 List에서 item을 찾는 것이 효율적 → 순서가 정렬된 자료구조가 좋겠음 2. 선형 배열 - 원소들을 순서대로 늘어놓은 것 - 0-based indexing - (in python) List는 여러 타입의 자료를 함께 저장 가능 - 리스트 중간의 원소 삭제 방법 간.. 더보기
반응형

티스토리툴바