조합은 순서를 고려하지 않습니다.

순서는 고려하지 않고 다양하게 몇 개를 뽑을 지에 집중합니다.

 

출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=vollollov&logNo=220915481071

 

조합을 구현하는 테크닉은 3가지가 있습니다.

 

중첩 반복문

n명 중 r개를 선택하는 방법일 때, r의 수가 3개 이하라면 반복문으로 빠르고 쉽게 구현할 수 있습니다.

for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
    		for (int k = j + 1; k < n; k++) {
            	}
    	}
}
next_permutation 을 이용하자.

순열의 특징을 가져와 1은 애들이 선택됐다고 보면 되고, 0은 선택받지 못한 애들이 됩니다.

즉 5C2 라면 chk 배열을 {0, 0, 0, 1, 1}이라고 두고, 1일 때에만 출력하면 됩니다.

int main()
{
	vector<int> input = { 3,5,1,7,9 };
	vector<int> chk = { 0,0,0,1,1 };
	do
	{
		for (int i = 0; i < chk.size(); i++)
		{
			if (chk[i] == 1)
			{
				cout << input[i] << ' ';
			}
		}
		cout << '\n';
	} while (next_permutation(chk.begin(), chk.end()));
}

7 9
1 9
1 7
5 9
5 7
5 1
3 9
3 7
3 1
3 5
재귀 구현

조합이라는 것도 즉, 그 현재 순간에 내가 하나를 선택하는 방법입니다.

따라서 그 순간 마다 하나를 pick 하는 과정이 동일하기 때문에 재귀 방법으로 구현할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 5C2 구하기 (조합)
int n = 5, k = 2;
vector<int> v = { 3,5,1,7,9 };

void combi(int start, vector<int>& picked)
{
	if (picked.size() == k)
	{
		for (int it : picked) cout << it << ' ';
		cout << '\n';
		return;
	}

	for (int i = start + 1; i < n; i++)
	{
		picked.push_back(v[i]);
		combi(i, picked);
		picked.pop_back();
	}
}

int main()
{
	vector<int> picked;
	combi(-1, picked);
}

재귀 방법이 처음에는 이상한 구조라고 생각되지만, 쉽게 현재 구간에서 나는 어떤 선택을 할 것인지를 결정해 주면 됩니다.

동시에 기저사례(종료조건)은 nCr 일 때 이미 r개를 뽑았다면 그때를 출력하고 빠져나가면 됩니다.

개발을 하다 보면 정말 많이 사용하는 것이 바로 문자열입니다. 보통 문자열을 표현할 때에는 정말 순수하게 문자열만 표현할 수도 있지만, 간혹 숫자와 같이 작성하거나 다른 특수 기호와 함께 사용되어야 할 때에도 많이 존재하는데요.

C#에서는 조금 더 편리한 기능을 제공하는 보간 문자열에 대해서 알아보고자 합니다.

 

보간 문자열?

이름이 되게 어색하게 들릴 수 있지만 C# 6.0에 도입된 기능입니다.

제일 좋은 것은 바로 코드 가독성이 대폭 향상됩니다. 코드 가독성이 향상되었다는 것은 미연에 개발자의 실수를 줄이고 조금 더 복잡한 문제에 집중할 수 있게 된다는 뜻도 있습니다.

 

기존에 널리 사용되었던 string.Format() 또한 문자열 변환 과정을 잘 수행하지만, 생성된 문자열을 직접 출력해보고 올바른 형태인지를 눈으로 직접 확인하기 전까지는 코드를 제대로 작성했는지를 쉽게 판별하기가 어렵습니다.

 string format = "{0} money";
 Console.WriteLine(string.Format(format, 10));

포맷 문자열과 인자 리스트를 분리해서 전달하는 구조라 정확하게 포맷 문자열에 나타낸 인자의 개수와 실제로 전달되는 인자의 개수가 정확히 일치하는지 여부는 따로 확인해주지 않습니다. 자칫 실수로 이어져 필요한 인자를 누락하면 런타임에서 예외가 발생합니다.

 

저희 회사 프로젝트에서도 이러한 포맷팅 형식을 많이 사용하는데요.

간단한 포맷팅 형식이나 구조라면 상관없지만 {0} 와 같은 인자를 넘기는 횟수가 4개 이상 넘어가게 되면 이게 어떤 거고 그런지 파악하는 시간도 길어질 뿐더러 코드도 길어져 확인이 조금 더뎌지는 경우도 있습니다. ㅎㅎ(나쁘다는 것은 아닙니다.)

 

보간 문자열의 사용방법은 문자열 앞에 $를 붙이면 끝납니다. 그리고 문자열로 변경할 표현식은 { } 중괄호 내에 두면 됩니다.

Console.WriteLine($"{10} money");

엄청난 코드 가독성을 보여줍니다. 바로 문자열에 그 숫자가 넣어져 보여질 것을 인식할 만큼 빠르게 대입되는 것이 눈에 보이며, 결과 예측도 쉽습니다.

 

