1. 개요

조합, 중복조합, 순열, 중복순열 알고리즘은 모든 경우를 나열하는 알고리즘이다.


모든 경우를 나열하기에 작은 범위의 문제에 대해서 완전 탐색 알고리즘에 적합하다.

또한 각각의 경우에 해당하는 모든 데이터 Set을 가지고 있기 때문에 조건에 만족하는 모든 경우를 출력할 때 필요하다.


또는 앞서 포스팅한 knapsack problem(배낭 문제)처럼 각각의 가치와 무게에 대한 경우에 따라서

문제가 설정한 최고 효율적인 방법이나 값을 찾는데 도움이 된다.


이 포스팅에서는 현재 각각의 뼈대가 알고리즘이 흩어져있는데, 이를 복습 겸 코드 작성하여 모든 뼈대를 종합해서 정리했다.


재귀 방식으로 움직이기 때문에 큰 문제는 해결하지 못한다.


만약 문제가 작고, 완전 탐색을 한다고 하여도 성능에 크게 문제가 없고, 또한 각각의 경우를 출력해야 한다면 이 

나열하기 알고리즘의 대표인 '조합, 중복조합, 순열, 중복순열' 알고리즘을 잘 고려하자.


조합이나 중복조합 그리고 중복순열 알고리즘은 쉽게 직관적으로 코드를 보면 이해할 수 있지만,

순열 알고리즘만큼은 조금 머릿속에서 쉽게 쉽게 이해가 안갔다.


오직 순열 알고리즘만 미리 초기화한 배열을 사용한다.

또한 Swap 함수나 또는 사전 순으로 출력을 위한 Right_Rotate()와 Left_Rotate()를 사용한다.

즉, 미리 입력해둔 배열 속 데이터를 이리저리 순서만 바꿔서 출력하고 다시 원래 상태로 되돌린다.


순열 알고리즘의 재귀 방법은 이렇다.


현재 단계에서, 배열의 첫 번째 원소, 두 번째 원소, 세 번째 원소 ... 마지막 원소를 맨 처음 원소와 교환한 후(처음만 결정)

다음 단계에서 나머지 뒷 부분의 순열 알고리즘을 작성한다.


예시)

-> 0 결정 - 1, 2의 순열

0, 1 2의 순열      -> 1 결정 - 0, 2의 순열 

                       -> 2 결정 - 0, 1의 순열

2. 문제

조합, 중복조합, 순열, 중복순열 뼈대 알고리즘을 모두 작성하시오.


3. 코드 및 출력

3-1) 조합


3-2) 중복조합


3-3) 순열


3-4) 중복순열


3-5) 메인


3-6) m: 3, n: 2 출력


3-7) m: 3, n: 3 출력



4. 정리

모든 경우를 다 나열하여 알고싶을 때나 또는 작은 부분에 대한 완전 탐색을 위할 때 이 알고리즘을 사용한다.

완전 탐색 알고리즘은 모든 알고리즘의 기본이니까 언제나 시작은 이 나열 알고리즘을 적용할 수 있는지 검사부터 하자.


계속 공부!



클래스에 대한 얘기를 하면 빠지지 않고 등장하는 것이 바로 상속이다.


이 상속 관계는 객체지향 프로그래밍에서 무척 중요하다.


객체지향 프로그래밍은 절차형 프로그래밍의 한계점에 의해 탄생한 프로그래밍 기법이다.

객체를 통해서 현 실세계를 표현하는 프로그래밍으로 현재 대부분 모든 프로그래밍 기법이다.


물론 객체지향 프로그래밍이라고 해서 모든 것을 표현하진 못한다고 한다. 특히 최근에 객체지향 프로그래밍의 한계점으로

새로운 프로그래밍 기법이 연구되고 있고 속속 등장하고 있다고는 하지만 이 얘기는 여기서 마무리하고 다시 본 이야기로

돌아가서 이런 객체지향 프로그래밍에서 클래스란 모두가 알다시피 어떤 실체의 틀을 말한다. 그리고 그 실체의 틀에 

필요한 정보를 넣어서 완성시킨 형상이 바로 객체다.


하지만 이 객체들은 진화한다. 현실 세계에도 계속 새로운 물건이 등장하고 그 물건을 개선하여 다시 새롭게 탄생한다.

이러한 현실 세계를 나타내기 위하여 컴퓨터로 나타내는 객체지향 세계에서도 진화라는 개념이 등장해야 했다.


그래서 나온 것이 상속이다.


