본문 바로가기

분류 전체보기

 (104)
[LeetCode] Valid Parentheses https://leetcode.com/problems/valid-parentheses/description/ [문제] Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type. E..
덱/데크 (Deque), 우선순위 큐 (Priority Queue) 덱 (Deque : Double Ended Queue) 덱은 특수한 형태의 큐로서 삽입, 삭제가 front와 rear 양 끝에서 가해질 수 있도록 허용한 자료구조다. 허용되는 작업을 이렇게 정의하면 이 구조는 사실상 큐로 작동할 수도 있고, 스택으로 작동할 수도 있다. 주요 함수 AddLast() AddFirst() RemoveLast() RemoveFirst() 시간 복잡도 삽입 : O(1) 삭제 : O(1) 검색 : O(1), index를 통해 random access가 가능하다. 구현 양 끝에서 삽입 삭제가 일어난다는 점을 감안하면 덱 구조에서는 포인터 두 개를 유지하는 것이 유리하다. 연결 리스트라면 헤드 포인터와 테일 포인터 두 개를 가져야 함을 의미한다. 또, 테일이 가리키는 마지막 노드에서 ..
큐 (Queue) 선형 자료 구조 큐(Queue)는 스택과 정 반대되는 개념으로, 가장 먼저 삽입된 것이 가장 먼저 삭제되는 선입선출 (FIFO, First-In, First-Out) 구조를 가지고 있다. 뭔가를 기다리며 서 있는 줄이나, 컴퓨터 키보드 명령이 한 줄을 다 칠 때까지 키보드 버퍼 메모리에 큐를 형성한 채 기다리는 것이 그 예이다. 스택에서 삽입, 삭제 모두가 맨 뒤에서 일어나는 데 비해 큐에서 삽입은 맨 뒤에서, 삭제는 맨 앞에서 이루어진다. 즉 큐는 양쪽 끝이 모두 사용된다. 큐 프런트(front) : 큐의 맨 앞 큐 리어(rear) : 큐의 맨 뒤 add / enqueue: 큐 리어에 데이터 삽입 remove / dequeue : 큐 프런트의 데이터 삭제 peek : 큐 프런트의 값 반환 시간 복잡도 ..
스택 (Stack) 스택 (Stack) 스택은 프로그램에서 가장 자주 사용하는 추상 자료형 중 하나로, '쌓아놓은 더미'를 뜻한다. 책상 위에 쌓아놓은 책, 설거지를 위해 쌓아놓은 식판, 창고에 쌓인 박스 등이 모두 스택이다. 스택 구조를 일반적으로 후입선출 (LIFO:Last-In First-Out) 구조라 부르며, 가장 나중에 들어온 데이터가 가장 먼저 빠져나가게 된다. 스택에서의 삽입, 삭제는 한 쪽 끝에서만 일어난다고 생각하면 된다. 인터넷 브라우저의 '되돌리기' 기능이 스택의 대표적인 기능 중 하나이다. 스택에서 일반적으로 생각해볼 수 있는 메소드들은 다음과 같다. push - 스택 맨위에 항목을 삽입 pop - 스택 맨위에 항목 삭제 peek or top - 스택의 맨 위(top)를 표시 isEmpty - 스택이..
리스트 리스트(List)는 목록 또는 도표를 추상화한 것으로, 여러 데이터 항목을 모아서 한꺼번에 관리할 수 있도록 한 것이다. 우리 주변의 수많은 정보들이 도표로 조직화되어 있기 때문에 리스트는 프로그램에서 가장 많이 사용하는 추상 자료형 중 하나이다. 주 작업으로는 삽입(Insertion), 삭제(Deletion), 검색(Retrieval) 등이 있다. 리스트는 순서가 있다는 점과 중복을 허용한다는 점에서 집합과 구별되고, 갈림길 없이 일렬로 나열되어 처음과 끝이 각각 하나씩 있다는 점에서 그래프와도 구별된다. 리스트의 구현은 배열을 사용하는 방법과 포인터를 사용하는 방법으로 나뉜다. 전자를 순차 리스트 또는 배열 기반 리스트(Array List)라고 하고 후자를 연결 리스트(Linked List)라고 한다..
재귀호출 (Recursive Call) 재귀(Recursion) : 주어진 문제를 그보다 작은 문제로 환원하는 것. 재귀호출(Recursive Call) : 프로그램을 실행하기 위해 자기 자신을 호출(Self call)하는 것. 문제 크기(Problem Size)는 데이터 양(Data Size)을 말한다. 크기 100의 문제를 크기 99의 문제로, 이를 다시 크기 98의 문제로 환원해서 결국에는 곧바로 해결 가능한 크기 1의 문제로 만들 때, 이처럼 큰 문제를 보다 작은 문제로 환원하여 이를 해결함으로써 큰 문제의 해결에 이르는 접근 방식을 분할 정복(Divide and Conquer) 전략이라 부른다. (수학적 귀납법-Mathematical induction과 순서를 반대로 적용한다고 보면 된다.) 재귀호출 함수가 자기 자신을 호출하는 이유..
배열, 구조체 배열 1. 배열 인덱스 배열(Array)이란 동일한 데이터 타입의 변수 여러 개를 하나로 묶어서 관리하기 위한 것으로, 인덱스를 사용하여 필요한 요소(Element)가 있는 곳을 단번에 찾아 갈 수 있다는 것이 가장 큰 특징이다. (직접 접근, Direct Access) 원하는 요소를 찾기 위해서는 해당 요소가 있는 주소를 알아내야 하는데, 해당 인덱스로부터 주소를 찾는 작업은 컴파일러가 계산하며 이는 다음과 같다. i번째 요소의 시작 요소 = &A[0] + (i - 1) x sizeof(Element Type); 이러한 계산이 가능한 근본적인 이유는 배열요소가 메모리 내에 서로 붙어 있기 때문이다. 배열 A의 시작 주소가 200번지라면 A[0]는 200번지에, A[1]은 204번지에서 시작한다. 때에 ..
추상 자료형 (ADT, Abstract Data Type) 사용과 구현의 분리 추상 자료형의 가장 큰 특징 중 하나로 내가 어떤 데이터 타입을 추상적으로 정의해서 사용했다면 실제로 그 데이터 타입을 구체적으로 구현하는 것은 남에게 맡길 수도 있다는 시각. 사용하는 관점과 구현하는 관점을 명확히 분리함으로써 프로그램 하나를 여러 사람이 나누어서 짜는 데 매우 유용함. 일반성 (Generality) 대표적인 추상화의 속성으로 작업을 정의하는 데 있어서 특수한 경우는 무시한다는 것. 이는 어떤 특정한 목적을 배제함으로써 해당 작업의 범용성 (General Usability)을 높이기 위한 것이다. 사용자 관점 (User View, Interface View)의 추상 자료형 1) 작업명 2) 용도 구현자 관점 (Implementation View)의 추상 자료형 1) ..

티스토리툴바