다만 주의할 점이 있습니다.

Console.WriteLine($"The value of pi is {Math.PI}");

문자열 보간 기능을 사용하더라도 실제 C# 컴파일러는 param을 이용해서 object 배열을 전달하는 기존 포맷팅 함수를 호출하도록 코드를 생성하게 됩니다.

Math.PI는 double 이므로 값 타입인데요. 이를 object 타입으로 변경하려면 박싱을 수행해야 합니다. 이러한 이유로 이 같은 코드를 너무 자주 사용한다거나 루프 내에서 사용하게 된다면 성능에 좋지 않은 영향을 미칠 수 있게 됩니다.

 

전달할 인자를 사전에 문자열로 변경한다면? 값 타입이 박싱되는 것을 회피할 수 있습니다.

Console.WriteLine($"The value of pi is {Math.PI.ToString()}"); // 3.141592653589793

기본적으로 제공되는 ToString() 메서드가 반환하는 문자열이 썩 유용하지 않은 경우가 있는데 이 경우 문자열을 어떻게 포맷팅 할 것인지를 표현하기 위해서 추가적으로 인자를 전달할 수 있습니다.

Console.WriteLine($"The value of pi is {Math.PI.ToString("F2")}"); // 3.14

 

보간 문자열의 표현식은 중첩해서 사용할 수 있습니다. { } 문자 사이의 모든 구문은 C# 코드의 일부인 동시에 표현식으로 간주됩니다.

Console.WriteLine($"The customer's name is {c?.Name ?? "Name is missing"}");

C가 NUll인지 Null 조건 연산자를 통해서 확인하고, 해당 Name 프로퍼티가 null 이면 오른쪽 구문을 수행하는 Null 병합 연산자까지 함께 사용한 코드가 위 코드입니다.

 

이처럼 문자열 보간 기능은 실수를 줄일 수 있고 더욱 강력할 뿐 아니라 활용도 또한 매우 높은 기술입니다.

적극 사용합시다!

 

최근 저도 개발하면서 문자열 관련 코드는 보간 문자열로 대체해서 사용하고 있습니다. ㅎㅎ

'CS > Effective C#' 카테고리의 다른 글

캐스트보다는 is, as가 좋다  (0) 2023.05.06
const보다는 readonly가 좋다.  (0) 2023.04.23
지역변수는 var를 사용하는 것이 낫다.  (0) 2023.04.23

캐스트의 경우에는 스타크래프트로 따지면, 드랍쉽에는 여러 유닛을 태울 수 있는데요. 여러 유닛의 각 특징들의 메서드(행동)를 가져오려고 할 때 그 유닛으로 캐스팅을 해야 그 유닛의 고유의 능력이나 행동을 가져올 수 있습니다.

그럴 때 캐스트가 필요하게 되는데요.

캐스트에 대해서 어떻게 하면 더 효율적으로 사용할 수 있는지에 대해서 알아봅시다.

 

C#은 정적 타이핑을 수행하는 언어입니다.

그래서 보통 판단은 정적으로 하려고 하는데요. 위와 같은 상황에서 런타임에서(게임 실행 중)에 반드시 타입을 확인해야할 필요가 있는 경우가 있습니다.

 

C#에서는 2가지 캐스트를 지원합니다.

1. as 연산자를 사용하는 방법 (더 방어적으로 사용하는 is 연산자로 형변환이 가능한지를 확인한 후에 실제 형변환 진행)

2. 일반적으로 알고 있는 컴파일러의 캐스트 연산자 구문을 사용하는 방법

 

형변환을 수행하는 경우에는 캐스팅을 사용하기보다는 as 연산자를 추천합니다.

- 안전한다.

- 런타임에 더 효율적으로 동작한다.

 

다만 as 나 is 연산자는 객체의 타입이 변환하려는 타입과 정확히 일치할 경우에만 형변환이 성공적으로 수행됩니다.

일반적으로는 형변환 과정에서 새로운 객체가 생성되는 경우는 없지만,

예외적으로 as 연산자를 이용하여 박싱된 값 타입의 객체를 nullable 값 타입의 객체로 변환하는 경우에 새로운 객체가 생성됩니다.

object o = Factory.GetValue();
var i = o as int?;
if (i != null)
    Console.WriteLine(i.Value);

위의 경우에는 as 연산자를 사용할 때 int는 값 타입이고 null이 될 수 없어서 일반적으로는 int로 형변환이 불가능하지만,

as 연산자는 그대로 사용하면서 nullable 타입으로 형변환을 수행한 후에 그 값이 null인지 판단으로 확인하는 방법도 있다.

 

as 연잔자를 사용해서 캐스팅 방법은 다음과 같다.

 object o = Factory.GetObject();

 MyType t = o as MyType;

 if (t != null)
 {
     // MyType 객체 사용
 }
 else
 {
     // 실패
 }
as 연산자와 캐스팅의 가장 큰 차이