글이 길어졌다. 이제부턴 짧게 작성해야겠다.


상속은 기존 것을 받아서 프로그래머 입맛대로 바꾸는 것을 말한다.

슈퍼 주전자를 만들고 싶다. 이 때, 슈퍼 주전자를 완전히 무에서 만들어내는 것보다 기존의 주전자에서 만들어내는게

훨씬 더 비용적으로 편하고 좋다. 그렇기에 기존 주전자를 받아서 바꾸고 싶거나 버리거나 추가할 부분을 추가하여 변형한다.


만약 주전자의 뚜껑을 열 때, 기존의 주전자는 사람의 손으로 직접 열지만 슈퍼 주전자는 스위치를 통해 연다고 하자.

이렇게 새롭게 변형이 일어나는 부분을 프로그래밍 코드로 표현하는 방법을 '오버라이딩'이라고 한다.


한 마디로 부모 클래스 메서드를 자식이 필요에 맞게 조정하는 것이다.


단!! 반환 타입, 이름, 매개변수 타입과 개수까지 모두 같아야 한다.

오버라이딩과 오버로딩은 엄연히 구분되어 있다.


아래 코드의 Move()가 바로 오버라이딩 대상이다.



만약 위의 클래스에서 다음과 같은 코드를 수행한다면 그 결과는 어떻게 될까?


다음은 위 코드의 결과화면이다.


정상적으로 상속되어서 오버라이딩된 것을 볼 수 있다. 하지만 !!!


하지만 이 방법은 큰 문제가 있다.

단순히 저 객체만을 사용하려 한다면 발생되지 않을 문제이지만, Shape 클래스에서 상속받은 자식 클래스들이 둘 이상일

경우에 발생하는 문제로 다음과 같은 함수를 호출하는데 발생한다.

이 함수는 Shape 클래스 타입을 파라메터로 받기에 Shape 클래스를 상속받은 모든 자식 클래스는 이 함수에 접근 가능하다. 

하지만, 

다음과 같은 코드를 보자.

이 코드의 결과는 무엇일까?

Triangle 객체를 생성해서 넣었기에 출력 결과는 Triange Move()가 나올 것 같지만, 결과는 다음과 같다.


실제 객체는 Triangle이지만 함수의 파라미터 타입으로 인해 함수는 Triangle의 부모 클래스인 Shape 객체로 인식하게 된다.


그럼 어떻게하면 Shape 타입이지만 Triange 객체에 의도대로 접근할 수 있을까?

바로 클래스 Upcasting을 활용하면 된다.


Upcasting을 활용하면 Shape 클래스를 상속받은 모든 클래스들은 이 함수를 사용할 수 있는 인터페이스 함수로 바꿀 수 있다.

그 방법은 Triangle 객체를 다음과 같이 생성한다.


다음은 위 코드의 출력 결과이다.


???

이게 무슨일이람? 

무언가 이상하다.


첫 번째로 Shape Move()가 아닌 Triangle Move()가 출력됐어야 했고, 그리고 부모 클래스인 Shape의 소멸자가 수행되기 전에

Triangle의 소멸자가 수행되어야 했는데 그러지 않는다. 이와같은 현상으로 인해 자식 클래스인 Triangle 객체가 해제되지

않고 남아있기에 메모리 누수 현상까지 발생한다.


바로 이 부분이 이번 포스팅의 핵심이다. 잘 기억하자. 또 그렇게 벌벌 거리지 않게.


 

위 문제는 만약 언어가 Java라면 큰 문제가 없겠지만, 언어가 C++이기에 발생하는 문제점이다.

가상테이블과 객체간의 연결 관계에 대해 깊은 이해를 위한다면 정확히 찾아보는 것이 좋다. 여긴 그냥 관념적인 내용이다.


컴파일 과정에서 현재 생성된 객체의 메서드가 부모 클래스의 메서드인지 자식 클래스의 메서드인지 판단하게 되는데,

만약 Java라면 모든 연결을 동적 바인딩 방식으로 진행하기에 사용자의 의도대로 Triangle 객체를 생성하고 Move() 메서드를

수행하면 그 결과는 "Triangle Move()" 결과나 나온다.


하지만 C++언어는 virtual 키워드를 통해 객체와 메서드간의 연결을 동적 바인딩을 명시해주지 않으면 위의 코드에서는

Triangle 객체를 생성했지만 실제로 Move() 메서드의 결과는 "Shape Move()"이다. 

