컴퓨터 공학(Computer Engineering)/자료구조(Data Structure) (4) 썸네일형 리스트형 떡국 = (떡국떡)국 = ((떡국떡)국떡)국... [재귀프로그램] 재귀 프로그램은 어떤 함수(Procedure)가 어떤 함수를 반복해서 호출하는 경우 생기는 순환적 특성을 이용한 프로그램을 의미한다. 같은 해결법을 반복해서 수행하며, 보통 큰 문제로부터 수행 단계가 깊어질수록 작은 문제로 쪼개 해결하는 방식을 취하기 때문에 분할 및 정복(Divide and Conquer)이라고 할 수 있다. 재귀 구조는 반복(for문) 문을 이용한 구조로 바꿀 수 있다. 재귀 구조와 반복 구조를 비교해보면, 재귀 구조의 경우 코드가 간단하고 명료해질 수 있다는 장점이 있으나, 반복적 함수 호출을 위한 시간적 오버헤드 및 함수 호출 스택이 필요하다는 등의 공간적 오버헤드가 발생한다. 백문이 불여일견이라고, 말이 긴 것보다 예제를 보는 것이 빠를 수도 있다. 대표적인 예로는 피보나치수열이.. O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) [시간복잡도] for i in range(n): for j in range(n): print('hello n^2') 위 코드는 얼마나 복잡한가? 내가 짠 코드나 알고리즘이 얼마나 복잡한지, 또는 시간이 얼마나 걸리는지를 나타내는 지표가 있을까? 있다. 그것이 바로 시간 복잡도(Time Complexity)이다. 시간 복잡도를 나타내는 방법은 Big-O, Omega, Theta가 있다. 그중에서 특히 Big-O는 시간 복잡도의 상한을 나타내기 때문에, 결국 코드의 최소 실행시간보다는 최대 실행시간이 얼마인지 더 중요하다는 점에서 알고리즘의 시간 복잡도의 대표적인 지표로 사용한다. 그에 대해 간단히 알아보자. Big-O(O) Big-O는 어떤 알고리즘 식의 최고 차수의 상한(점근적 상한, Asymptotic Upper B.. 65 83 67 73 73, 이것은 컴퓨터의 글자다. [컴퓨터의 숫자와 문자 표현] 컴퓨터는 2진수를 이용해 자료를 표현한다. 2진수는 0과 1이 한 자릿수를 이루는 숫자 체계로, 1011(2)의 경우 십진수로 나타내려면 다음과 같다. (23 * 1) + (22 * 0) + (21 * 1) + (20 * 1) = 8 + 0 + 2 + 1 = 11 컴퓨터는 2진수를 기반으로 8진수, 16진수 등 다른 진수 기반의 수를 표현 가능하다. 그러나 지금 이 글 또한 컴퓨터가 나타내는 문자이듯 컴퓨터는 문자 또한 표현이 가능해야 한다. 컴퓨터에서는 이를 어떻게 표현하고 다루는지 몇 가지 경우들을 알아보도록 하자. 수치 자료(Numeric Data) 1. 10진수 우선 우리가 현실세계에서 흔히 쓰는 10진수 연산을 위한 방법들이 있다. 팩(Pack) 형식과 언팩(Unpack 또는 Zone) 형식이 .. 500GB짜리 용량의 디스크가 실제로 500GB가 아닌 이유? [자료구조의 개념과 단위] 500GB짜리 새 SSD를 사서 컴퓨터에 설치했다. 두근거리는 마음으로 용량을 확인해봤더니 이게 뭐야? 500GB보다 꽤나 부족한 용량이다. 이 때문에 당황한 기억이 있는 사람들이 있을 것이다. 분명히 500,000,000,000바이트가 넘는 디스크를 달았는데도 불구하고 왜 실제 용량은 465GB인 걸까? 이를 알기 위해서는 컴퓨터 자료구조에 대해 반드시 알아야... 하는 것은 아니지만 자료구조의 개념과 컴퓨터가 자료를 표현하는 방법 및 그 단위에 대해 간략하게 알게 된다면 당황하지 않을 수 있다. 자료(Data) 자료, 혹은 데이터라고 하면 더 익숙할 이것은, 관찰 또는 측정을 통해 수집된 숫자 또는 문자 등으로 나타낼 수 있는 값을 의미한다. 이는 자료들이 반드시 어떤 정보를 담고 있어야 한다는 것은.. 이전 1 다음