사용자 정의 형변환을 어떻게 다루는가 하는 점입니다.

 

as나 is연산자는 런타임에 객체의 타입을 확인하고 필요에 따라서 박싱을 수행하는 것을 제외하고는 어떠한 작업도 수행하지 않습니다. 임의의 객체를 다른 타입으로 형변환하려면 이 객체는 지정한 타입이거나 혹은 지정한 타입을 상속한 타입이어야만 하고 그 외에는 null로 지정됩니다.

 

캐스팅의 경우 객체를 지정한 타입으로 변환하기 위해서 형변환 연산자가 개입될 수 있습니다.

대표적인 형변환 연산자가 바로 숫자 타입에 대한 형변환 연산자라면 (long 타입을 short 타입으로 캐스팅하면 일부 정보를 잃을 수 있다는 것)이 문제가 됩니다.

물론 사용자의 의도일 수 있겠지만 일반적으로 data의 손실이 되도록 코드를 짜는 것은 좋지 않습니다.

class SecondType
{
    private MyType value;

    public static implicit operator MyType(SecondType t)
    {
        return t.value;
    }
}

class MainApp
{
    static void Main()
    {
        object o = Factory.GetObject();

        // o는 SecondType이라고 가정하면
        // 첫 번째 방법
        MyType t = o as MyType;

        if (t != null)
        {
            // MyType 타입의 t 객체 사용
        }

        // 두 번째 방법
        try
        {
            MyType t2;
            t2 = (MyType)o;

            // MyType 타입의 t2 객체 사용
        }
        catch (InvalidCastException e)
        {
            // 형변환 오류 보고
        }
    }
}

as 연산자와 캐스팅의 방법은 모두 실패합니다.

캐스팅 방법을 사용하면 사용자 정의 형변환 연산자가 사용된다고 했었으나,,

컴파일러는 런타임에 객체가 어떤 타입일지를 예측하지 못..(정적 타이핑 이므로)

컴파일러는 단순히 컴파일 타임에 객체가 어떤 타입으로 선언됐는지만 추적하기 때문에 모두 실패하게 됩니다.

 

컴파일러는 객체 o가 런타임에 어떤 타입인지를 알 방법이 없습니다.

컴파일러는 객체 o가 object 타입이라고 생각하고 object 타입을 MyType으로 형변환할 수 있는 연산자가 정의됐는지만을 확인합니다. 이러한 형변환 연산자를 정의하지 않았기 때문에 컴파일러는 이제 o 객체가 MyType 형식인지를 확인하는 코드만 생성합니다.

런타임에 o는 SecondType 형식의 객체이므로 형변환에 실패하게 됩니다.

컴파일러는 런타임에 o가 어떤 타입일 지를 예측하고 이를 기반으로 MyType으로 형변환이 가능한지를 고려하지는 않습니다.

 

사용자 정의 형변환 연산자는 객체의 런타임 타입이 아닌 컴파일타임 타입에 맞춰 수행된다는 점에 다시 한번 유의합니다.

런타임에 o 객체를 MyType으로 변환할 수 있는지는 중요하지 않고 이에 대해서 알지도 못하며 고려하지도 않습니다.

다만 사용자 정의 형변환 연산자가 정의되었다면?

어떤 타입으로 선언되었느냐에 따라 다르게 동작할 수 있습니다.

 

캐스팅보다 as 연산자를 사용한다라면 어떤 타입으로 선언되었든 간에 항상 동일한 결과를 반환해줍니다.

t = o as MyType;

설사 사용자 정의 형변환 연산자가 정의됐다 하더라도 o가 MyType이나 MyType을 상속한 타입이 아니라면 컴파일 오류를 발생합니다.

 

foreach

자주 사용하는 foreach 루프는 제너릭 타입이 아닌 IEnumerable 인터페이스를 사용합니다.

class MainApp
{
    // version 1
    public void UseCollection(IEnumerable theCollection)
    {
        foreach (MyType t in theCollection)
            t.DoSuff();
    }
    
    // version 2
    public void UseCollection2(IEnumerable theCollection)
    {
        IEnumerator it = theCollection.GetEnumerator();
        while (it.MoveNext())
        {
            MyType t = (MyType)it.Current;
            t.DoSuff();
        }
    }
}

foreach 문은 캐스팅을 통해서 루프에서 사용되는 타입으로 객체를 형변환합니다.

version 1이 흔히 사용하는 foreach 문이고, 아래 version 2는 위의 foreach 문이 생성하는 코드입니다.

 

foreach 문은 값 타입과 참조 타입 모두에 대해서 형변환을 지원해야 하는데 이때 캐스팅을 사용하면 대상 타입을 구분할 필요가 없어지게 됩니다. 하지만 이로 인해 InvalidCastException이 발생할 가능성이 존재합니다.

 

