1장 . 역사,장단점,난해한 C (8퀸문제),,

1

UNIX (운영체제) : Assembly - B - NB > C(언어) " portability " 

 

C로 UNIX 재구성 >  C89 or C90 > C 99

 

C기반 언어 

     C++ : C + classes, 객체지향( oop)

     java : C++ 기반

     C#  : Cpp + java

     perl : 간단 > C특징

 

C로 배워야하는 이유

1. C의 근본적인 특징 파악 > 다른 C 기반 통찰 가능

2. C가 오래돼서 자료들이 많음

3. 소프트웨어 개발에 많이사용

4. C 의 단순성 > 메모리,처리능력 한정 될때 유용 > 임베디드

 

장점

1. 효율성 : 제한된 메모리

2.이식성 : 컴퓨터의 기반 > 대부분 C

3. 강력함 : 짧더라도

4. 융통성 : 형변환,, 버그 조심

5. Standard library : 수백개의 함수들..

6 . UNIX 와의 통합 : wiht LINUX

 

단점 : 장점들과 같은이유

1. error-prone : 컴파일하기 전까진 에러 모름.. 

2. misunderstand : small but many feature > 넌 쉬운데 난 어려워

3. terse : C의 첫시대 = 컴퓨터와의 의사소통이 어려움 > 간결

4. flexible : 너무 융통성있어서 나만 알고 다른사람은 모르는 >> 코드는 항상 다수가 알수있게 작성해야함.

5. 수정의 어려움 : classes and packages 의 부재 > 대형 작업시 작게 분할 불가

 

C의 장점들을 잘 이용함과 동시에 함정들을 잘 피해가야함.. 컴파일러도 모든것을 걸러내주진 못함

 

link : C컴파일러보다 더 오류분석 잘함 ( UNIX )

 

• Compiler : 코드를 기계어로 변환 + syntax errors 분석
• lint: 정적 분석 도구, 코드를 실행하지 않고 코드를 분석> 잠재적인 문제 찾음

 

1.진단 메세지를 제공 > 하나하나 파악해야함 .. if 수백줄이면 알짜배기는 일부

2. splint 같은 서드파티 이용

3. 대안으로 컴파일러에서 warning levels > high 

debugger : 

• Compiler : 최종 실행 후 runtime error, incoorect output
• debugger : 하나하나 분석가능 

link + debugger + more reliable,,

• bounds-checkers  : 배열첨자 검사
• leak-finders: memory leaks검사, 동적할당 > 해제 x 검사

 

기존 code libraries ( 함수의 모음) 이용

    이용자 수 many > 오픈소스, 상업, 구글 등에서 쉽게 구할 수 있음

 

C의 자유로움> 합리적인 규칙 을 택해서 잘 지켜야함

> 합리적인 규칙 : 너무 복잡, 단순 X

                           standard 를 잘 지켜라 > 꼭 필요할때 빼고는

>> 최신 컴파일러는 c99 를 잘 안따름 확장기능 ex) gcc 

> gcc 가 안좋다는것 X > but 이식성문제(다른 컴파일러에서는 같은 소스코드 컴파일못하는 경우가 생김)

 

 

 

 

 

난해한 C

// 행(row), 열(col)

// 함수 매개변수 2개인데 1개만 값을 넘기면 컴파일 오류

퀸 의 공격범위 : 같은 행,열 , 대각선1(왼쪽 위 에서 오른쪽 아래) , 대각선2 ( 왼쪽아래에서 오른쪽위)

특징) 대각선1 : row == col 

          대각선2 : row+col 의값이 항상 일정

(int row, int col)

board[i] == row // 1. 같은 행에 있는지 확인, col 까지만 봐도됨( 그이상은 대각선, 공격범위밖)

 

순서

1.  solveNQueens : col (행) 에 0 들어감 

2.  issafe > board[]에 배치 > row ++

3.  solveNQueens : col + 1 

4. col 이 8 될때까지 반복

5. board[col] 이므로 이중for문에서 두번째를 열로 셋팅 > 있으면 Q 

 

Backtracking : 문제를 해결하는 알고리즘 부분적으로 해결을 시도하면서 가능한 모든 해결책을 탐색

~= 미로찾기 , 문제 생기면 마지막전으로가서(재귀함수) 다른 선택을 택함

복잡 but 안되는길은 가지 않으니 불필요한탐색x 

 

 

prone 취약한

 

 

v,i, j,k,l,s,a[99] ; main ()

{

for(scanf(”%d",&s) ;*a-s;v=a[j *=v]-a[i],k=i<s,j+=(v=j<s&&

(!k&&! Iprintf (2+"\n\n%c" - (! 1« ! j ) , " #Q" [l*v? (1* j ) &1:2] ) &&

++1||a[i]<s&&v&&v-i+j&&v+i-j))&&!(l%=s),v||(i==j?a[i+=k]=0: ++a[i])>=s*k&&++a[ — i] )
;
)

// 쉽게 풀어쓰면

#include <stdio.h>

#define N 8  // 퀸의 개수

int board[N];  // 체스판, 각 인덱스는 열을 나타내고, 값은 퀸의 행을 나타냄

// 퀸이 공격하지 않도록 배치할 수 있는지 확인하는 함수
int isSafe(int row, int col) {
    for (int i = 0; i < col; i++) {
        if (board[i] == row || // 같은 행에 다른 퀸이 있음
            board[i] - i == row - col || // 대각선에 다른 퀸이 있음
            board[i] + i == row + col) { // 반대 대각선에 다른 퀸이 있음
            return 0;  // 공격 가능, 불가능
        }
    }
    return 1;  // 안전
}

// 백트래킹을 사용하여 퀸을 배치하는 함수
int solveNQueens(int col) {
    if (col >= N) {   // 모든 퀸을 배치했다면 출력
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i] == j) {
                    printf("Q ");  // 퀸을 출력
                } else {
                    printf(". ");  // 빈 칸을 출력
                }
            }
            printf("\n");
        }
        printf("\n");
        return 1;  // 해법을 찾음
    }

    // 각 행에 대해 퀸을 배치해본다
    for (int row = 0; row < N; row++) {
        if (isSafe(row, col)) {
            board[col] = row;  // 퀸을 배치
            if (solveNQueens(col + 1)) {
                // 다음 열에 대해 재귀적으로 퀸을 배치
                return 1;
            }
            // 배치가 안되면, 현재 위치를 다시 비운다
            board[col] = -1;
        }
    }

    return 0;  // 해법을 찾을 수 없음
}

int main() {
    for (int i = 0; i < N; i++) {
        board[i] = -1;  // 체스판 초기화
    }

    solveNQueens(0);  // 첫 번째 열부터 시작
    return 0;
}