그 이유는 virtual 키워드를 입력하지 않았기 때문에 컴파일러가 부모와 자식의 오버라이딩 관계를 정적으로 바인딩했기

때문에 발생한다. 그래서 동적 생성인 new 연산자로 생성했다고 해서 동적 바인딩이 이루어지지 않고, 이미 정적 바인딩이

진행되었기에 함수 호출 시 원하는 출력이 나타나지 않는다.


만약 정상적인 출력을 원한다면 virtual 키워드를 부모 클래스의 오버라이딩 함수 앞에 넣어주면 된다.


수정된 클래스이다.

수정된 클래스의 출력 화면이다.


의도대로 Shape Move()가 아닌 Triangle Move()가 출력되었다.

하지만 여전히 Triangle 객체가 해제되진 않고 있어 메모리 누수 현상이 계속된다.

이를 어떻게 해결해야할까?


정답은 똑같이 부모의 소멸자 앞에 virtual 키워드를 삽입하면된다.

그러면 소멸자도 똑같이 동적 바인딩이 이루어지면서 원하는 의도대로 프로그램이 진행된다.


다음은 최종적으로 수정된 클래스이다.

위 코드의 출력 결과이다.


정상적으로 함수 실행이 완료되었고, 객체의 소멸까지 메모리 누수 현상없이 잘 해결되었다.


이처럼 Upcasting을 활용하면 파라미터로 부모 클래스 타입을 가지지만, 자식 객체들이 접근하여 그 함수를 활용할 수 있다.


말이 어려우니까 한 마디로,

만약 Upcasting을 하면 객체지향의 다형성을 제대로 활용할 수 있다. 아래의 코드를 보면 명확히 이해 가능하다.


마지막 코드

출력


play() 함수를 각각의 객체 타입에 맞게 파라미터를 오버로딩 할 필요없이, 상속 관계라면 하나의 함수로 접근 가능하다.

이것이 Upcasting을 사용하는 가장 대표적인 이유다.


아주 미약한 이유로는 Upcasting된 코드를 보면, 상속 관계를 한 눈에 알아볼 수 있어 가독성에 아~~~~주 조금 도움된다.


그리고 Downcasting이란 Upcasting의 반대의 의미이며 절대로 생성할 때 사용하면 안된다. 

애초에 visual studio라면 오류를 내보낸다.

왜냐하면 다음과 같은 코드가 있다.


Triangle* t = new Shape();


기본적으로 Triangle 클래스가 Shape 클래스의 자식 클래스이기에 필요로 하는 정보량이 훨씬 많기에 그만큼 생성해야 한다.

하지만 Shape() 객체로 생성하면 Triangle 클래스가 필요로 하는 정보량을 모두 생성할 수 없다.

그렇기에 Downcasting은 생성할 때, 쓸 수 없다.


단지 Upcating한 객체를 원래대로 되돌릴 때 사용할 뿐이다.


마지막으로 이와같은 Upcasting, Downcasting의 존재는 편리하지만 잘못사용하면 정보의 손실이 발생하는 위험한 방법이다.

그렇기에 이를 보완하기 위한 Dynamic Casting이 존재하지만, 이에 대한 내용은 다음에 알아볼 것.



다시는 이 내용몰라서 당황하지 않게 정말 평생의 미련이 될 뻔했다. 바보야.

솔직하지 않았더라면.



1. 개요

몇 일 면접과 테스트를 본다고 알고리즘 코드를 짜지 못했다.

그러니 바로 공부한 것들이 가물가물 해졌다.


그래서 앞서 재귀 방식으로 풀었던 '금액 맞추기 알고리즘'을 조합 알고리즘을 활용하여

모든 경우를 출력하는 알고리즘을 작성하면서 복습하기로 했다.


똑같은 조합 재귀 흐름에 단지 조건만 변화한다.

역시나 똑같은 현재의 경우를 조사하고, 조사하지않고라는 두 가지 흐름뿐이다.


계속 까먹지 않도록 알고리즘 공부하자.


오늘 칼럼을 읽으면서 배운 알고리즘 공부법.


1. 생각을 많이 하는 것.

2. 문제에 집착않고 빠르게 포기할 수 있는 것.

3. 다른 사람의 도움을 받는 것.


이 중에서 특히 2번째 방식이 와닿았다.


알고리즘 문제는 최대 1시간만을 생각해야 한다. 1시간동안 더이상 답이 떠오르지 않으면 2가지 방법이 있다. 첫 번째는 바로

