꿈 꾸는 누렁이

오늘은 컨테이너, 이터레이터, 알고리즘이란 무엇이며, 무엇이 있는지 학습한 결과를 기록한다.

Container

컨테이너는 뜻 그대로 그릇, 무언가 담을 수 있는 역할을 한다. 즉, 자료 및 값을 저장하는 역할을 한다. 이 그릇의 모양이나 크기에 따라 담기를 권장되는 내용물이 다르고 취급 방법이 다르다.(컵이라는 그릇에 라면을 담을 수는 있지만 효율적이지 못한 것처럼.)

먼저, 컨테이너에는 순차 컨테이너, 연관 컨테이너, 컨테이너 어댑터 등이 있다. 

이게 무슨 소리인가? 

순차 컨테이너 : 뭔가 자료들이 순차적으로 들어가는거..?
연관 컨테이너 : 연관되어서 들어가는거..? 쌍으로 연관되어서 들어가는 것인가?
컨테이너 어댑터 : 어댑터란 다른 전기나 기계 장치를 서로 연결해서 작동할 수 있도록 만들어 주는 결합 도구 라는 정의가 있는 것으로 보아, 컨테이너와 컨테이너를 변환할 수 있는 그런게 아닐까?

나는 리얼로 위와 같이 생각했다. 내가 조사해 본 컨테이너들은 다음과 같다.

순차 컨테이너 

말 그대로 순차적으로 자료를 저장한다. 내 예측이 맞았다! 순차 컨테이너에서는 자료의 추가가 빠르지만 탐색할 때에는 시간이 많이 걸린다. 왜냐하면 순차적으로 접근하기 때문에!

이러한 순차 컨테이너에는 vector, deque, list 가 있다. 그렇게 벡터, 벡터했던게 바로 여기서 나오는 개념이었구나~

1. Vector : 동적 배열 처럼 동작하며, 자료는 뒤 쪽에서 추가된다.
2. Deque : 벡터와 유사하지만 앞에서도 자료들이 추가될 수 있다.
3. List : 벡터와 유사하지만 중간에서 자료를 추가하는 연산이 효율적이다.

연관 컨테이너

다음은 연관 컨테이너이다. 연관 컨테이너는 조사해 본 결과 사전과 같은 구조로 자료를 저장한다고 한다. 즉, 키와 값의 형태로 데이터가 저장되고, 자료들은 정렬되어 있으며 이러한 정렬 때문에 자료 추가에는 시간이 걸리지만 탐색은 키를 통하여 한 번에 뽑아내니 빠르다. 

이러한 연관 컨테이너에는 Set, Map, MultiSet, MultiMap 등이 있다

1. set : 집합이라고 하며, 중복이 없는 자료들이 정렬되어 저장된다.
2. map : 맵이라고 하며, key - value 형태로 저장된다.
3. multiset : 다중 집합이라고 하며, 집합과 유사하지만 자료의 중복을 허용한다.
4. multimap : 다중 맵이라고 하며, 맵과 유사하지만 키가 중복될 수 있다.

컨테이너 어댑터

드디어 컨테이너 어댑터이다!

컨테이너 어댑터는 기존 컨테이너의 인터페이시를 제한하여 만든 기능이 제한되거나 변형된 컨테이너를 의미한다고 한다. 이게 무슨 말일까 싶어서 좀 더 확인해보았는데

컨테이너 어댑터에는 Stack이 있다. 이를 예로 들자면, 기본 컨테이너인 벡터는 vector 클래스를 사용하는데 이 클래스의 인터페이스를 제한하고(벡터의 여러 기능들을 제한하고) 특정 형태(스택에 관련된 연산)의 동작 만을 수행하도록 한다.

그러니까 한 마디로 내가 어떤 자료구조를 구현할 것 인데 그냥 밑 바닥부터 구현하기 힘들고 귀찮은데 마침 기가 막히고 검증된 기존의 컨테이너가 있으니 이를 활용하여 확장 및 축소 등의 적용(Adapt)을 하는 것이라고 보면 될 것 같다. 그런데 뭔가 계속 제한한다고 하는데 이는 기존의 컨테이너에서 필요없는 부분은 사용하지 못하도록 하는 의미의 제한인 것 같다.

아무튼, 이러한 컨테이너 어댑터에는 Stack, Queue, Priority queue이 제공된다.

Iterator

이제는 반복자(Iterator)의 개념이다.

이 반복자는 각 컨테이너의 자료구조에 맞는 액세스를 할 수 있도록 도와준다. 예를 들어 순회를 한다거나, 원하는 값이 있는 메모리에 접근 가능하도록. 검증되었기 때문에 안심하고 사용해도 된다.

