홍C: 섹션 1.1 ~ 1.5
C 언어는 시스템 프로그래밍을 효율적으로 하기 위해 만들어진 언어다, 특히 UNIX 운영체제의 개발에 C 가 많이 쓰였다. C는 프로그래밍 효율성이 좋다. 강력하고 유연하며 프로그래머 중심이어서 개발자에게 주어진 권한이 막강하다. 다른 시스템에 이식하기에도 용이하다. 다만 개발자에게 책임도 커지게 된다.
C는 운영체제, 게임, VFX, 임베디드, 공장 자동화 등 개발의 모든 분야에 쓰인다. 즉, 컴퓨터가 있으면 C, C++는 무조건 쓰인다.
C 언어는 다른 프로그래밍 언어와 마찬가지로 사람의 필요에 따라 발전해왔다. 벨 연구소에서 만들어진 고전 C부터 현대의 C까지 변화해왔다.
소프트웨어는 총 7단계의 개발을 거쳐온다. ① 소프트웨어 목적 정의 ② 프로그램 설계 ③ 코드 작성 ④ 컴파일 ⑤ 프로그램 실행 ⑥ 프로그램 테스트 및 오류 수정 ⑦ 프로그램 유지와 보수이다.
프로그램실행과정을 되돌아보면 프로그램 실행에 많은 요소들이 관여한다. IDE(통합개발환경)을 활용하면 개발 프로세스를 간략화할 수 있다.
퀴즈
스택과 레지스터의 차이
스택은 프로시저 호출 시 지역변수와 매개변수를 저장하기 위한 메모리 공간이다. 선언되는 순서와 반대로 메모리가 해제되는 LIFO 구조를 가지고 있다. 스택은 함수의 로컬 변수를 저장하고 함수의 제어흐름을 관리한다. 스택은 동적으로 메모리를 할당하고 해제할 수 있게 하며 구현이 간단하고 메모리 관리 오버헤드가 낮다.
레지스터는 프로세서 내부의 고속 작동 메모리로 프로시저 실행 중 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용된다. 레지스터는 중간 연산 결과를 저장하고 빠른 데이터 접근을 가능하게 한다.
꼬리재귀최적화
재귀함수가 호출 될 때마다 스택 프레임이 생성된다. 따라서 재귀함수를 호출할 때는 메모리를 계속 유의해야하고 스택 오버플로우가 되지 않도록 조심해야한다.
꼬리 재귀 최적화는 재귀함수 호출 시 호출 스택의 사용을 최적화하는 기법이다. 재귀함수를 호출하는 일반적인 방법으로는 스택에 계속 프레임이 쌓인다. 하지만 꼬리 채귀 최적화기법은 일반적인 방법과는 달리 스택메모리의 사용량을 일정량 유지한다.
일반적인 재귀방법
int factorial(int n){
if(n == 1){
return 1;
}
return n * factorial(n-1);
}꼬리재귀최적화방법
int factorialTail(int n, int acc){
if(n == 1){
return acc;
}
return factorialTail(n-1, n*acc);
}
int factorial(int n){
return factorialTail(n, 1);
}LCS
LCS는 최장공통부분수열을 구하는 문제다. 다이나믹 프로그래밍을 활용하면 2차원 테이블을 생성한 후 변화하는 지점을 재귀함수로 잡아 LCS의 길이와 형태를 구할 수 있다.
그리디 알고리즘 vs 다이나믹 프로그래밍
그리디 알고리즘이란 최적부분구조에서 매 순간마다 가장 좋아보이는 선택을 하는 알고리즘이다. 그리디 선택성이 만족될 경우에만 그리디 알고리즘을 사용할 수 있다.
다이나믹 프로그래밍이란 최적부분구조에서 하위 문제의 해결책을 상위 문제에서 중복해서 활용해야할 때 사용하는 알고리즘이다. 문제를 접근하는 방식에 따라 상향식 방식과 하향식 방식이 있다. 상향식 방식은 하위 문제의 결과를 메모이제이션 기법을 통해 기억한다. 하향식방식은 하위 문제의 결과를 아래에서부터 차곡차곡 쌓아 큰 문제를 해결하는 타뷸레이션 기법을 사용한다.
그래프의 이행적 폐쇄
모든 지점에서 다른 모든 지점에 도달할 수 있는 지 여부를 확인하기 위해 그래프의 이행적 폐쇄를 활용할 수 있다. 이행적 폐쇄는 플로이드 워셜 알고리즘을 활용해서 구할 수 있다. 그래프에서 서로 연결 되어 있는 노드들은 1, 끊긴 노드는 0으로 둔다.
모든 노드에 대해 플로이드 워셜 알고리즘을 적용해서 다른 노드에 접근할 수 있으면 0을 1로 바꾸고, 접근할 수 없다면 그대로 둔다.
모든 노드에 대해 이행적 폐쇄를 구하면 모든 지점에서 다른 지점에 갈 수 있는 지 여부를 확인할 수 있다.