foreach 문장은 컬렉션 내부의 객체가 런타임에 어떤 타입인지, 그 타입을 루프 변수 타입으로 형변환 가능한지 등을 확인하지 않습니다. IEnumerator.Current의 반환형인 System.Object 타입으로 형변환 가능한지와, Object 타입의 객체를 다시 루프 타입 변수로 형변환 가능한지만 확인합니다.

 

특별히 객체의 타입이 정확히 MyType인 경우에만 동작하는 함수를 만들고자 한다면 더 정밀한 타입 비교가 필요한데,

.NET 기본 클래스 라이브러리에는 시퀀스 내의 개별 요소들을 특정 타입으로 형변환하는 Enumerable.Cast<T>() 메서드가 존재합니다.

class MainApp
{
    static void Main(string[] args)
    {
        IEnumerable collection = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

        var small = from int item in collection
                    where item < 5
                    select item;

        var small2 = collection.Cast<int>().Where(item => item < 5).Select(n => n);
    }
}

여기서 Cast<T> 메서드는 as 연산자 대신 캐스트 연산을 수행하는데, as 연산자를 사용하면 형변환하려는 타입에 제한이 생기기 때문에 Cast<T> 메서드를 구현하는 대신 캐스트 연산을 사용하는 단일 Cast<T> 메서드만 작성했다고 합니다.

 

가능하면 형변환은 피하자.

사용자의 의도를 명확히 표현할 수 있는 is나 as 연산자를 사용하는 것이 좋습니다.

is나 as 연산자는 거의 예상대로 동작하며 대상 객체를 올바르게 형변환할 수 있을 경우에만 성공하고 나머지는 실패합니다.

 

캐스트 연산보다는 is나 as를 사용하는 것이 의도하지 않은 부작용이나 예상치 못한 문제를 피할 수 있는 좋은 방법이 됩니다.

간혹 성능을 위해서 상수형을 작성하게 될 때 엄청난 고민을 하게 됩니다.

이때 누구는 const를 쓰고, 또 누구는 readonly를 쓰고 있습니다. 어떨 때 이걸 쓰고, 또 어떨 때 이걸 쓰는지 코드를 작성하다 보면 고민이 깊어져 2시간가량을 먹었던 기억이 있습니다.

그 답 오늘 해결해봅시다!

 

C#은 컴파일타임 상수와 런타임 상수 2 유형의 상수를 가집니다.

컴파일타임 상수는 const를 의미하고, 런타임 상수는 readonly를 의미합니다.

// 컴파일타임 상수
public cosnt int Millennium = 2000;

// 런타임 상수
public static readonly int ThisYear = 2004;

컴파일타임 상수가 약간 더 빠르긴 하지만, 런타임 상수에 비해서 유연성이 떨어집니다.

결론적으로 말하자면,

컴파일타임 상수는 성능이 매우 중요하고 상수의 값이 절대로 바뀌지 않는 경우에만 제한적으로 사용하고,

나머지는 런타임 상수를 사용하는 것을 추천합니다.

 

컴파일타임 상수는 메서드 내에서 선언이 가능, 런타임 상수는 메서드 내에서 선언이 불가능

서로 다르게 동작하는 이유는 값에 접근하는 방식이 서로 다릅니다.

컴파일타임 상수는 컴파일타임에 변수가 값으로 대체됩니다.

// 사용자가 작성한 코드
if (myDateTime.Year == Millenium)

// IL 코드로 컴파일되면 아래와 같다.
if (myDateTime.Year == 2000)

반면에 런타임 상수런타임에 값이 평가됩니다.

상수처럼 값으로 대체되지 않고 상수에 대한 참조로 컴파일됩니다. (한 번 살펴보고 그 값으로 컴파일된다는 뜻)

 

이러한 차이로 인해서

컴파일 상수는 내장된 숫자형, enum, 문자열, null에 대해서만 사용이 가능합니다.

오히려 그 외의 값을 사용하려고 할 때에는 컴파일 오류가 발생합니다.

private const DateTime localTime = new DateTime(2023, 4, 23, 0, 0, 0);

런타임 상수는 생성자에서 초기화될 수 있으며 그 이후에는 수정될 수 없습니다.

런타임은 컴파일 상수보다 아까 유연하게 사용될 수 있다고 했습니다.

해당 런타임 상수는 어떤 타입과도 함께 사용이 가능하며, 멤버 초기화 구문뿐 아니라 생성자를 통해서도 초기화가 가능하다는 점입니다. (서로 같은 클래스의 인스턴스지만 내부적으로는 생성자에 의해 서로 다른 값을 가지는 장점도)

 

클래스 내에서 런타임 상수를 정의하는 경우라면 동일 클래스의 인스턴스라 하더라도 인스턴스 별로 서로 다른 값을 가질 수 있습니다. 반면에 컴파일타임 상수는 정의에 따라 정적 상수이므로 모든 인스턴스가 동일한 값을 가질 수밖에 없습니다.

 

가장 중요한 차이

상수의 값이 런타임에 평가된다는 점입니다.