일종의 포인터와 비슷한 객체이다. 기존의 자료구조에서 보면 링크드 리스트에서만 보더라도 노드를 순회하기 위해서는 포인터의 값을 증가 혹은 감소시키고 여러 검사를 하는 등 작업을 했는데 반복자가 이를 대신해준다고 보면 된다. 

알고리즘마다 각기 다른 방식으로 컨테이너 요소들에 접근하기 때문에 반복자에도 여러 종류들이 존재한다. 그렇기 때문에 컨테이너를 사용한다면 꼭 반복자를 사용해야 한다.

반복자에는 몇 가지 예를 들자면 input iterator, output iterator, forward iterator, bidirectional iterator, random access iterator 등이 있다.

Algorithm

알고리즘은 문제 해결하기 위해서 그 절차나 방법의 공식화를 의미한다.

탐색, 정렬, 반전, 삭제, 변환 등이 있다.

위와 같이 3가지 요소로 구성된 것이 C++ STL이라는 것을 학습했고, 대충 개념을 잡게 되었다.

c언어의 표준 함수 호출

• C언어의 라이브러리를 사용하기 위한 헤더 삽입

위와 같이 헤더를 선언하면 C함수의 라이브러리를 C++에서도 사용할 수 있다.

그러나 C언어 스타일로 헤더를 선언하고, 함수를 호출한다고 하더라도 그 자체를 허용한다. 그 이유는 하위 버전과의 호환성(backwards compatibility)를 제공한다.

위와 같은 헤더 삽입과 함수 호출은 허용하는 것이 바로 하위 버전과의 호환성을 제공한다고 한다.

그러나 오버로딩 되는 라이브러리 등의 문제로 모두 호환되는 것은 아니다.

Malloc과 free의 대체 – new와 delete

• C언어에서의 동적 할당

C언어에서 동적 할당의 단점은 할당 크기를 바이트 단위로 직접 명시해주어야 하고, 반환되는 void *에 대해서 적절한 타입 변환이 이루어지고 대입이 이루어져야 한다.

C++에서의 new와 delete 연산자를 사용하면 위의 단점을 모두 커버할 수 있다.

• C++에서의 동적 할당

다음과 같은 형식으로 동적 할당을 행한다.

그리고 다음은 C 스타일의 동적 할당과 C++ 스타일의 동적 할당을 비교한 것인데 완전히 같은 내용이다.

• C++의 클래스의 객체 생성 시 new & delete

객체 생성을 할 때에는 꼭 new 연산자를 이용하여 동적 할당하고, delete 연산자를 이용하여 할당을 해체해야 한다. -> C의 malloc & free 함수로 동적 할당 및 해체를 진행할 경우 생성자 / 소멸자의 호출이 이루어지지 않음.

• 참조자를 통한 힙 영역 참조

참조자를 이용하여 포인터 연산 없이 접근해볼 수 있다.

함수와 변수의 생명주기

• 함수

문제를 해결하는데 앞서 문제를 작은 단위로 나누는 과정에서 그 작은 단위의 문제를 해결하는 하나 이상의 기능을 지닌 부 프로그램.

함수 정의의 기본 틀

1. ‘ 함수_이름 ‘ 에는 말 그대로 함수의 이름을 정의한다.

2. ‘ 출력_타입 ’ 에는 해당 함수가 값을 반환할 경우 반환하는 값의 자료형을 기재한다.
    -> 왜냐하면 함수의 값을 받을 때, 어떤 자료형 변수로 받을지 결정할 수 있어야 하기 때문이다.

3. ‘ 입력_형태 ‘ 에는 함수가 실행될 때 입력 값으로 받는 인자를 기재한다. 여러 타입, 여러 개의 인자를 받을 수 있다.

4. ‘ 함수의 내용 ‘ 에는 함수가 수행할 연산 명령들이 정의 된다.

5. ‘ 출력_타입에_따른_반환_값 ‘ 에는 함수가 종료 하면서 반환하는 값을 기재하는데, 조건문에 의하여 여러 번 기재될 수 있으며 ‘ 출력_타입 ‘ 에 맞춰 값을 반환한다.

함수의 정의와 호출 및 선언

함수의 정의와 호출

<입력 X / 출력 X 인 func 함수의 정의와 호출>

<입력 O / 출력 X 인 func 함수의 정의와 호출>

<입력 X / 출력 O 인 func 함수의 정의와 호출>

<입력 O / 출력 O 인 func 함수의 정의와 호출>

함수의 선언

위와 같이 함수를 main 함수 밑에서 정의할 때, main 함수 내에서 함수의 호출이 정의보다 앞서는 이유로 함수가 존재 하지 않는다는 에러가 발생하는데 이 때 main 함수 상단의 선언을 통해서 정의가 밑에 있음을 컴파일러에게 명시하여 문제를 해결한다.

• 변수의 생명주기

<지역 변수( = 자동 변수 )>

