https://github.com/koosaga/DeobureoMinkyuParty


나는 내 코드나 내 자료들을 퍼블릭하게 올리는게 이롭다고 생각해서 자료들을 계속 업로드 하자고 제안을 했었다.


팀노트를 깃헙에 올리는게 어떻냐고 물어봤고 팀원들이 동의를 했다. 그래서 대전 리저널이 끝난 이후에 올리자는 얘기가 있었고 결국 사과가 팀노트를 업로드 했다. 사실 내가 좀 주도적으로 하는 일이여야 하는게 맞지 않았나 싶다. MolaMola 팀이나 Please Open Testdata 같은 팀도 팀노트를 열었기 때문에, 다른 팀노트의 좋은 점을 받아들이고 개선할 부분을 서로 개선하고 보완하는 방향으로 서로 팀노트를 잘 만들어 갔으면 좋겠다.


사실 지금 팀노트가 굉장히 난해하고 PS에서 사용하는 지식들의 끝단을 다루는 것 같다. 그래서 더 다양한 코드들을 추가하고, 입맛에 맞게 팀노트를 조절해가면서 쓸 수 있게 다양한 레퍼런스 코드들을 써 보려고 한다. 예를들면 기본적인 알고리즘인 Dijkstra나 Extended Euclidean Algorithm 같은 것들은 팀원이 다 짤 줄 안다고 작성을 안했고... 팀원이 알지만 디버깅할 때 버그가 많이 생기는 알고리즘이나, 상수가 매우 작은 (Locality to the rescue!) 알고리즘들이 들어있다. 혹은 공식들을 그냥 블랙박스로 사용하는 정도이다.


공개할 용도의 팀노트를 정비하는 일도 결국에는 해야 할 일인데, 언제부터 해야할 지 모르겠다. 일단 다양한 예제들을 추가하는 것으로 부터 시작해야겠다.

고등학교때 부터 시작해서 4년 8개월동안 기숙사 생활을 했다. 2013년 3월 부터 시작해서, 2017년 11월 이 글을 쓰는 시점까지 그리고 이제 자취라는 것을 시작해 보려고 한다. 아마 12월쯤이면 자취를 시작하지 않을 까 싶다. 방 정리하기가 귀찮아서 그렇지 끝나면 거의 들어가지 않을까 싶다.



자취를 시작하게 된 원인에는 여러가지가 있다. 기숙사 생활에 질린것이 가장 클 것이다. 그리고 여러가지 내가 가지고 있는 욕구들을 해소하기 위해서 일 것이다. 예를들면 "개인 공간이 필요하다." 라든가 "요리가 하고 싶다" 같은... 몇가지를 정리 해 봐야 할 것 같다.




개인 공간이 필요하다


이게 아마 내가 가장 절실하게 자취를 하고 싶다고 생각한 이유가 아닐까 싶다. 개인 공간이 없다는 것이, 내성적인 성격 탓에 혼자 있을 시간에 나를 혼자 있게 놔두지 못하는 것도 꽤나 스트레스를 받는다. 사람 만나는 것이 내부의 에너지를 소모하면서 외로움을 없애는 것이라면, 다른 사람 없이 혼자 있는 것은 내부의 에너지를 회복하는 쪽에 가까울 것이다. 내성적인 성격의 가장 큰 장점이 "모든걸 포기하고 아무것도 안하고 오래 누워있으면 에너지가 회복이 되는 것" 이라고 생각하는데, 나는 기숙사에서 이걸 하기가 힘들었다. 사실 학기 중에 이걸 하기 힘든것도 없진 않았다. 뭐 어쨌든 방학때든 학기 중이든 혼자서 누워서 회복 할 수 있을때가 정말 필요하다고 생각했다. 내가 무얼 해도 아무도 뭐라고 하지 않는 것도 중요하다. 설령 내가 무언가를 하지 않더라도 그런 안정감을 느끼는것은 굉장히 중요하다고 생각했다.




요리가 하고 싶다


이건 사실 안 해봐서 잘 모르겠지만... 뭔가 만들고 싶다는 욕구가 있고 이상하게 요리쪽으로 그런게 있다. 먹는걸 워낙 좋아하는 것도 있을 것 같고, 여러가지 요리 레시피를 보고 좋다고 생각한것도 있는것 같다. 그리고 학교에서 먹을게 없다고 느낀것도 제일 크다. 학교에서 배달을 시켜먹거나 학식을 가서 먹으면 만날 뻔한 메뉴의 음식들을 계속 먹게 되는데 너무 질렸다.




부동산이 필요하다