런타임 상수를 참조하는 코드를 컴파일하면 컴파일타임 상수처럼 코드를 값으로 대체하지 않고, readonly 변수에 대한 참조 코드를 생성합니다.

 

응용프로그램을 유지보수할 때 상당한 영향을 미치는데요.

컴파일타임 상수는 다른 어셈블리의 참조 여부와 상관없이 항상 숫자나 문자열 등을 직접 사용한 것과 완전히 동일한 IL 코드를 생성합니다.

물론 성능상 좋겠지만 응용프로그램 전체를 리빌드(rebuild) 하지 않고 수정된 부분만 빌드(build)하면 오히려 예상했던 것과 다르게 이전에 빌드했는 결과가 나올 수 있다는 것입니다.

 

응용프로그램의 크기가 작으면 상관없겠지만, 보통은 리빌드 하는데 30 ~ 1시간 (많은 시간)이 소요되기 때문에 내가 수정한 영역만 다시 빌드하는 Build를 하기 마련입니다. 그런데 빌드만 하기에는 컴파일타임 상수는 수정된 것으로 반영되지 않는다는 것이죠. 그래서 해당 상수를 참조하는 모든 코드를 반드시 재컴파일 해야 합니다.

 

반대로 런타임 상수는 이러한 대응에 유연합니다. readonly 변수에 대한 참조 코드를 생성했기 때문에 컴파일 시에 참조 코드가 생성되고 런타임이 비로소 그 값을 평가하게 됩니다.

이렇게만 보면 readonly가 최고?!

readonly 대신 const를 사용했을 때 얻을 수 있는 장점은 성능이 빠릅니다.

코드를 상수값으로 대체하기 때문에 readonly 변수를 통해서 값을 참조하는 것보다는 당연히 빠를 수밖에 없습니다.

하지만,, 성능 개선 효과가 크지 않고 유연성을 해치기 때문에 사용자의 판단이 무엇보다 중요합니다.

 

특성 매개변수(attribute), swich/case 문의 레이블, enum 정의 시 사용하는 상수 등은 컴파일 시에 사용돼야 하므로 반드시 const 통해서 초기화하고 그 외에는 readonly를 사용하는 것이 좋습니다.

최근에 인턴으로 들어오신 팀원이 지난 주에 직군 면접을 봤었습니다.

직군 면접에 대해서 이것저것 얘기하다 보니 생각난 것이 있습니다.

바로 Effective C#인데요.

사수님께서 입사 후 제일 먼저 사주신 책입니다.

예전에 직군 면접 보기 전에 한번 정독했던 기억도 나고, 블로그에 정리하면서 내실을 다지는 것이 어떨까하여 시작합니다.

 

가장 흥미로우면서도 편리한 var 에 대해서 설명하는 단원이네요.

 

득 보다 실이 많다.

정확한 반환 타입을 알지 못한 채 올바르지 않은 타입을 명시적으로 지정하게 되면 오히려 손해라는 뜻입니다.

극단적으로 값 타입을 object 형으로 받아버리는 것도 마찬가지죠.

 

버그가 발생하여 유지보수를 하려고 할 때에 많은 코드 분석을 하게 됩니다.

이럴 때 너무 긴 코드는 오히려 집중도를 떨어트리기도 합니다. 이때는 var를 사용해서 너무 긴 타입의 형은 간단한 var 형식으로 처리할 수 있습니다.

// 1
Dictionary<int, MainQuest> mainQuestDic = new Dictionary<int, MainQuest>();
// 2
var mainQuestDic = new Dictionary<int, MainQuest>();

 주렁 주렁 타입이 긴 변수명은 생각을 해야 하는 프로그래머가 작성에만 집중하게 된다는 단점이 있습니다.

 

C#에서는 특정 변수를 var로 선언하게 되면, 동적으로 수행되는 것이 아니라 할당 연산자 오른쪽의 타입을 확인하고

왼쪽 변수의 타입을 결정하게 됩니다.

컴파일러는 변수의 타입을 명시적으로 알려주지 않더라도 개발자를 대신해서 올바른 타입으로 추론합니다.

마치 CPP의 auto 랑 비슷하네요.

 

Primitive type 은 var를 함께 사용할 때 주의가 필요합니다.

내장된 숫자 타입을 var랑 함께 사용하는 것은 문제가 되진 않으나 예상했던 결과와 다르게 동작할 수 있습니다.

var total = 100 * GetMagicNumber() / 6;

// GetMagicNumber() 가 어떤 타입의 값을 반환하는 지에 따라 데이터가 잘릴 수도 있다.

개발자는 컴파일러 처럼 내부적으로 이뤄지는 타입 추론과 암시적 변환 과정을 쉽사리 명확하게 이해하기가 어렵습니다. 간혹 휴먼 에러가 발생합니다.

명확한 계산(= 의도한 계산)에 대해서는 명시적으로 선언하는 것이 좋습니다.

 

오잉 그러면 결론?

var를 이럴 때 사용해보자.