중괄호 내에 일반적인 형태(자료형 + 이름)로 선언 되는 모든 변수

• 해당 지역(해당 변수를 감싼 가장 가까운 중괄호 내의 영역)에서만 유효

• 해당 지역을 벗어나면 자동으로 소멸

• 선언된 이름이 같아도 지역이 다르면 중복 선언이 가능

• 선언 시 메모리의 ‘스택’ 영역에 ‘쌓이는’ 형태로 할당 된다. (LIFO)

• 조건문 혹은 반복문 내에서 선언된 변수 그리고 함수에서의 매개 변수 또한 지역 변수이다.

• 지역 변수는 외부에서 선언된 동일한 이름의 변수를 가리게 된다. -> 변수의 이름을 통해 메모리에 접근 시 해당 지역에서 먼저 찾은 후 지역의 외부에서 찾는다.

• for문이나 while문의 소괄호 내부가 아닌 중괄호 내에서 선언된 변수는 생성과 소멸을 반복한다. -> 반복은 중괄호의 진입과 탈출의 반복이기 때문

<전역 변수>

• 중괄호 내에 선언 되지 않는다.

• 프로그램의 시작과 동시에 메모리 공간에 할당되어 프로그램의 종료 시까지 존재한다.

• 초기화를 직접 하지 않더라도 0으로 자동 초기화 된다.

• 프로그램의 전체 영역 어디서든 접근이 가능하다.

<Static 정적 변수>

• static 지역 변수

지역 변수에 static 키워드를 붙임으로써 생성되는 정적 변수.
선언된 중괄호 내에서만 접근이 가능( 지역 변수의 특성 )
1회 초기화되고(직접 초기화 하지 않을 경우 0), 프로그램 종료 시까지 메모리 공간에 존재( 전역 변수의 특성 )

• static 전역 변수

전역 변수에 static 키워드를 붙임으로써 생성되는 정적 변수.
정적 전역 변수는 파일 외부에서 extern 키워드를 이용한 접근이 불가능함. -> 변수의 접근 범위를 해당 파일로 변경

<Register 변수>

지역 변수에 register 키워드를 붙임으로써 생성되는 변수.

Register로 선언된 변수는 CPU 내에 존재하는 ‘레지스터’ 라는 메모리에 공간이 할당될 ‘확률’이 높다. 레지스터 영역은 작고, 중요한 영역으로 상당히 제한이 있는 메모리 공간이기 때문에 register 키워드를 붙인다고 해서 무조건적으로 레지스터 영역에 할당이 되는 것이 아니다. 컴파일러에게 요청을 하는 명령이다.

전역 변수에 register 키워드를 붙이는 요청은 컴파일러에 의해 거절 된다. 중요한 메모리 영역을 전역 변수로 계속 해서 할당을 시키는 것은 명백한 자원 낭비이기 때문이다.

• 재귀 함수

함수 내에서 자기 자신(함수)을 다시 호출하는 함수.

재귀 함수의 간단한 예이다. 재귀 함수의 필수 구성 요소는 다음과 같다.

1. 빨간색에 해당하는 1번 원의 ‘ 재귀 호출 ‘ -> 자기 자신에서 자신을 다시 호출하는 것(복사본)

2. 파란색에 해당하는 2번 원의 ‘ 탈출 조건 ‘ -> 재귀 구조의 무한 루프에 빠지지 않도록 한다.

참조자(Reference)

• 참조자

참조자란 할당된 메모리 공간에 둘 이상의 이름을 부여하는 것으로 다시 말하면 참조자는 자신이 참조하는 변수를 대신할 수 있는 또 하나의 이름

다음은 참조자를 사용하는 예제이다.

10번 라인에서 & 연산자를 이용하여 참조자(레퍼런스)를 선언하고, 변수 num에 대해서 참조를 진행한다. 참조자 선언과 참조를 마친 후 13번 라인에서 일반 변수 num과 레퍼런스 ref의 주소를 출력해보았을 때 완전히 같은 주소를 출력하는 것을 확인할 수 있는 것으로 미루어 보아, 기존의 대상이 되는 변수에 이름만 부여되는 것임을 확인할 수 있다. 즉, 참조자는 이름을 하나 더 부여하는 별칭인 셈이다.

그리고 하나의 변수에 대해 여러 참조자를 선언하고 참조할 수 있으며, 참조자를 대상으로 참조자를 선언할 수 있다.

9번 라인부터 13번 라인까지 대상 변수에 대한 참조자의 수, 참조자를 대상으로 하는 거듭된 참조까지 가능함을 알 수 있다. 그리고 19번 라인에서 대상 변수 그리고 참조자들의 주소를 출력했을 때 모두 대상 변수의 주소로 같게 나왔음을 확인할 수 있다.

참조자의 잘못된 선언 형태에 대한 간단한 예제이다.