인터넷 검색을 하거나 다른 사람에게 도움받는 것이고, 두 번째는 며칠 후에 그 문제를 보고 다시 생각을 해보고 모르겠으면

찾는 것이다.


알고리즘 문제풀이에서 가장 중요한 것은 '스스로 해결하는 능력'이 아니라 '문제를 풀이하는 능력'이라는 것.

즉, 어떻게 해서든 문제를 풀어내는 것이 중요하지 내 스스로 학구열에 불타서 풀었다고 좋은게 아니라는 것이다.


사실 알고리즘 문제풀이는 알고리즘을 알아야 풀고, 모르면 풀기가 굉장히 어렵다. 알고리즘은 매우 많은데 그걸 모두 스스로

만들어서 하려고 한다면 그건 별로 효과가 없다.


그렇다고 알고리즘 문제풀이를 암기하라는 것은 아니다. 꾸준히 계속 반복학습을 하면서 알고리즘 문제 풀이를 하면서 그 

문제를 풀어나가는 '생각의 과정'을 배우는 것이 가장 중요하다.


2. 문제

주어진 지폐 1000원, 5000원, 10000원, 50000원으로 입력한 금액을 맞추는 모든 경우를 출력하고,

각각의 경우를 이루는 지폐들을 모두 출력하시오. (입력 금액의 단위는 반드시 1000원 단위)


3. 코드 및 출력 

3-1) 코드


3-2) 출력


4. 정리

뭔가 요즘 알고리즘 풀이 능력에 대한 과도기 같다. 조금만 더 열심히 꾸준히 해낸다면 한 단계 레벨업을 할 수 있을 것

같은 느낌이다. 하지만 그 벽을 넘는 것이 어떤 것인지 모르겠다. 앞으로 나가서 계속 배우기보다 과거에 배웠던 것을

다시 복습하는게 더 중요한 것 같다.


그리고 오늘 어쩌면 첫 번째 결과가 나올지도 모른다. 

두렵다. 정말.

또 와르르 무너지는 그 심경을 다시 느끼게 될까봐.

아니야 난 돼. 라고 항상 자신감에 넘쳤던 예전이 신기하다.

어떻게 그렇게 무대포로 거침없이 나아갈 수 있었는지.

분명 과거보다 더 발전하고 더 많이 알고 더 능숙해졌는데, 알아갈수록 두려움은 계속 커진다.

이래서 모르면 용감하다는 말이 진짜 절실히 느껴지는 때다.


과연 어떨까?

나는 앞으로 갈 수 있을까? 아니면 한 번더 미뤄질까?

분명 그 자리에서만큼은 아쉬움과 미련이 없을정도로 잘 해냈다고 생각했는데, 그 느낌은 과연 진짜였을까.

요동친다.


된다 된다 된다 된다.

그래 된다.



흔히 KB, MB, GB, TB (킬로바이트, 메가바이트, 기가바이트, 테라바이트)라고 알고있었다.

하지만 이번에 KiB, MiB, GiB, TiB란 개념을 접했다.


무척 당황했다.


아니 요즘 새로운 바이트의 크기인가?


저 가운데의 i의 정체는 뭐지?


그래서 찾아봤다.


MiB를 예를들면, 메가 이진 바이트(Mega Binary Byte)를 뜻한다.

즉, 메가바이트의 단위인 1,000,000 Byte는 메비바이트로는 2^20, 즉 1,048,576 Byte이다.

거의 크기가 비슷하다. 하지만 왜 메가바이트를 안쓰고 이런 새로운 개념이 탄생한 이유는

킬로, 메가, 기가, 테라 바이트들은 10진수 기반이다.


그렇기에 사람에겐 익숙하지만 이진수를 기반으로 하는 컴퓨터에겐 무척 난해하다.

그렇기에 두 Byte의 단위가 비슷하다고는 하지만 컴퓨터가 때때론 몇몇 경우에서 착오를 일으키게 하는 대표적인 예가된다.

이를테면 저장장치의 빈 공간을 아주 정확히 파악해야할 때같은 경우이다.


그래서 IEEE와 CIPM에 의해서 이진 바이트가 보급되었고, 컴퓨터에서의 Byte 단위 수를 일컫는다.


1024(2^10) KiB는 1 MiB와 같고


1024(2^10) MiB는 1 GiB와 같고

1024(2^10) GiB는 1 TiB와 같다.



이 개념을 잘 알아두고 혼동하지 말자.



+ Recent posts