- 모호함을 불러일으킬 가능성이 있는 타입은 명시적으로 선언하는 것이 좋다.

- Primitive type에 대해서는 가능하면 명시적으로 선언하여 실수를 줄이자.

그 외에는 var를 사용하는 것이 베스트다.

'CS > Effective C#' 카테고리의 다른 글

string.Format()을 보간 문자열로 대체하라  (0) 2023.05.06
캐스트보다는 is, as가 좋다  (0) 2023.05.06
const보다는 readonly가 좋다.  (0) 2023.04.23
어떤게 더 좋을까?
// 접미어
for (int i = 0; i < n; i++)
{
	...
}

// 접두어
for (int i = 0; i < n; ++i)
{
	...
}

 

접미어 방식이나 접두어 방식 모두 논리적으로는 아래 블록으로 들어오게 되면 i 자체는 논리적으로 모두 +1씩 증가하게 됩니다.

 

접미어 방식과 접두어 방식의 선택이 프로그램의 행동에 영향을 주지 않더라도, 이런 선택이 때때로는 실행 속도에 작게 나마 영향을 준다고 합니다.

 

접미어 방식은

1. 값의 복사본을 만든다.

2. 복사본의 값을 증가시킨다.

3. 복사본을 리턴한다.

 

접두어 방식은

1. 값을 증가시킨다.

2. 그 값을 리턴한다.

 

복사본을 만든다는 과정의 차이가 생깁니다.

복사본이라는 것은 작은 프리미티브 타입이라면 괜찮으나, 사용자 정의형 데이터(구조체나 클래스) 등의 복사 비용은 생각보다 만만하지 않습니다.

 

결론으로는 프리미티브 타입은 어느 방식을 사용해도 거의 차이가 없지만,

사용자 정의형 데이터라면 접두어 방식이 조금 더 효율적입니다.

 

현업에서도 C++ 구조로 짜시는 분들은 접두어 방식을 많이 사용하고,

C# 구조로 짜시는 분들은 접미어 방식을 많이 사용하는 것 같습니다. 물론 C# 은 foreach 방식도 있으니..

 

이왕이면 접두어 방식을 사용합시다!

'CS > C++' 카테고리의 다른 글

클래스 설계  (0) 2024.07.28
클래스 상속  (0) 2024.07.27

최근 C++ 로 공부하고 있어 C++ 문법 기준으로 작성함을 알려드립니다. (_ _)

 

면접에서 한 번 질문받았던 내용입니다.

 ~ 님 혹시 자동공간, 정적공간, 동적공간에 대해서 아시나요?

그때는 첫 면접이라 아는 건 엄청 많았는데,, 설명을 너무너무 못했습니다. (따흑..)

면접 끝난 후에 복귀하면서 이렇게 쉽게 설명할 수 있는걸! 하는 기억에..

이번에 좀 자세하게 작성해서 또 같은 실수를 반복하지 않도록 방지하고자 작성합니다.

 

여러분은 아시나요?

한 번 생각해보시고 아래로 와주세요.

 

 

C++ 에서는 데이터를 저장해 두기 위한 메모리를, 대입하는 방법에 따라 3가지로 구분합니다.

자동 공간(Automatic storage), 동의어로는 자유 공간 혹은 힙(heap)이라고 하네요.

정적 공간(Static storage)

동적 공간(Dynamic storage)

자동 공간

많이들 사용했을 겁니다.

함수 안에서 정의되는 보통의 변수들을 자동 변수라고 합니다.

자동 변수들이 자신의 정의되어 있는 함수가 호출되는 순간에 자동으로 생겨나 그 함수가 종료되는 시점까지만 존재한다라고 해서 자동 변수입니다.

 

이러한 자동 변수들은 자신들을 포함하고 있는 블록 안에서만 유효하고 블록을 벗어난 공간에서는 소멸합니다.

 

메모리적인 측면에서는 어디 공간에 존재할까요? 바로 스택에 저장됩니다.

스택은 그 값이 순차적으로 저장되고, 역순으로 해제되는 특징이 있어 프로그램이 실행하는 동안 늘었다가 줄었다가 반복하면서 관리됩니다. (대부분 변수들을 선언해서 잠깐 사용하고, 블록을 벗어나면 접근할 수 없습니다.)

정적 공간

프로그램이 실행되는 동안에 지속적으로 존재하는 공간을 말합니다.

만드는 방법은 2가지인데요.

첫 번째로 전역 변수를 선언하는 겁니다.

두 번째로 static 키워드를 사용해서 선언한 변수입니다.

언제 어디서나 접근할 수 있지만, 결국 프로그램이 종료되면 같이 소멸됩니다.

 

메모리적인 측면에서는 데이터 영역에 존재합니다.

이렇게 보면 모든 공부는 하나로 연결되는 것처럼 느껴지네요. (언젠간 나도 그러겠지..)

동적 공간 (자유 공간, 힙)

C++ 의 꽃이라고 할 수 있는 공간입니다.