먼저, 10번 라인에서는 참조자를 선언만 하고, 참조를 하지 않은 상태인데 참조자는 선언과 동시에 어떤 대상을 꼭 참조해야만 한다. 그리고 11번 라인에서는 선언과 동시에 참조를 진행했지만 참조의 대상은 참조자의 타입이 맞는 변수가 대상이어야 한다. 마지막 12번 라인에서는 NULL로 선언과 동시에 참조를 하고 있지만 역시 마찬가지로 변수가 대상이 아니기 때문에 참조가 불가능하다. 이와 더불어 한 번 참조가 된 이후에는 참조의 대상 변경이 불가능하다.

참조의 가능 범위는 다음과 같이 크게 3가지가 존재한다.

일반 변수

배열 요소

포인터 변수

• 참조자와 함수

Call-By-Address와 Call-By-Reference 모두 주소 값을 인자로 전달하는 형태의 함수 호출은 뜻하는데, 그 사실 보다는 주소 값을 전달하되, 해당 주소를 이용하여 참조 혹은 값의 변경이 일어났는가를 볼 수 있어야 함. (결국, call-by-address와 call-by-reference 방법은 서로 비슷한 방법이라고 보일 수 있지만 전자는 단지 주소만을 전달하느냐 후자는 주소를 전달하고 참조를 행하느냐를 보는 것인데 전자의 경우는 주소만 전달될 뿐 참조가 일어나지 않기 때문에 call-by-value로 볼 수도 있음 그렇기 때문에 두 용어는 구분이 필요함을 이야기함.)

다음은 참조자를 이용한 swap 함수의 구현이다.

• Const 참조자

참조자를 이용하여 call-by-reference를 구현할 때, 매개 변수에 참조자를 const화 시켜서 넣게 되면 해당 참조자 매개 변수를 이용하여 값의 변경을 허용하지 않겠다 라는 의미를 갖는다.

이러한 의미가 왜 필요한가?

위와 같은 예제를 마주쳤을 때, C언어에서는 num의 값이 바뀌지 않는 call-by-value 방식의 호출이라는 것을 위 예제만 보고도 알 수 있으나, C++언어에서는 참조자의 개념 때문에 call-by-reference인지 call-by-value인지 알 수가 없다. 이를 확인하기 위해서는 함수의 원형을 확인해야 하고 뿐만 아니라 정의까지 확인해야한다. (왜냐하면 참조자로 매개 변수를 선언했을지라도 참조 후 값의 변경이 있는지 없는지는 정의를 확인해야하기 때문이다.) 이러한 불편함을 해소하기 위해서 함수의 원형 선언만 보더라도 const 키워드로 인해 값의 변경이 일어나는지 일어나지 않는지를 확인할 수 있게 해준다. 다음과 같이.

그리고 const 참조자에는 이러한 경우도 있는데,

16번 라인에서 const를 이용한 변수의 상수화로 심볼릭 상수를 선언하였고, 17번 라인에서 ref 참조자로 심볼릭 상수와 참조 관계를 형성한다. 그리고 18번 라인에서 참조자를 통한 값의 변경을 행한다. 기껏 16번 라인에서 상수로 만들었는데 참조자를 통한 값을 변경을 하고 있다. 그러나 이는 허용하지 않는다. 17번 라인 참조 관계를 형성하는 부분에서부터 허용을 하지 않는다 왜냐하면?

C언어 정리에서 언급했듯이 대입 연산자를 기준으로 l-value 와 r-value의 자료형은 완벽하게 같아야 대입이 이루어지는데 현재 17번 라인에서는 l-value의 타입은 int& 이고, r-value의 타입은 const int 이다. 이는 다른 타입이기 때문에 대입에서 오류가 나는 것임.

그래서 위와 같이 맞춰 주어야만 오류가 나지 않는다.

또 const 참조자는 상수를 참조할 수 있는 특징을 가지고 있다. 일반 참조자와 다르게 const 참조자를 이용해서상수와 참조 관계를 형성하려고 하면 상수가 해당 라인이 넘어가면 소멸되는 리터럴 상수가 아닌 임시 변수 형태로 생성되어 그 값을 가지고 있는 형태로 생성된다. 그렇기 때문에 그 임시 변수 공간과 참조 관계를 형성할 수 있는 것이다.

15번 라인에서 50이라는 임시 변수를 생성하고 그 임시 변수의 공간에 ref 이름을 부여한다. 7번 라인과 16번 라인 또한 같은 맥락이다.

• 함수의 출력 타입이 참조형인 경우

위와 같은 함수 정의에서 14번 라인의 경우에는 arg 변수에 대한 새로운 참조 관계가 형성되는 경우이고, 15번 라인에서는 200이라고 하는 값이 반환된 것이고 v에는 값이 저장되는 경우이다.

