이 장에서 다룰 내용
•
왜 컴퓨터 과학 이론이 우리의 생존과 연관되어 있는가?
•
사용자에게 적합한 유형 만들기
•
알고리즘의 특성 이해하기
•
아무도 알려주지 않은 자료 구조와 이상한 특성
•
컴퓨터 과학 이론은 소프트웨어 개발과 무관해 보일 수도 있다.
◦
기존 라이브러리와 프레임워크는 이런 내용에 이미 최적화되고 잘 테스트되어 신뢰성있는 방식으로 이 작업들을 처리한다.
•
왜 이론에 신경 써야할까? 컴퓨터 과학의 이론은 알고리즘과 자료구조를 처음부터 개발할 수 있게 해줄 뿐 아니라 언제 사용해야할 지 알려주기 때문이다.
◦
결정하기 어려운 상충 관계에서 도움을 주며, 작성 중인 코드의 확장성을 이해하는 데도 도움이 된다.
•
여기서는 데이터 타입에서 잘 알려지지 않은 내용 몇 가지와 알고리즘의 복잡성, 특정 데이터 구조의 내부 동작 방식을 이해하는 등 이론의 중요한 부분만을 살펴볼 예정이다.
1. 알고리즘 특강
•
알고리즘이란 어떤 문제를 해결하기 위해 필요한 규칙과 단계를 모아놓은 것이다.
•
평범한 알고리즘인 세다트 알고리즘부터 이진 탐색까지 이어가면서 왜 특정 알고리즘이, 다른 알고리즘에 비해 더 좋은 성능을 가지는지, 알 수 있다.
1. 빅오를 더 잘 이해하면 좋다.
•
빅오 표기법은 작명에서 알 수 있듯, 증가를 설명하기 위한 표기법일 뿐으로, 이를 통해 알고리즘이 얼마나 확장되는지를 가늠할 수 있다.
•
가령, 모든 요소를 순서대로 검토하는 경우, 배열의 요소 개수에 선형 비례하는 연산을 수행한다. 이것을 O(N)이라고 쓰며, 여기서 N은 요소의 수를 의미한다.
◦
이는, 우리에게 알고리즘이 정확하게 어떤 단계를 걸쳐 수행되는지를 알려주진 않지만, 적어도 데이터 크기에 따라 성능이 어떻게 달라질지는 알려준다.
•
빅오 표기법은 시간 복잡도뿐이 아닌, 공간 복잡도라 불리는 메모리 사용의 증가를 측정하는 곳에도 사용된다.
•
빅오는 증가에 대한 것이기 때문에 가장 중요한 부분은 표기법에서 가장 큰 증가 함수이다.
◦
실질적으로 말하자면 빅오 관점에서 O(N)과 O(4N)은 동일하다.
◦
반면, O(N·M)에서 점은 곱셈 연산자를 의미하며, N과 M이 모두 증가할 때 N과 M이 모두 증가하며 이때 O(N)과 O(N·M)은 같지 않다.
◦
O(N·logN)은 O(N)보다 살짝 안 좋지만 O(N^2)만큼 나쁘지는 않다.
•
알고리즘의 실행 속도와 메모리 사용량이 증가하는 것을 빅오 표기법으로 제대로 설명할 수 있어야 자료구조와 알고리즘을 잘 선택할 수 있다.
◦
즉, 알고리즘을 직접 구현할 필요가 없어도 빅오에 익숙해져야 한다.
2. 내부 데이터 구조
•
자료구조란 데이터를 어떻게 배치하는지에 대한 것이다. 데이터를 어떻게 배치하는가에 따라 데이터가 유용해질 수 있다.
•
실제로 데이터는 우리가 생각하듯 직관적으로 저장되지 않는다. 0, 1의 숫자로 표현되며 이러한 내용을 상기시키는 이유는 미리 알아두고 두려워하지 않아야하기 때문이다.
1.
문자열
•
문자열은 용도나 구조적인 측면에서 배열과 유사하지만 보통은 불변이다.
•
문자열 생성과 관련한 요청을 조금 더, 효율적으로 처리하고 싶다면 C#의 StringBuilder와 같은 라이브러리를 시도해보면 좋다.
◦
StringBuilder는 문자열을 추가할 때마다 메모리를 재할당하고 복사하는 대신, 내부적으로 연속 메모리 블록을 사용한다. 따라서 앞선 방법보다 효율적이다.
•
문화권을 이해하면 문자열 작업이 더 안전해지고 빨라질 수도 있다.
◦
문화에 따라 문자가 달라지고, 언어에 따라 언어가 달라지므로, 이런 구체적인 설정들을 지원하는 라이브러리들을 사용하면 이들 모두 해결하는데 도움이 된다.
2.
배열
•
배열은 배열 크기를 초과하지 않는 개수만큼의 데이터를 저장하는데 탁월하다.
◦
즉, 크기를 키우거나 바꿀 수 없는 정적 구조이다. 더 큰 배열을 원한다면 배열을 새로 만들고 기존 배열을 복사해야 한다.
•
배열은 문자열과 달리 변경이 가능하다. 이때문에 불필요한 변경문들이 우후죽순 생겨날 수 있다.
◦
이를 주의해야 한다. 스스로 상태를 바꾸도록 놔둬서는 안 된다. 이는 모든 악의 근원이다.
3.
리스트
•
리스트는 StringBuilder의 작동 방식과 유사하게 크기가 가변적인 배열처럼 동작한다.
•
거의 모든 곳에서 배열 대신 리스트를 사용할 수 있겠지만 이는 불필요한 성능 저하를 불러일으킬 것이다.
◦
이는 배열은 직접 접근하는 반면, 리스트에서는 인덱스된 접근을 사용하기 때문이다.
◦
이는 가상 함수를 호출하는 것으로, 객체 지향의 다형성이라는 특징상, a라는 인터페이스의 함수 read()는 그 구현체의 구현을 찾아 실행되어야 하기 때문에, 인덱스된 접근을 사용하게 된다.
4.
연결 리스트
•
연결 리스트란 요소가 메모리 안에서 연속적이지 않고 각 요소가 다음 항목의 주소를 가리키는 리스트를 말한다.
◦
삽입이나 삭제 작업에 O(1) 복잡도를 가지므로 유용하다. 다만 개별 항목이 메모리 내 어디에나 저장되기 때문에 조회 성능이 좋지는 않다.
▪
물론, 양 끝에 포인터를 두어 속도를 줄일 수는 있다.
◦
그렇다고 항상 연결 리스트가 리스트보다 빠른 것은 아닌데, 전체 메모리 블록을 한 번에 할당하고 추가적인 참조 검색을 수행하는 대신, 각 요소를 위해 개별적으로 메모리를 할당하는 경우, 성능에 이슈가 생길 수 있다.
◦
시스템 프로그래밍에 관심이 없는 한, 연결 리스트를 마주칠 일은 잘 없으나, 면접 시 골치 아픈 질문을 목적으로 한 질문에 마주하게될 수도 있다.
5.
큐
•
데이터를 삽입한 순서대로 리스트에서 항목을 읽을 수 있다.
6.
딕셔너리
•
해시맵 혹은 키/값으로도 알려진 딕셔너리는 가장 유용하고 많이 사용되는 자료구조 중 하나다.
•
우리는 이 자료구조의 조회 성능을 당연하게 여기고는 한다. 그렇다면 왜 성능이 좋은 것일까?
◦
비밀은 단어 해시에 존재한다. 해싱을 통해, 우리는 언제나 특정 값에 대한 해싱 넘버를 가지고 접근을 하면 그 값과 매칭되는 값이 항상 반환됨을 신뢰할 수 있기 때문이다.
•
중복이 발생하면 어떻게 될까? 딕셔너리는 이를 배열이나 트리, 리스트에 보관한다.
◦
즉, 중복이 발생하면 조회 성능이 저하됨을 알 수 있다.
•
딕셔너리를 사용하지 말아야할 때는 언제일까? 키-값 쌍을 단순히 순차적으로 사용하는 경우, 의미가 없다.
7.
해시 집합
•
집합은, 고유한 값을 가진다는 점을 제외하고는 배열이나 리스트와 같다.
•
HashSet은 조회나 삽입이 빠르기 때문에, 교집합이나 합집합을 구하는 작업에도 적합하며, 보통은 이런 기능을 함께 지원한다.
◦
이 경우, 해시 함수가 매우 중요하다.
8.
스택
•
스택은 후입 선출법을 따르는 큐라고 볼 수 있다.
9.
호출 스택
•
함수의 반환 주소를 저장해 호출된 함수의 실행이 완료되면 반환할 위치를 알려주는 자료구조이다. 보통은 스레드 당 하나 씩을 가진다.
•
이는 반환 주소뿐 아니라 함수의 매개변수와 로컬 변수도 포함한다.
3. 타입에 대한 과대 포장은 무엇인가?
•
프로그래머는 보통 타입을 당연한 것으로 여긴다.
•
심지어 어떤 사람들은 프로그래머가 각 변수의 타입을 결정하는 것과 같은 세부 사항을 다룰 필요가 없는 자바스크립트나 파이썬같은 동적 타이핑 언어를 쓸 때 더 빠르다고들 주장한다.
1. 타입에 강해지기
•
타입은 기본적으로 코드의 정확도를 무료로 검사하기 때문에 기본 타입 시스템을 이해하는 것은 생산적인 프로그래머가 되는 데 큰 도움이 된다.
•
강한 타이핑(strong typed)과 약한 타이핑(weakly typed)은 서로 다른 타입의 변수에 다른 타입의 값을 할당할 수 있는지, 즉 프로그래밍 언어가 얼마나 관대한지를 의미한다.
정적 타입의 변수는 런타임 시 변경할 수 없다. | 동적 타입의 변수는 런타임 시 변경할 수 있다. | |
강한 타이핑: 서로 다른 타입으로 대체할 수 없다. | C#, 자바, 러스트, 스위프트, 코틀린, 타입스크립트, C++ | 파이썬, 루비, 리스프 |
약한 타이핑: 서로 다른 타입으로 대체할 수 있다. | 비주얼 베이직, C | 자바스크립트, 비주얼 베이직 스크립트 |
•
왜 타입을 사용해야할까? 답은 단순하다. 타입을 통해 우리는 더 안전하고, 더 빠르고, 더 쉽게 유지보수할 수 있는 코드를 작성할 수 있다.
◦
외에도 변수 타입을 선언하고 클래스에 주석을 달아서 시간을 손해보더라도, 디버깅할 버그가 줄어들고 성능 문제가 덜 발생하기 때문에 잃어버린 시간은 금방 만회할 수 있다.
•
이러한 명백한 이점 외에도 타입은 약간의 소소한 이점도 추가로 가지고 있다. 함께 알아보자.
2. 유효성 증명
•
유효성 증명이란 사전 정의된 타입을 사용하는, 잘 알려지지 않은 이점 중 하나이다.
•
사용자의 입력은 항상 유효성 검사를 수행해야 한다. 잘못된 입력으로 인해 코드 어딘가에선 예상치 못한 예외가 발생하기 때문이다.
•
데이터 유효성 검사는 코드 전반에 걸쳐 유효성을 증명하는 것이 아니다. 다음 그림은 애플리케이션에서 입력에 대해 유효성을 검사하는 지점을 알려준다.
•
타입은 유효성 증명을 넘겨줄 수 있다. 게시물 식별자를 위한 정수 값이나 사용자 이름을 위한 문자열 값 자체를 전달하는 대신, 입력을 검증하는 클래스나 구조체를 전달할 수 있기 때문에 유효하지 않은 값이 포함되는 것은 불가능하다.
◦
이는 간단한 것 같지만 강력한데, 매개변수로 포스트 식별자를 받는 함수는 정수 대신 PostId라는 클래스를 요구한다. 이렇게 하면 생성자가 먼저 유효성 검사를 한 후에 유효성 증명을 그대로 전달한다.
•
사용자 정의 데이터 타입은 원시 타입보다 설계를 더 잘 설명할 수 있고 반복적인 유효성 검사를 피할 수 있으므로 버그 예방에도 도움이 된다.
◦
번거롭더라도 구현할 가치가 있으며, 이미 프레임워크에서 제공해주고 있을 수도 있다.
3. 무조건 프레임워크를 사용하지 말고 똑똑하게 활용하라
•
프레임워크는 보통, 우리의 개발을 더 편하게 해주는 훌륭한 유틸리티로 가득 차 있다.
•
이것을 공부하는 것이 지루한 시간낭비처럼 비춰질 수 있지만 특정 구현을 위해 알고리즘을 짜내는 것보다는 효율적이다.
4. 오타 이상의 타입
•
데이터 타입을 사용하면 코드 설명에 큰 도움이 될 수 있다.
•
이넘과 같은 자료형을 적절히 사용하여, 매직 넘버를 방지함으로써 코드의 가독성을 향상시킬 수 있다는 내용이다.
5. nullable이 아니라 non-nullable이라 했어야 한다
•
nullability 검사는 여러분이 작성 중인 코드에 대한 의도를 파악하는 데 도움을 준다.
•
이를 통해 우리는 그 값이 정말 선택적인지 아니면 선택적일 필요가 전혀 없는지에 대해 더 명확하게 생각할 것이다.
6. 무료 성능 향상
•
데이터 타입, 구조, 알고리즘의 성능 특성을 기본적으로 이해하고 있다면 성능을 더 높이는 방향으로 나아갈 수 있다.
◦
성능과 확장성은 단일 차원의 개념이 아니다.
7. 참조 타입 대 값 타입
•
참조 타입과 값 타입의 차이는 타입이 메모리에 저장되는 방식과 관련이 있다.
◦
간단하게 값 타입의 실제 변수 값은 호출 변수에 저장되는 반면, 참조 타입은 힙에 저장되고, 실제 값에 대한 참조만 호출 스택에 저장된다.
•
참조 타입과 값 타입의 차이를 안다면 올바른 작업에 올바른 타입을 사용할 수 있으므로 좀 더 효율적인 프로그래머가 될 수 있다.
•
값 타입은 스토리지와 성능에서 참조 타입보다 효율적이기 때문에 존재한다.
◦
참조 타입은 한 단계 우회적인 부분이 있다.
4. 요약
•
컴퓨터 과학 이론은 지루할 수 있지만, 이론을 아는 것은 우리를 더 나은 개발자로 만들어 준다.
•
타입은 일반적으로 강한 타이핑 언어에서 사용되는 것으로 알려져 있지만, 코드를 덜 작성하기 위해 사용될 수 있다.
•
각 프레임워크는 특정 데이터 타입에 대해 더 우수하고 효율적인 데이터 구조를 제공하며 이는 코드를 더 빠르고 안정적으로 만들 수 있다.
•
타입을 사용하면 코드를 더 쉽게 설명할 수 있고, 따라서 주석을 덜 작성해도 된다.
•
값 타입과 참조 타입의 차이는 매우 크며, 값 타입을 알고 있으면 좀 더 효율적인 개발자가 될 수 있다.
•
문자열의 내부가 어떻게 돌아가는지를 아는 것은 유용하며, 효율적인 개발에 도움이 된다.
•
배열은 빠르고 편리하지만 공개적으로 노출된 API에 가장 적합한 후보는 아닐 수 있다.
•
리스트는 동적으로 크기가 증가하는 경우에 유용하지만 그렇지 않을 경우 배열이 더 효율적이다.
•
연결 리스트는 독특한 데이터 구조이지만, 그 특성을 알면 딕셔너리 구조의 트레이드오프를 이해하는 데 도움이 된다.
•
딕셔너리는 빠른 키 검색에 유용하지만 해시 함수의 구현에 따라 성능이 크게 달라진다.
•
고유한 값을 갖는 리스트는 멋진 검색 성능을 위해 HashSet으로 표현할 수 있다.
•
스택은 특정한 단계를 추적하기 위한 훌륭한 데이터 구조다. 호출 스택이 대표적이다.
•
호출 스택이 작동하는 방식을 알면 값 타입이나 참조 타입이 성능에 미치는 영향을 보완할 수 있다.