뭔가 집을 가지고 사고 판다는 의미가 아니라, 내가 원하는 것들을 하려면 나만 건드릴 수 있는 공간이 있어야 한다. 예를들면 서버를 배치한다거나, 피규어를 놓는다거나, 개인 공간이 필요한다는 것과 비슷한 맥락인것 같기도 하지만, 조금 다른 느낌의 장소가 필요하다. 사실 피규어를 안 모으는 이유에는 놓을 곳이 없다는 것도 있다.





학교에 들어와서 동아리방에서 잔 적이 기숙사에서 잔 적보다 많은 것 같다. 어차피 기숙사가 개인 공간이 아니고, 동아리방은 외로움도 해결할 수 있고 바로 옆에 컴퓨터도 있기 때문에 이런 것 같다. 동아리방에서 자면 건강도 안 좋아지고, 이런데 자취가 뭔가 내가 바뀔수 있는 계기를 제공하지 않을까 하고 생각한다.

'생각들' 카테고리의 다른 글

동아리 하제  (0) 2018.08.27
교수님과 상담을 하고 왔습니다  (1) 2018.07.11
2018년 가을 5학기 수강신청  (0) 2018.07.09
자기비하에 내가 느낀 점에 대해  (2) 2017.12.16
기말고사 안 갔다.  (0) 2017.12.12
자취에 대해서  (0) 2017.11.22

조건문과 반복문은 프로그래밍 언어를 단순한 계산기에서, 프로그래밍을 할 수 있는 도구로 만들어 주는 열쇠일 것이다. 오늘은 반복문을 사용할 때 많은 프로그래머들이 (익숙해서든, 익숙하지 않아서든) 잊어버리는, 루프 불변조건(Loop-invariant)에 대해 다뤄 보려고 한다. 최대한 이해하기 쉽게 작성하려고 했다.


 


프로그래밍을 하면서 가장 많이 만나는 것 중 하나는 반복문이다. 반복문은 C/C++과 Python에서 다음과 같은 꼴이다. (여기서 i++ 은 i += 1, i를 i의 다음숫자로 바꾼다.) 이다.

C, C++: for(int i=0; i<n; i++)
Python: for i in range(n):

이 글에서는 C, C++ 스타일의 반복문을 많이 사용하여 설명할 것이다. 이런 형태의 반복문을 보지 못한 사람들을 위하여, 그리고 다시 한번 반복문을 생각하기 위하여 C/C++ 스타일의 for문 부터 다시 한번 짚고 지나가자.




C/C++스타일의 반복문은 다음과 같이 생겼다.

for( init_statement; condition; iteration_expression )
{
	statement;
}

이것을 풀어서 쓰면, 다음과 같은 모양이다. (실제로는 Scope가 달라진다.)

init_statement;
while(condition)
{
	statement;
	iteration_expression;
}

while(p)는, p를 만족할 동안 정해진 내용을 반복한다는 뜻이므로 (정해진 내용을 만족하면 빠져나오고, 만족하지 않으면 while문의 처음부터 다시 시작한다.)

 for(int i = 0; i < n; i++) f(i); 

라고 적힌 코드는,

int i = 0;
while(i < n)
{
	f(i);
	i++;
}

의 일을 하게 되고, 이는 실제로 반복을 해보면 이는 실제로 손으로 해보면, f(0)을 호출하고, i가 1 늘어서 f(1)을 호출하고... 이를 반복하여 f(0), f(1), ..., f(n-1)까지의 함수 호출을 하는 것을 알 수 있다. 그리고 이는 Python에서의 range를 사용한 루프와 같다. 한가지 차이점이 있다면, C, C++의 for loop에서는  statement가 i를 바꿔서는 안된다.




반복문을 이용해서 코드를 하나 작성해 보자. 반복문의 예제 코드 중 하나이다. 배열의 길이 N과 배열 A를 받아서 최댓값을 반환하는 함수를 만들어 보자. (여기서, N은 1 이상임이 보장되어 있고, A는 0번째 원소부터 N-1번째 원소까지 있다.)

int getMax(int N, int A[]) { int maxv = A[0]; for(int i=1; i<N; i++) if(maxv < A[i]) maxv = A[i]; return maxv; }

굉장히 평범하고 많은 사람이 작성할법한 코드이다. 그럼 이 코드가 맞다는 것을 설명해보자. 우리는 수학적 귀납법을 사용할 것이다.

코드를 while문을 이용하여 같은 코드로 작성하면 다음과 같이 된다.:

int getMax(int N, int A[])
{
	int maxv = A[0];
	int i = 1;
	while(i < N)
	{
		if(maxv < A[i])
			maxv = A[i];
		i++;
	}
	return maxv;
}