위와 같은 경우에는 반환 값을 참조가 아닌 일반 자료형으로 지정한 경우인데 이 경우 반환되는 값은 단순히 값만 반환되기 때문에 일반 변수로 값을 리턴 값을 받을 수 있지만, 25번 라인처럼 참조 관계를 형성할 수는 없다 왜냐하면 int& r = 200; 형태와 같은 형태이기 때문이다.

위와 같이 함수 내의 지역 특성을 지니는 지역 변수에 대해서 참조 관계를 형성시켜서는 안된다(왼쪽). 이는 포인터로 지역 변수에 대해서 가리키고 참조하는 것과 다를 것이 없다.(오른쪽).
함수가 종료되면 사라지는 지역적 특성을 지니는 지역 변수를 함수의 외부(함수 종료 상태의 지역)에서 참조한다는 것은 이미 해체되어 없는 공간 혹은 다른 쓰레드 작업에 의해 이미 다른 중요 값으로 채워져 있는 공간을 참조하고 조작할 수 있는 가능성이 있기 때문에 잘못된 것.

이름 공간

• 이름 공간이 존재 등장한 이유?

변수, 함수 등의 이름 충돌을 막기 위함이다.

• 이름 공간

위와 같은 예제에서는 두 함수 모두 수행하는 내용은 다르지만 이름, 매개 변수가 같다는 이유로 오버로딩이 적용되지 않고 에러가 난다. 예제에서는 나타나지 않지만 두 함수 모두 다른 모듈이나 소스에 이미 의존되어 있는 부분이 있기 때문에 이름을 바꾸거나 할 수 없다. 이러한 경우 이름 공간을 이용한다.

위의 예제에서는 각 함수를 A, B라는 이름 공간(namespace) 으로 감싸고, 영역을 구분하였다. 영역을 구분하였기 때문에 함수 중복 문제로 오류가 발생하지 않는다. 그리고 24, 25번 라인에서는 ‘ :: ’ 범위 지정 연산자를 이용하여 이름 공간을 지정하여 그 내부의 함수를 지정하여 호출하는 식으로 함수 호출을 진행함.

• 이름 공간 기반의 함수 선언과 정의 구분

이름 공간에서 동일한 이름 공간 내의 함수 호출 및 변수 참조가 일어날 경우 범위 지정 연산자를 이용하여 이름 공간을 명시할 필요가 없다.

• 이름 공간의 중첩

이름 공간은 중첩이 가능하고, 범위 지정 연산자를 거듭 이용하여 범위를 지정하고 변수나 함수에 접근한다.

• 이름 공간 std

std::cout, std::cin, std::endl 등은 모두 이름 공간 내의 어떤 요소들이었다.

위와 같은 형태로 존재하고 있는 요소들이고, cout/cin/endl 은 추후에 정리.

• using 연산자를 이용한 이름 공간의 명시

위와 같이 이름 공간 전체를 명시하여 이름 공간의 범위 지정 연산을 생략할 수 있다.

위와 같이 이름 공간 내의 특정 요소를 지정하여 이름 공간 범위 지정을 생략할 수 있다.

아래는 이름 공간을 명시 혹은 이름 공간 내의 특정 요소에 이름 공간을 명시하여 범위 지정 연산을 생략한 예를 보여준다.

반복과 분기

• 반복

반복을 명령하는 문장

While문

왼쪽과 같은 형식으로 while문의 중괄호 속 내용을 반복하여 실행하는데 조건이 참인 경우에만 반복 내용을 실행하고, 조건이 거짓이 되는 순간을 꼭 만들어 주어야 한다. 즉, 탈출 조건을 만들어 주어야 하는데 그 탈출 조건은 소괄호 속 조건과 반복 카운터 변수의 증감을 통해 이룰 수 있다.

For문

역할은 while문과 완전히 같지만 형식이 주어져서 더욱 보기 깔끔하다 그러나 코딩의 유연성은 while문에 비해서 조금 떨어진다. for문의 동작 순서는 while문과 완전히 같다.

초기문 -> 조건문 -> 반복 내용 -> 증감문 -> 조건문 -> 반복 내용 -> 증감문 -> ~ -> 조건문 -> for문 종료

위와 같은 순으로 반복한다.

Do-While문

위와 같은 형식으로 반복을 진행하는데, 다른 반복문과 다른 특이한 점은 반복 내용을 한 번은 무조건 실행하는 경우에 사용한다. Do~While 문은 조건과 상관없이 딱 한 번은 무조건 실행하게 되어 있다. 왜냐하면 조건을 밑에서 검사하는 형식이므로.

• 분기

프로그램을 처음부터 끝까지 모두 실행하는 형태가 아닌 프로그램의 흐름을 원하는 형태로 제어하기 위한 구문.

