본문 바로가기

Computer Science&Engineering/자료구조

 (4)
알고리즘의 성능 분석 (시간복잡도 계산 방법) # 어떤 알고리즘이 성능이 좋을까? 알고리즘의 성능을 분석하기 위해서 여러 방법을 쓸 수 있다. 가장 쉬운 방법은 알고리즘의 실제 실행시간을 측정해보는 것이다. 실행시간을 비교하면서, 어떤 알고리즘이 성능이 좋고 빠른지 알 수 있다. 하지만 이 방법에는 크게 두 가지 단점이 있다. 하나는 실제로 알고리즘을 구현해야 한다는 것, 다른 하나는 컴파일러나 실행 기기에 실행시간이 의존한다는 사실이다. 이러한 한계를 극복하기 위하여 복잡도 분석을 사용할 수 있다. # 복잡도 분석 실제로 구현하지 않고, 실행환경에 의존하지 않으면서 알고리즘의 성능을 분석할 수 있는 방법이다. 알고리즘에서 실행되는 산술 동작의 갯수를 세보는 방법이다. 복잡도 분석에는 두 가지 종류가 있는데, 시간 복잡도 분석과 공간 복잡도 분석이다..
추상 데이터 타입 (Abstract Data Type) 이란 # 데이터 타입(Data type)이란 : 자료와 연산들의 모음 예를 들어, int 형 데이터 타입은 .. -2, -1, 0, 1, 2 ... 와 같은 정수 자료와 +, -, /, * % 등의 연산들의 모음이다. # 추상 데이터 타입(Abstract Data Type, ADT)이란 : 추상적으로 수학적으로 정의된 데이터 타입 : 어떠한 자료와 자료의 연산이 정의되어 있다. 연산은 추상 데이터 유형과 외부 간의 인터페이스 역할을 한다. 실제로 자료와 연산이 어떻게 구현되었는 지는 사용자가 알 필요가 없다. 예를 들어, 자연수를 추상 데이터 타입으로 정의하자면, 자료는 0부터 INT_MAX까지의 정수 연산은 zero(), is_zero(), add(x,y), sub(x,y), equal(x,y), succe..
자료구조와 알고리즘은 무엇인가 # 프로그램 = 자료구조 + 알고리즘 프로그램은 자료구조와 알고리즘으로 이루어진다. 예를 들어, 최대값을 찾는 프로그램은 배열이라는 자료구조에 순차탐색 알고리즘을 이용하여 구현할 수 있다. 따라서, 컴퓨터 프로그램을 짜려면 자료구조와 알고리즘을 잘 익혀두어야 한다. # 자료구조의 종류와 예시 - 스택(Stack) : 스택은 영어로 "쌓아두다"라는 뜻이다. 따라서 책을 쌓아두는 것을 떠올리면 된다. - 큐 (Queue) : 큐는 영어로 "열, 줄 세우기"라는 뜻이다. 마트에서 계산할 때 줄서는 것을 생각하면 된다. - 리스트 (List) : 리스트는 "목록" 정도로 생각하면 좋을 것 같다. 할 일 목록이 순서대로 나열된 것을 예로 들 수 있다. - 트리 (Tree) : 트리는 "나무"이다. 나뭇가지가 뻗어..
자료구조(Data Structure) 정리 시작 # 무려 3년전 수강한 자료구조 최근 SCSA 과정을 통해 자료구조를 다시 공부하면서, 학교다닐 때 배웠던 자료구조를 정리할 필요성을 느끼게 되었다. 자료구조 수업을 들을 당시에는 매 주 수업이 너무 빡세서, 정리고 뭐고 그냥 매 주 나간 진도 맞춰 복습하기에도 바빴다. 자료구조 수업을 맡으신 교수님이 학교에 새로 부임하신 열정 넘치시는 교수님이셔서, 매 주 코딩 과제가 있었고 - 그 과제를 3번 안내면 F (fail)를 주신다고 하셨다. 실제로 16주 수업에 연휴이나 중간기말 기간 2~3주를 제외하고 10번 이상의 과제가 있었다. 과제를 내기만 하면 되는 것이냐? 그것도 아니었다. 과제를 내주실 때 2~3문제를 주시는데, 채점해서 30점 이상 받아야 1회 제출로 쳐주신다. 과제를 다 내고도 점수를 받지..

티스토리툴바