new와 delete 연산자를 사용해서 프로그램 실행 동안에 자유롭게 빈 공간을 찾아 메모리를 할당해서 사용합니다.

이러한 공간이 바로 동적 공간입니다.

 

동적 공간은 런타임에 필요한 만큼 생성해서 사용하고, 필요 없을 때 해제하는 자유자재로 할 수 있는 공간입니다.

 

데이터의 수명은 프로그램의 수명이나 함수의 수명에 얽매이지 않습니다.

프로그래머의 delete를 사용하냐에 따라 수명이 달라집니다.

다만, delete 를 사용하지 않게 되면 계속해서 살아남게 되고 그곳에 접근할 수 있는 유일한 포인터를 잃어버리게 된다면 그 공간에 접근할 수 없습니다.

이를 메모리 누수(memory leak)이라고 하며, 이게 계속 계속 누적된다면 사용하지는 않는데 메모리만 잔뜩 먹게 되는 프로그램이 되는 것이죠.

 

반드시 new와 delete는 짝꿍처럼 다녀야 합니다.

 

메모리적인 측면에서는 Heap 영역에 존재합니다.

데이터의 크기가 확실하지 않고 변동이 있기 때문에 Heap이라는 공간에서 메모리를 할당해 사용을 하고, 사용하지 않을 때는 반드시 해제를 해야 합니다. (해제할 때도 2번 해제하면 정의되지 않은 행동이라고 하여 위험합니다.)

 

제일 중요한 건 개발할 때,

변수들의 특징을 잘 알고 사용하면 조금 더 효율적인 프로그램이 될 것 같습니다.

자연수 N과 K가 주어졌을 때, 이항 계수 nCk 를 구하는 문제입니다.

 

해당 숫자를 10,007로 나누는 의미는 대부분 큰 숫자인 경우에 해당 숫자로 나누는 테크닉이 필요합니다.

이항 계수는 중요한 성질을 가지고 있습니다.

 

n과 k가 같을 때 혹은 k가 0일 때는 1입니다. 이를 통해 base condition 을 만족할 수 있고,

 

파스칼 법칙에 의하면 nCr = n-1Cr-1 + n-1Cr 을 만족하게 됩니다.

이러한 법칙을 하나씩 하다 보면 반복되는 구간이 생기게 됩니다. 반복되는 것을 계속해서 계산하는 것은 낭비입니다. 따라서 한 번 구한 답을 캐시에 저장하면, 이후에 꺼내다 쓰면 됩니다. 이것을 메모리제이션이라고 합니다.

 

위에서 base condition도 만족하지 않고, 메모도 하지 않았다면 적어도 한 번은 계산해야 되기 때문에

dp[n][k] = func(n - 1, k - 1) + func(n - 1, k) 를 통해 구하고 리턴합니다. 다만 주의할 점은 계산할 때마다 10,007 로 나누어 줘야 합니다.

 

따라서 dp[n][k] = (func(n - 1, k - 1) % 10,007 + func(n - 1, k) % 10,007) % 10,007

 

이렇게 푸는 방식을 dp(다이내믹 프로그래밍) 중에서도 Top-down 방식입니다.

#include <iostream>
using namespace std;

typedef long long ll;
int n, k;
ll dp[1001][1001];

const int MOD = 10007;

ll combination(int n, int k)
{
	if (dp[n][k] != 0) return dp[n][k];
	if (n == k || k == 0) return 1;

	dp[n][k] = (combination(n - 1, k - 1) % MOD + combination(n - 1, k) % MOD) % MOD;

	return dp[n][k];
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	cout << combination(n, k) << endl;
	return 0;
}

'Algorithm' 카테고리의 다른 글

[백준 9996] 한국이 그리울 땐 서버에 접속하지  (0) 2024.08.16
[백준 11655] ROT 13  (0) 2024.08.15
[백준 1654] 랜선 자르기  (0) 2021.12.23
[백준 2231] 분해합  (0) 2021.12.22
[백준 1991] 트리 순회  (0) 2021.12.12

오랜만에 파라메트릭 서치 문제를 풀었습니다.

파라메트릭 서치 문제는 최적화 문제를 결정 문제로 바꾸어 푸는 문제입니다.

 

주어진 문제는 여러 개의 랜선의 길이가 주어졌을 때, 각 랜선들을 mid로 자르면 나눠지는 랜선의 개수가 N개 이상을 만들면 되는데, 이때 mid의 길이를 가능한 최대로 뽑고 싶다는 것이 이 문제의 핵심입니다.

 

예시에서는 200m로 잘랐을 때 11개를 만들 수 있으며 나올 수 있는 최대 길이라고 합니다.

어떻게 11개가 나왔을까요.

802 / 200 = 4

743 / 200 = 3

457 / 200 = 2

539 / 200 = 2

4 + 3 + 2 + 2 = 11개가 됩니다.

 

정리하면 어떻게 자르든 11개 이상만 나오면 조건을 만족하며, 그때 자른 길이 중 최대를 저장하면 됩니다.