If문

아주 간단하게 소괄호 내의 조건이 만족하면 (참이면) 반복 내용을 실행하고, 만족하지 못하면 중괄호 속에 해당하는 내용은 통째로 실행하지 않고 뛰어 넘는다.

다음과 같이 중괄호의 생략도 가능한데 이러한 경우는 반복할 문장이 한 줄일 때만 가능하다.

다음과 같이 else 를 이용하면 위의 if 조건을 만족하지 않은 모든 경우를 다 받아들이는 구문이 존재한다. 여기서 기억해야하는 중요한 포인트는 else는 위의 if 조건에 부합한 모든 경우들을 수용하기 때문에 따로 조건 검사를 하지 않는다는 것이다. 위와 같은 포인트를 잘 기억하고 다음을 보도록 하자.

다음과 같이 여러 조건을 if문으로 채우는 경우에는 모든 조건을 하나하나 검사하게 된다. 예를 들어 사칙 연산을 택하는 프로그램이 존재할 때 더하기, 빼기, 곱하기, 나누기의 총 네 개의 연산이 존재하지만 결국 선택되는 연산은 하나이다. 그러므로 한 가지 연산이 선택되었을 때에는 나머지 연산에 대해서는 확인하는 작업은 필요로 하지 않다. 다만, if문으로 제시되는 조건들이 모두 연관이 있는 하나의 주제에서의 선택에 대한 조건임을 전제로 한다.

왼쪽의 경우가 하나의 주제에 대해서 선택을 할 때, 모든 조건을 다 검사하는 소스이고, 오른쪽의 경우는 어떤 조건을 만족하게 될 경우 그 조건보다 아래에 오는 조건들은 자연스럽게 무시하는 경우의 소스이다. 이것이 가능한 이유는 위에서 언급한 두 가지 조건으로 인해 가능해진다.

1. 실행할 문장이 한 줄일 경우에는 중괄호를 생략할 수 있다.

2. else는 위의 라인의 if 조건에 부합한 모든 경우들을 수용하기 때문에 따로 조건 검사를 하지 않는다

이 두 전제에 의해서 else if 라는 문장이 생긴다.

원래 형태의 소스이고, 이 부분에서 두 가지 전제를 적용하여 중괄호를 없애게 되면 else if 구문을 확인할 수 있다. else 바로 밑의 조건문은 모두 유기적으로 연관되어 있기 때문에 if 문과 함께 한 줄로 취급하는 것이다. 그렇기 때문에 else의 중괄호를 생략할 수 있는 것이다.

결국, if, else if, else 구문은 if와 else 구문을 중첩시킨 형태에 지나지 않는다.

조건 연산자(삼항 연산자)

If 조건문을 대체할 수 있는 조건 연산자이다. 다음과 같은 형식을 지니고 ‘?’, ‘:’ 두 개의 연산자와 세 개의 피연산자를 이용하여 조건에 대한 결과 반환을 수행한다.

다음은 위와 따른 예제이다.

Switch~Case문

스위치~케이스문은 if문과 마찬가지로 분기를 통한 프로그램의 흐름을 제어해주는 방법 중 하나인데 if문과는 구조가 많이 다르고 조금은 제한적인 형태로 구성되어 있지만 간결하고 가독성이 좋아진다는 장점이 있다.

switch 키워드 옆 소괄호에는 분기 선택에 대한 정보가 담겨 있는 ‘정수형’ 변수가 인자로 전달되어야 한다. 그리고 그 전달된 값을 case 별로 나눈 것이 11번, 14번, 17번 라인이다. 여기서 짚어야 할 포인트는 분기의 조건으로 범위가 올 수 없고, 떨어지는 값의 형태로 분기가 일어난다는 것이다. 그리고 해당 case부터 break; 부분 사이의 실행 내용을 실행한다. break는 switch문 하나를 탈출하는 분기이며 반복문과는 관련이 없다. 만약 break를 생략하게 되면 전달되어온 인자의 값과는 상관없이 다음 case 영역의 break문 전까지 모조리 실행하게 된다. 그리고 마지막으로 default는 위에서 정의된 모든 case 분기에 빠지지 못한 경우는 모두 이 default 영역으로 분기된다. else와 같은 역할이라고 보면 된다.

goto문

레이블을 이용하여 분기를 제어하는 형태이다.

‘ 레이블: ’ 형식으로 레이블을 마킹한 후, ‘ goto 마킹한_레이블명; ‘ 명령어를 통해 프로그램의 흐름을 마킹한 레이블 라인으로 변경한다.

이 goto문은 절차지향의 패러다임에 위배되는데 그 이유는 위에서 아래로의 순차적인 실행이 아니라, 뒤죽박죽 어느 라인의 위치이든 간에 상관없이 흐름 변경이 가능하다. 즉, 프로그램의 자연스러운 흐름을 방해하기 때문이다.