증명할때, 루프 불변조건(loop-invariant)이라는 개념을 도입할 것이다. 이 루프 불변조건은 루프가 시작할때 유지되는 조건들을 의미한다. 이 문제에서의 루프 불변조건은, maxv의 값이 A[0]부터 A[i-1]까지의 최댓값을 가지고 있다는 것이다. 주석을 달아서 자세하게 확인해 보자.

int getMax(int N, int A[])
{
	int maxv = A[0];
	int i = 1;
	// 1 - maxv의 값은 A[0]
	while(i < N)
	{
		// 2 - maxv의 값은 A[0]부터 A[i-1]까지의 최댓값
		if(maxv < A[i])
			maxv = A[i];
		// 3 - maxv의 값은 A[0]부터 A[i]까지의 최댓값
		i++;
		// 4 - maxv의 값은 A[0]부터 A[i-1]까지의 최댓값
	}
	// 5 - maxv의 값은 A[0]부터 A[N-1]까지의 최댓값.
	return maxv;
}

1번 조건이 만족한다는 것은 maxv가 A[0]이고, 숫자가 하나만 있으면 그 숫자가 최댓값이라는것에서 알 수 있다.

2번 조건은, i = 1일때는 1번조건과 같다.

3번 조건은, 2번 조건에서 A[i]가 A[0]부터 A[i-1]까지의 최댓값보다 크면, A[i]가 다른 모든 수 보다 크므로 최댓값이다. 아닐 경우에는, A[0]부터 A[i-1]까지의 최댓값중에 A[i]보다 큰 값이 있으므로 최댓값이 유지될 것이다.

4번 조건은, 3번 조건에서 i값이 1커졌기 때문에 숫자를 맞춘 것이다.


이 4번 조건은, 만약에 루프를 빠져나가지 않는 다면, 다시 2번 조건에 들어가게 된다. 그리고 여기서 발견할 수 있는 흥미로운 사실은 i가 1이 커졌다는 것이다! 이것을 계속 반복되면, 루프를 빠져나올 때 i = N이기 때문에, 5번 조건 역시 만족하게 된다. 이 증명은 수학적 귀납법과 맥락을 같이한다.

 

루프 불변조건은 모든 루프문에서 다양하게 사용된다. 코딩을 하면서, 루프 불변조건은 루프를 분석하는데 굉장히 강력한 도구이고, 디버깅을 할 때도 강력하게 사용될 수 있다.(루프 불변조건을 assert하는 것으로, 논리단계를 제대로 밟고 있는지 아닌지 확인할 수 있다.) 그리고 루프가 포함된 함수를 분석하는데에 핵심이 된다.




루프 불변조건에 대해 글을 썼다. 수학적 귀납법과 같은 방식으로 생각을 해서, 증명을 한다고 생각하면 논리가 잡히기 시작할 것이다.

다음 게시글에는 동적 계획법에 대해 설명하려고 한다. 아래쪽에 풀어볼만한 연습문제들을 남겨 놓겠다. 풀이 등에 대한 질문이 있거나, 게시글에 개선할 사항은 덧글로 남겨줬으면 한다.

 



  • 배열이 있을 때, 배열의 모든 원소의 합을 구하는 프로그램을 작성하고, 그 프로그램이 올바르다는 것을 증명하여라.
  • O(n2)정렬로 유명한 삽입 정렬, 버블 정렬 그리고 선택 정렬이 올바르게 작동한다는 것을 증명하여라.
  • 최대 힙(max heap)으로 작성된 우선순위 큐가 올바르게 동작한다는 것을 증명하여라.
  • 다익스트라 알고리즘을 보고, 루프 불변조건을 이용하여 다익스트라 알고리즘이 올바르게 동작함을 증명하여라.

 



최대 힙, 우선순위 큐와 다익스트라 알고리즘에 대한 설명은 추가로 작성해서 게시글로 올리겠다.




이제까지의 모든 Logical Thinking 게시글 보기: http://blog.kyouko.moe/8



  1. SOYONGKIM 2018.10.18 11:15

    안녕하세요 글 잘 읽었습니다.
    읽다가 조금 이해가 잘 안되서 질문 드려봅니다.
    1. "maxv는 A[0]~A[i-1]까지의 최대값"이라는 것, 즉 루프 불변조건은 귀납법처럼 처음에 이러한 조건을 가정하고 검증에 들어가는 건가요?
    2. 루프 불변조건은 코드의 검증을 위해서만 사용되나요? 아니면 처음 코드를 작성할때도 사용되나요? 다시 말해 루프 불변조건을 먼저 설정하고 이에 맞춰서 코드를 작성하는 것도 가능한가요? 있다면 어떻게 해야할까요?
    (매번 코딩할때 마다 무한루프나 빠진 조건때문에 답이 이상하게 나오는 등 디버깅하는 시간이 오래걸려 다른 접근법을 찾고 있습니다..)

+ Recent posts