Data Science/Algorithm11 [프로그래머스] 어서와! 자료구조와 알고리즘은 처음이지? 강의노트 Part 17 [기본질문] 1) Tree란? - 뿌리 (루트; root) 노드에서 간선 (edge) 들이 마치 나무에서 뿌리로부터 잔가지로 뻗어나가듯이 가지치기된 구조 - 데이터베이스 시스템 또는 검색 엔진 등에서 아주 많이 이용 - 트리를 딱딱하게 말하면, 순환하는 길이 없는 그래프 (graph) 로 정의 노드 (nodes) 간선 (edges) 루트 노드 (root node), 리프 노드 (leaf nodes), 내부 노드 (internal nodes) 부모 (parent) 노드와 자식 (child) 노드 노드의 수준 (level) 노드의 차수 (degree) 트리의 높이 (height) - 또는, 깊이 (depth) - 부분 트리 (서브트리; subtrees) 이진 트리 (binary trees) 포화 이진 트리 .. 2019. 12. 24. [프로그래머스] 어서와! 자료구조와 알고리즘은 처음이지? 강의노트 Part 14~16 [기본질문] 1) 큐 (queue) 자료구조는? - 데이터 원소를 한 줄로 늘어세우는 자료 구조, 즉 선형 (linear) 구조(선형 배열, 연결 리스트, 그리고 스택과 비슷) - 스택: 후입선출 (LIFO; last-in first-out) - 큐: 선입선출 (FIFO; first-in first-out) , 파이포로 불림 - 인큐 (enqueue) 연산: 원소를 큐에 넣는 동작 - 디큐 (dequeue) 연산: 큐로부터 데이터 원소를 꺼내는 동작 - 그런데, 선형 배열을 이용한 연결 리스트에서는 디큐 연산이 큐의 길이에 비례하는 만큼의 시간을 소요. 배열에 저장된 데이터 원소들을 하나하나 앞 칸으로 당겨서 위치를 조정해야 하기 때문. 그래서 연산의 시간 복잡도 측면에서는 연결 리스트로 큐를 구현하는 .. 2019. 12. 20. [프로그래머스] 어서와! 자료구조와 알고리즘은 처음이지? 강의노트 Part 12~13 [기본질문] 1) 스택의 응용? - 중위 표기법 (infix notation) : 두 개의 피연산자 A 와 B 를 가지고 덧셈을 하는 수식을 표기하면 A + B 와 같이 되는데, 이 때 연산자인 + 가 두 피연산자의 사이에 (가운데에) 위치하기 때문에 중위 표기법이라고 부름 - 후위 표기법이 : 연산자를 두 피연산자의 뒤에 쓰는 방식. 따라서 앞의 예인 A + B 를 후위 표기법으로 표기하면 AB+ - 이렇게 수식을 후위 표기법으로 표기하면, 컴퓨터가 (프로그램이) 수식을 계산하는 데 유리. - 왼쪽부터 수식을 읽으면서 연산자를 만날 때마다 두 피연산자에 그 셈을 적용하면 되기 때문인데요, 이 때 스택이 이용 - 후위 표기법으로 표현된 수식의 값을 계산 (evaluate) 하는 알고리즘을 설계하고 구현 .. 2019. 12. 15. [프로그래머스] 어서와! 자료구조와 알고리즘은 처음이지? 강의노트 Part 11 [기본질문] 1) 스택(Stack)이란? - 추가된 데이터 원소들을 끄집어내면 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료 구조 - 마지막에 넣은 것이 가장 먼저 꺼내어지는 성질 때문에 스택을 다른 말로는 후입선출 (LIFO; last-in first-out) 자료 구조라고도 함 - Push 연산: 스택에 데이터 원소를 추가하는 (집어넣는) 동작 - Pop 연산: 마지막에 추가되었던 원소를 참조하고 삭제하는 (꺼내는) 동작 2) 스택의 활용도? - 컴퓨터 내부에서 프로그램이 실행할 때 함수 호출이 일어나고 함수들이 리턴하면 마지막 호출된 곳으로 돌아가는 동작을 구현하는 데에도 스택이 이용되고, 이러한 일은 컴퓨터의 동작에 핵심적인 것이기 때문에 컴퓨터 하드웨어 (프로세서) 는 어떤 방식으로.. 2019. 12. 15. 이전 1 2 3 다음