Continue & Break문

먼저, continue문이다.

위와 같은 형식을 갖추며 continue를 감싸고 있는 가장 가까운 반복문의 조건 검사 위치로 이동한다. 단순히 반복문의 상단으로 프로그램의 흐름이 이동하는 것이 아니라, 조건을 찾아가는 것이다. 즉, do~while문에서는 위로 가는 것이 아닌 하단의 조건 위치로 프로그램의 흐름이 변경된다. 그리고 for문에서 continue문을 실행하게 될 경우에는 조건문을 실행하기 이전에 증감문 또한 실행한 뒤 조건문을 실행하러 상단으로 위치한다.

다음은 break문이다.

위와 같은 형식을 갖추며 break를 감싸고 있는 가장 가까운 반복문 하나를 탈출한다. 중첩된 반복문에서도 마찬가지로 break를 감싸고 있는 가장 가까운 반복문 ‘1개’만 탈출한다.

지난 포스팅 때, 재귀는 믿음이 졸라 중요하다고 했다. 이번에도 마찬가지다.

그 전에 재귀를 공부할 때, 써야하는 경우에 대한 추가적인 기록이 필요할 것 같아서 먼저 기록한다.

재귀가 필요한 경우

재귀가 필요한 경우는 다음과 같다.

탈출 조건이 명확하고, 같은 작업이 계속해서 반복되는 경우.

피보나찌 수열에서는 n-2항과 n-1 항이 더해지는 부분이 반복된다.

Fibonacci(5) 이면 Fibonacci(4) + Fibonacci(3) 인데 Fibonacci(4)에도 Fibonacci(3)에도 n-2항과 n-1항이 더해지는 부분이 필요하기 때문에 반복이 되고, 이를 재귀로 구현했던 것이다.

이번 포스팅에서 구현해 볼 이진 탐색에서 또한 마찬가지다. 

가운데 값을 구한 후 비교 -> 범위 재설정 

이 작업이 반복되기 때문이다. 탈출 조건의 명확성은 말할 것도 없고 말이다.

이진 탐색에서도 믿음이 필요한가?

물론이다. 필요하다. 위에서 제시한 재귀가 필요한 경우와 믿음이 존재한다면 재귀 함수를 마음 놓고 신경도 안 쓰고 사용해도 된다.

재귀란 무엇인가?

피보나찌 수열 구하기이다. 재귀로 구해볼 것이다. 재귀는 매우 특이한 방법이 아닐 수 없다.

A라는 함수가 있을 때, A를 열심히 실행하는 도중에! 그것도 A가 미처 다 끝나지도 않은 채로 다시 A를 실행한다. 

이렇게 되면 와 진짜 너무 복잡한데, 또 두 번째 실행된 A안에서 또 A가 호출하면 와 진짜 머리 터진다.

윤성우 선생님? 강사님? 교수님? 의 자료 구조에서 공부한 파트를 정리하게 되었다.

그냥 재귀를 하면 심심하니까 피보나찌 수열을 통해서 재귀 함수를 작성해보았다. 복잡할 수 있으므로 시간의 흐름에 따라 스텝을 밟을 것이다.

피보나찌 수열의 재귀적 구현

먼저, 다음은 피보나찌 수열이다.

0,   1,   1,   2,   3,   5,   8,   13,   ...

0번째 항과 1번째 항은 무조건, 지구가 멸망하지 않는 이상 0과 1로 각각 주어진다.(멸망하면 수학을 풀 필요가 없다) 그렇다면 2번째 항부터는 어떻구 구하는가?

• 2번째 항을 구하는 방법 : 0번째 항의 값과 1번째 항의 값을 더한다.
• 3번째 항을 구하는 방법 : 1번째 항의 값과 2번째 항의 값을 더한다.
• 4번째 항을 구하는 방법 : 2번째 항의 값과 3번째 항의 값을 더한다. (ㄱ)
• n번째 항을 구하는 방법 : n-2 번째 항의 값과 n-1 번째 항의 값을 더한다. ( 일반화 ) (ㄴ)

일단, (ㄱ) 까지의 상황을 코드로 정리해보겠다.

그렇다. 무식하다. 근데 이게 좀 쩌는 것이 무어냐면 ㅋㅋ,

• Fibonacci(4); 의 결과 : 3
• Fibonacci(3); 의 결과 : 2 
• Fibonacci(2); 의 결과 : 1

함수의 결과가 중요하지 않다. Fibonacci 함수의 본질을 알려준다. Fibonacci 함수의 본질은 다음과 같다.

Fibonacci 함수에 원하는 항의 인덱스 값을 넣으면 해당 인덱스 항의 값을 구해줘요!