만약에 조건 11개를 만족하더라도 200보다 작을 수 있는 경우의 수가 존재할 수 있습니다.

무슨 말이냐면, 

802 / 199 = 4

743 / 199 = 3

457 / 199 = 2

539 / 199 = 2

4 + 3 + 2 + 2 = 11개

어떤가요. 주어진 조건을 만족하면서도 자른 길이가 199m입니다.

 

정답이 한 가지가 아니라 여러 가지라는 뜻이죠.

우리는 조건을 만족하더라도 더 최대로 자를 수 있는 경우가 있으면 그것이 정답이라는 뜻입니다.

조건을 만족한다! 더 길게 잘라볼까?????

조건을 만족하지 못한다! 좀만 적게 잘라보자...

 

약간 실생활을 생각해보면 됩니다.

이정도 자르면 4개는 나오겠지??

싹둑, 어라? 3개네 좀 더 짧게 잘라야겠다!

이런 경험이 있을 것입니다.

 

이렇게 조건을 만족하더라도 더 가보자!!처럼 이러한 방식을 파라메트릭 서치라고 합니다!

 

자르는 방법은 다음과 같습니다.

len의 길이로 자른다고 가정했을 때 나오는 개수를 우리는 아래와 같이 작성할 수 있습니다.

bool calc(int len)
{
    int cnt = 0;
    for(int i = 0; i < K; i++)
    {
        cnt += v[i] / len;
    }
    
    return cnt >= N;
}

랜선의 길이가 2^31 - 1보다 작거나 같은 자연수이기 때문에 이 말은 곧 0부터 int의 최댓값까지 나올 수 있다는 말이므로.

우리가 자르고자 하는 길이의 탐색 구간은 0 ~ INT_MAX까지! 

자연수라고 했으니까 0이 아니고 1로 해도 됩니다.

그런데 여러 문제를 풀어보니까 0이 실수도 안 하고 그렇습니다.

 

기존의 이진 탐색처럼 반복문을 구성하고 해당 mid(자를 길이)를 선택했다면 그걸로 잘라보고,

조건을 만족한다면 더 나아가 보고 (여기서 나아간다는 뜻은 길이를 더 길게 잘라보겠다는 뜻)

조건을 만족하지 못한다면 더 짧게 잘라보고

하면서 길이를 갱신해나가면 됩니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int K, N;
vector<int> v;

bool calc(int len)
{
    int cnt = 0;
    for(int i = 0; i < K; i++)
    {
        cnt += v[i] / len;
    }
    
    return cnt >= N;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> K >> N;
    v.resize(K);
    for(int i = 0; i < K; i++) cin >> v[i];
    long long left = 0;
    long long right = INT_MAX;
    long long ans = 0;
    while(left <= right)
    {
        long long mid = (left + right) / 2;
        
        if(calc(mid))
        {
            ans = max(ans, mid);
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    
    cout << ans << endl;
    return 0;
}

'Algorithm' 카테고리의 다른 글

[백준 11655] ROT 13  (0) 2024.08.15
[백준 11051] 이항 계수 2  (0) 2022.01.11
[백준 2231] 분해합  (0) 2021.12.22
[백준 1991] 트리 순회  (0) 2021.12.12
[백준 1120] 문자열  (0) 2021.12.09

객체지향 프로그래밍을 해봤다면 지문 이해가 쉬웠을 것 같습니다.

어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라고 합니다.

간단히 말하자면 M으로 인해 N이 생겨났으니, 주체인 M이 N의 생성자라고 생각하면 됩니다.

그랬을 때 문제에서 N이 입력으로 주어지면 우리는 M을 구해야 합니다.

그중에서도 가장 작은 M을 구하려면 M을 1부터 검사하면서 N을 만들 수 있는 생성자를 찾아가면 됩니다.

언제까지 찾으면 될까요?

확실한 건 M은 N보다 클 수 없습니다. 생성자니까요.

따라서 N보다 작을 때까지만 루프를 돌면 됩니다.

 

calc함수는 어떤 자연수의 각 숫자의 합을 리턴하는 함수입니다.

문자열로 쪼개서 계산해도 되지만, 이러한 방식이 오히려 더 편할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int calc(int n)
{
    int sum = 0;
    while(n)
    {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    int cur = 1;
    bool found = false;
    while(cur < n)
    {
        int num = cur + calc(cur);
        if(num == n)
        {
            cout << cur << endl;
            found = true;
            break;
        }
        cur++;
    }
    
    if(found == false)
        cout << "0\n";
    return 0;
}

'Algorithm' 카테고리의 다른 글

[백준 11051] 이항 계수 2  (0) 2022.01.11
[백준 1654] 랜선 자르기  (0) 2021.12.23
[백준 1991] 트리 순회  (0) 2021.12.12
[백준 1120] 문자열  (0) 2021.12.09
[백준 2960] 에라토스테네스의 체  (0) 2021.12.07

+ Recent posts