학교/자료구조와 알고리즘

6. 순환

잠깐동안 tistory를 또 작성하지 못했다. 오늘의 내용은 순환이다. 순환이란? - 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법이다. - 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다. 예를 들어 정수의 팩토리얼은 다음과 같이 정의된다. n! = 1 (n=0) n! = n*(n-1)! (n>=1) 위의 정의에서 팩토리얼 n!을 정의하는데 다시 팩토리얼(n-1)!이 사용되었다. 이러한 정의를 순환적이라 한다. 위의 정의에 따라 n!를 구하는 함수 factorial을 제작해보자면, int factorial(int n) { if( n

5. 빅오 표기법 & 최선, 평균, 최악

입력자료의 개수가 큰 경우에는 차수가 가장 큰 항이 전체의 값을 주도하기 때문에 보통 시간복잡도 함수에서 차수가 가장 큰 항만을 고려하면 충분함. + 수행시간이 서로 다른 연산들의 수행 시간을 같다고 가정하였기 때문에 정확한 비교가 의미가 없을 수도 있음. 따라서 시간 복잡도 함수에서 중요한 것은 n이 증가하였을 때 연산의 총 횟수가 n에 비례하여 증가하는지, 아니면 다른 증가추세를 가지는지가 더 중요함. '시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복 잡도를 표시하는 방법'을 빅오 표기법이라고 함. 즉 알고리즘이 n에 비례하는 수행시간을 가진다고 말하는 대신에 알고리즘 의 시간복잡도가 O(η) 이라고 함. 빅오 표기법의 수학적 정의 두개의 함수 f(n)과 g(..

4. 알고리즘

요즘 많은 테크 기업들이 코딩 테스트의 비중을 높이면서 알고리즘 해결 능력의 중요도가 높아졌다. 이번 게시물에서는 알고리즘을 왜 배워야 하는지와 알고리즘의 기초에 대해 다뤄볼 것이다. (아마 좀 길 수도 있을 것 같다) 요즘의 컴퓨터는 예전의 컴퓨터에 비하여 엄청난 계산속도와 방대한 메모리를 자랑하고 있으며 또한 계속하여 발전을 거듭하고 있다. 그렇다면 프로그램 작성 시에 계산시간을 줄이고 메모리를 효과적으로 사용하기 위하여 더 이상 고민할 필요는 없는 것일까? 하지만 요즘에도 여전히 프로그램의 효율성은 중요하다. 첫 번째 이유는 최근 상용 프로그램의 규모가 이전에 비해서는 엄청나게 커지고 있기 때문이 다. 즉 처리해야할 자료의 양이 많기 때문에 알고리즘의 효율성이 더욱 중요하게 된다. 알고리즘 간의 효..

3. 추상 자료형

이번 내용은 추상 자료형이다. 자료형이란 용어 그대로 "데이터의 종류"이다. 정수, 실수, 문자열 등이 기초적인 자료형의 예. 이러한 자료형은 프로그래밍 언어가 기본적으로 제공하고 이외에도 많은 자료형이 존재함. C언어에는 정수, 실수, 문자를 나타내는 기초적인 자료형과 다른 자료형을 묶을 수 있는 배열이나 구조체도 있음. 배열 : 동일한 자료형이 여러 개 모인 것 구조체 : 다른 자료형이 여러 개 모인 것 데이터의 종류가 결정됨에 따라 그 데이터와 관련된 연산도 달라짐. Ex. 나머지를 계산하는 연산자는 정수 데이터에서는 의미가 있지만 실수 데이터에서는 의미가 X 자료형이라고 하면 데이터뿐만 아니라 데이터 간에 가능한 연산도 고려하여야 함. 복잡한 자료형을 구현할 떄는 연산이 연산자가 아니고 함수로 작..

2. 알고리즘

이전에 썼던 1. 자료구조 내용의 연장이다. 내용이 길어서 나눠서 정리하게 되었다. 알고리즘이란 쉽게 말하면 문제를 해결할 수 있는 방법이다. 컴퓨터를 이용하여 전화번호부에서 특정한 사람의 이름을 찾는다고 할 때, 한 가지 방법은 전화번호부의 첫 페이지부터 시작하여 한 장씩 넘기면서 특정한 사람을 찾는 것이다. 이 방법은 엄청난 시간이 걸리는 방법이고 보통 이런식으로 찾는 사람은 거의 없을 것이다. 또 하나의 방법은 전화번호부의 이름들이 정렬되어 있음을 이용하는 방법이다. 즉 찾고자 하는 이름이 "박철수"라고 할 때 전화번호부의 중간에 있는 이름과 "박철수"를 비교한다. 중간에 있는 이름보다 앞에 있다면 앞부분만 검색하고 그렇지 않다면 뒷부분만 검색하면 된다. 이 방법은 굉장히 효율적인 방법이고 일반적인..

1. 자료구조

학교에서 강의를 들은지는 꽤 됐지만 중간고사 공부도 할 겸 다시 정리하는 시간을 갖고자 글로 정리를 하게 되었다. 첫번째 내용은 자료구조와 알고리즘의 정의에 관한 것이다. 참고로, 이 책은 2019년 생능출판사에서 나온 천인국, 공용해, 하상호 저의 C로 쉽게 풀어쓴 자료구조 책과 강의자료를 토대로 작성되었다. 자료구조는 우리의 일상생활에서 유사성을 찾을 수 있다. 그릇을 쌓아서 보관하는 것은 스택, 마트 계산대의 줄은 큐, 버킷 리스트는 리스트, 영어사전은 사전, 지도는 그래프, 컴퓨터의 디렉토리 구조는 트리와 같다. 쌓인 그릇은 가장 마지막에 얹은 그릇을 가장 먼저 뺄 수 있으므로 스택의 특성과 같다. 마트 계산대의 줄은 먼저 온 사람이 먼저 계산할 수 있으므로 큐의 특성과 같다. 이처럼 자료구조는 ..