이게 진짜 개중요하다. 우리는 앞으로 만들 우리의 Fibonacci 함수를 믿어야 한다. 우리는 Fibonacci 함수의 인자로 원하는 항의 인덱스 값을 넣으면 해당 인덱스 항의 값을 내어준다는 사실을 믿어야한다. 믿음이다. 재귀 함수 루틴이 들어간다고 해서 이러한 사실이 부정인가? 아니다. 

위의 믿음을 가지고 특정 항을 생각해보자. 특정 항은 예를 들어 5번째 항의 값을 구한다고 생각하자.

Fibonacci(5) = Fibonacci(4) + Fibonacci(3);

재귀를 생각하지 말라. 믿음이 있어야한다.
Fibonacci(4)는 4번째 항의 값을 리턴할 것이라는 믿음.
Fibonacci(3)은 3번째 항의 값을 리턴할 것이라는 믿음.

이런 믿음을 바탕으로 (ㄴ)까지의 상황으로 아래와 같이 구현해보았다.

그렇다면, 실제로 어떻게 동작을 해보는지 재귀의 경우를 그려볼까?

피보나치 수열의 재귀적 구현의 동작 원리

그만 알아보자

이진 탐색을 구현해보았다.

이진 탐색에 대해 간단하게 기록하기 전에 이진 탐색의 전제 조건에 대해서 기록을 먼저 해보겠다.

이진 탐색의 전제 조건

• 이진 탐색은 오름차순이든 내림차순이든 관계없이 '정렬'이 되어있는 연속된 배열 자료구조에서 적용된다.

이러한 전제를 갖는 자료구조를 대상으로 탐색을 진행하는 것이 이진 탐색이다. 그렇다면 왜 이진 탐색은 저런 전제를 갖나?
그 해답은 이진 탐색의 정의에 있다.

이진 탐색이란?

타겟을 탐색할 때, 전체 자료구조의 (1)최대한 가운데 위치하는 값과 타겟을 (2)비교하여 탐색의 범위를 비교한 가운데 값을 기준으로 왼쪽과 오른쪽 중 하나로 탐색의 (3)범위를 좁히고 다시 좁혀진 범위에서 최대한 가운데 값을 다시 비교하고 탐색의 범위 결정을 반복하여 타겟을 탐색하는 알고리즘이다.

이진 탐색은 반복이 들어간다. (4)반복이 들어간다는 의미는 탈출 조건이 필요하다는 뜻이다.

이 탈출 조건은 매우 당연하고 자연스럽다.

허나, 이 이유를 알기 전에 범위를 잡는다는 개념을 알아야 한다. 범위를 잡는 것은 여러 케이스들이 있을테지만 선형(배열) 자료 구조에서의 범위를 잡는다는 행위에 대해서 적어보겠다.

탐색할 범위를 잡는다는 것은 시작 인덱스와 끝 인덱스를 잡는 것이다. 쉽게 말해서 시작과 끝을 잡아야한다. 배열에서 시작과 끝을 잡는다는 의미는 시작 인덱스 값과 끝 인덱스 값을 잡는다는 것이다.

자, 그러면 세 가지의 경우가 있다.

• 시작 인덱스 < 끝 인덱스
  : 정말 당연한 것이다. 탐색할 범위의 양 시작과 끝을 잡고 있다고 보면 된다.
• 시작 인덱스 == 끝 인덱스
  : 이런 경우가 나올 수 있을까? 나올 수 있다. 시작 인덱스이자 끝 인덱스에 위치한 값이 타겟인 경우다. 운이 안 좋은 가장 최악의 경우인 것이다. 어떻게 이렇게 제일 끝에 나올 수 있어? 재수 없단 말이지! 이런 뉘앙스의 최악의 경우를 뜻하고, 이런 경우까지 고려하여 알고리즘의 성능 평가를 시행한다 실제로.
• 시작 인덱스 > 끝 인덱스
  : 이런 경우가 가능할까? 알고리즘이고 말고를 떠나서 글자 자체만 보더라도 불가능하다. 고로, 탈출 조건이 된다. 이 경우는 해당 배열 자료구조에 타겟에 해당하는 값이 없기 때문에 발생하는 경우이다. 시작 인덱스와 끝 인덱스가 같은 바로 위의 경우에도 타겟이 검출되지 않으면 발생하는 경우이고, 이 경우에는 조건 제어를 통해 반복을 탈출해야한다. 왜냐고? 배열에 타겟이 없으니까!

자 그렇다면 구현하는데에 생각하는 순서를 좀 정리해본 것이 위 본문에서의 괄호 안의 숫자들이다.

• (1)최대한 가운데 위치하는 값(을 구한다)
• (2)비교
• (3)범위를 좁힌다(결정한다)
• (4) 탈출 조건

위 순서에 해당하는 부분들을 주석으로 표시해봤다.