요즘 프로젝트를 진행하면서 버전관리를 위해 Git을 사용중이다.

보통 프로젝트에는 소스코드와 IDE에서 프로젝트를 불러오기 위한 프로젝트 설정 파일들이 포함된다.

 

일단 프로젝트 설정 파일들(이하 프로젝트파일)과 소스코드를 커밋하여 원격저장소에 푸시하고,

그 이후부터 프로젝트파일들은 파일내용이 변해도 무시하기 위해 .gitignore에 등록하였다.

(프로젝트파일들은 컴파일을 하거나, 단순히 IDE에서 불러오거나, 디버깅설정들을 변경하기만 해도 다 변경된다.)

 

하지만 이후에 프로젝트파일들이 변경될 때마다 git status에는 modifed 되었다고 출력되는 것이다.

나는 분명히 .gitignore에 추가했는데 말이다.

그래서 코드 변경내용을 한번에 git add * 하고 싶은데, 프로젝트파일들이 자꾸 변경내역에 떠서 귀찮게 하는 것이다.

구글링 해보니 이미 커밋한 파일들은 tracking되기 때문에 .gitignore에 추가해도 계속 tracking된다고 한다.

 

따라서 .gitignore에 추가할 파일들은 애초에 원격저장소에 올리지 않을 파일들만 추가하거나,

앞으로 변경되지 않을 파일들만 추가하는게 편하겠다.

 

일단 프로젝트 파일들을 변경내역에 안뜨게 하기 위해 어떤 방법들이 있을까 생각해보았다.

 

첫번째로는 아예 저장소에 올리지 않는 것이다. 하지만 이경우의 문제점은 다른 팀원들이 Git에서 코드만 받을 수 있지 프로젝트 파일들은 나에게 또 요청할 것이다. 굉장히 귀찮을 것 같다.

 

두번째로는 저장소에 프로젝트파일을 압축하여 올려 받을사람은 받고, 실제 내가 사용하는 프로젝트파일은 로컬에서 따로 관리한다. 그럴 듯 한 방법이지만 뭔가 깔끔하지는 않다.

 

그래서 구글링을하여 다른 방법이 없을까 찾아보았다.

 

1. 첫번째 솔루션

git rm -r --cached . 
git add .
git commit -am "Remove ignored files"

 

이 방법을 해보니 아예 .gitignore에 등록된 파일중 tracking중인 파일들을 로컬에서는 놔두고 원격저장소에서는 삭제한다. 커밋하고 푸시하면 원격저장소에서 삭제된다. 내가 원하는 방법이 아니었다. 원격저장소에는 그래도 남아있어야 한다.

 

 

 

2. 두번째 솔루션

git update-index --assume-unchanged [path] (해제하려면 git update-index --no-assume-unchanged [path])

ex) git update-index --assume-unchanged Project/*

 

이 방법으로 해보니까 잘 되는 것 같다. 해당 경로에 파일들을 수정해도 수정내역에 뜨지 않는다.

하지만 단점은 로컬에서만 적용된다. 새로 clone한 저장소에서는 적용되지 않는다. 저 커맨드를 다시 입력해줘야 한다.

내가 원하는 것은 아예 원격저장소에서 clone했을 때 프로젝트파일들이 복사는 되지만 수정해도 수정내역에 안 떴으면 좋겠다.

 

그리고 또 하나, git reset --hard를 했을 경우 수정한 파일들의 수정내역이 날라가는 것 같다.

 

 

 

3. 세번째 솔루션

git update-index --skip-worktree [path] (해제하려면 git update-index --no-skip-worktree [path])

ex) git update-index --skip-worktree Project/*

 

이 방법도 두번째와 마찮가지로 잘 되는 것 같다. 아마도 두번째와 같이 로컬에만 적용될 것 같다.

문제는 이 방법으로 Project의 내용을 수정한 뒤 git reset --hard를 하면 fatal error가 발생한다.

 

git update-index --no-skip-worktree [path] 으로 다시 해제한 뒤 reset을 하면 잘 되는 것 같다.

 

일단은 여기까지 찾아봤는데 다른 방법이 더 있을 수도 있다.

어제 밤에 구글링하다가 sub module을 사용하는 방법이 있다고 스택오버플로우에서 본 것 같은데 어려워서 그냥 넘겼다....

 

 

참고한 스택오버플로우 페이지

https://stackoverflow.com/questions/1274057/how-to-make-git-forget-about-a-file-that-was-tracked-but-is-now-in-gitignore

 

How to make Git "forget" about a file that was tracked but is now in .gitignore?

There is a file that was being tracked by git, but now the file is on the .gitignore list. However, that file keeps showing up in git status after it's edited. How do you force git to completely f...

stackoverflow.com

https://stackoverflow.com/questions/13630849/git-difference-between-assume-unchanged-and-skip-worktree/13631525#13631525

 

Git - Difference Between 'assume-unchanged' and 'skip-worktree'

I have local changes to a file that I don't want to commit to my repository. It is a configuration file for building the application on a server, but I want to build locally with different settings.

stackoverflow.com

https://stackoverflow.com/questions/936249/how-to-stop-tracking-and-ignore-changes-to-a-file-in-git

 

How to stop tracking and ignore changes to a file in Git?

I have cloned a project that includes some .csproj files. I don't need/like my local csproj files being tracked by Git (or being brought up when creating a patch), but clearly they are needed in the

stackoverflow.com

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
interface ILogger
{
    void WriteLog(string log);
}
 
class ConsoleLogger : ILogger
{
    public void WriteLog(string message)
    {
        Console.WriteLine("{0} {1}", DateTime.Now.ToLocalTime(), message);
    }
}
 
ILogger logger = new ConsoleLogger();
logger.WriteLog("Hello, World!");
cs


인터페이스는 인스턴스를 못 만들지만, 참조는 만들 수 있다.

이 참조에 파생 클래스의 객체의 위치를 담을 수 있다.

저작자표시

PSW : Processor Status Word, 16비트 레지스터


범용 레지스터

r0 ~ r7


r5: 프레임 포인터, 환경 포인터

r6: 스택 포인터
r7: 프로그램 카운터


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct proc
{
    char p_stat;    // 상태, NULL인 경우 해당하는 PROC[]를 비었다고 판단
    char p_flag;    // 플래그
    char p_pri;        // 실행 우선순위, 값이 작을수록 우선순위가 높으며, 다음에 실행되기 쉬움
    char p_sig;        // 수신된 시그널
    char p_uid;        // 사용자 ID(정수형)
    char p_time;    // 메모리나스와프 영역에 머물렀던 시간(초)
    char p_cpu;        // CPU를 사용한 누적 시간(tick, 틱)
    char p_nice        // 실행 우선순위를 낮추기 위한 보정 값, 초기값은 0으로 nice 시스템 콜로 사용자가 값을 설정함
    int p_ttyp;        // 프로세스를 실행한 터미널
    int p_pid;        // 프로세스 ID
    int p_ppid        // 부모 프로세스 ID
    int p_addr;        // 할당받은 물리 메모리 어드레스(64바이트 단위)
    int p_size        // 할당받은 메모리 크기(64바이트 단위)
    int p_wchan;    // 슬립 상태가 된 이유
    int *p_textp;    // 사용 중인 텍스트 세그먼트
}proc[NPROC];
 
struct user
{
    int u_rsav[2];        // 프로세스가 바뀔 때, 실행 중인 r5, r6를 저장한 곳
    int u_fsav[25];        // PDP-11/40 환경에서는 사용하지 않음
    char u_segflg;        // 파일을 읽고 쓸 때 사용하는 플래그
    char u_error;        // 에러가 발생했을 때 에러코드를 저장함
    char u_uid;            // 실제로 파일을 실행하는 사용자 ID(effective user id)
    char u_gid;            // 실제로 파일을 실행하는 사용자 그룹 ID(effective group id)
    char u_ruid;        // 실행될 때 사용자 ID(real user id)
    char u_rgid;        // 실행될 때 그룹 ID(real group id)
    int u_procp;        // 이 user 구조체에 대응된 proc[] 엔트리를 가리킴
    char *u_base;        // 파일을 읽고 쓸 때 매개변수를 넘겨 줄 때 사용함
    char *u_count;        // 파일을 읽고 쓸 때 매개변수를 넘겨 줄 때 사용함
    char *u_offset[2];    // 파일을 읽고 쓸 때 매개변수를 넘겨 줄 때 사용함
    int *u_cdir;            // 현재 디렉터리의 inode[] 엔트리
    char u_dbuf[DIRSIZ];// namei()가 사용하는 작업영역, 파일, 디렉터리명 등을 저장함
    char *u_dirp;        // 사용자 프로그램, 혹은 커널 프로그램에서 가리키는 파일의 경로를 읽을 때 사용함
    struct {        
        int u_ino;        // u_ino는 inode 번호, u_name은 파일이나, 디렉터리를 나타냄
        char u_name[DIRSIZ];
    }u_dent;            // namei()가 사용된 작업 영역, 디렉터리 엔트리가 저장됨
    int *u_pdir;            // namei()에 대상되는 파일, 디렉터리의 부모 디렉터리를 저장함
    int u_uisa[16];        // 사용자 PAR의 값
    int u_uisd[16];        // 사용자 PDR의 값
    int u_ofile[NOFILE};    // 이 프로세스가 오픈한 파일
    int u_arg[5];        // 사용자 프로그램에서 시스템 콜로 매개변수를 전달할 때 사용함
    int u_tsize;        // 텍스트 세그먼트 크기(64바이트 단위)
    int u_dsize;        // 데이터 영역 크기(64바이트 단위)
    int u_ssize;        // 스택 영역 크기(64바이트 단위)
    int u_sep;            // PDP-11/40 환경에서는 기본값이 0
    int u_qsav[2];        // 시스템 콜을 처리 중에 시그널 처리가 발생했을 때 사용함. r5, r6를 저장하는 곳
    int u_ssav[2];        // 스와프 아웃 처리로 user.u_rsavp[]값이 부정되었을 때 사용함. r5, r6를 저장하는 곳
    int u_signal[NSIG];    // 시그널을 수신했을 때 동작 설정을 위해서 사용함
    int u_utime;        // 사용자 모드로 CPU를 사용한 시간(tick)
    int u_stime;        // 커널 모드로 CPU를 사용한 시간(tick)
    int u_cutime[2];        // 자식 프로세스가 사용자 모드로 사용한 시간(tick)
    int u_cstime[2];        // 자식 프로세스가 커널 모드로 사용한 CPU 시간(tick)
    int *u_ar0;            // 시스템 콜 처리 시 사용자 프로세스의 범용레지스터나 PSW 조작을 할 떄 사용함
    int u_prof[4];        // 프로파일용, 이 책에서는 다루지 않음
    char u_intflg;        // 시스템 콜 처리 중에 시그널 처리가 발생했는지 판단하는 플래그
}u;
cs


저작자표시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#define N 12
 
int n;
int dp[N + 1];
 
int main()
{
    scanf("%d", &n);
 
    // dp[n] = (n - 1) * (dp[n - 2] + dp[n - 1])
 
    dp[2] = 1;
    for (int i = 3; i <= N; i++)
        dp[i] = (i - 1) * (dp[i - 2] + dp[i - 1]);
 
    printf("%d\n", dp[n]);
 
    return 0;
}
cs


저작자표시




저작자표시

Chapter 01 C언어 기반의 C++


01-1. printf와 scanf를 대신하는 입출력 방식


- printf 대신 cout, scanf 대신 cin을 사용한다.

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
 
int main()
{
    int num = 20;
    std::cout << "Hello World!" << std::endl;
    std::cout << "Hello " << "World!" << std::endl;
    std::cout << num << ' ' << 'A';
    std::cout << ' ' << 3.14 << std::endl;
    return 0;
}
cs



01-2 함수오버로딩


- 함수의 매개변수의 자료형 또는 개수가 다를 때, 동일한 이름의 함수정의를 허용하는 것을 말한다.

- 함수 오버로딩이 가능 하려면 매개변수의 자료형 또는 개수가 달라야 한다.



01-3 매개변수의 디폴트 값


- 매개변수에 디폴트 값이 설정되어 있으면, 함수호출 시 인자를 전달하지 않으면 디폴트 값이 전달된다.

- 매개변수에 디폴트 값이 설정되어 있으면, 선언된 매개변수의 수보다 적은 수의 인자전달이 가능하다. 그리고 전달되는 인자는 왼쪽에서부터 채워져 나가고, 부족분은 디폴트 값으로 채워진다.

- 함수의 원형을 별도로 선언하는 경우, 매개변수의 디폴트 값은 함수의 원형 선언에만 위치시켜야 한다.

- 일부분만 디폴트 값을 지정할 수도 있다. 하지만 반드시 오른쪽 매개변수의 디폴트 값부터 채우는 형태로 정의해야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
 
// 함수 원형을 별도로 선언하는 경우, 디폴트 값은 함수의 원형 선언에'만' 위치시켜야 한다.
// 매개변수에 전달되는 인자는 왼쪽부터 채워져 나가고, 부족분은 디폴트 값으로 채워진다.
int BoxVolume(int length, int width = 1, int height = 1);    
 
int main()
{
    cout << "[3, 3, 3] : " << BoxVolume(3, 3, 3) << endl;
    cout << "[5, 5, D]" << BoxVolume(5, 5) << endl;
    cout << "[7,D,D]" << BoxVolume(7) << endl;
//    cout << "[D,D,D]" << BoxVolume() << endl;    // 모든 매개변수에 디폴트 값이 지정된 것이 아니므로, 에러
    return 0;
}
 
int BoxVolume(int length, int width, int height)
{
    return length * width * height;
}
cs


1-4 인라인(inline) 함수


1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
 
inline int SQUARE(int x)
{
    return x * x;
}
 
int main()
{
    std::cout << SQUARE(5) << std::endl;
    std::cout << SQUARE(12) << std::endl;
    return 0;
}
cs


- 매크로를 이용한 함수의 인라인화는 전처리기에 의해서 처리, 키워드 inline을 이용한 함수의 인라인화는 컴파일러에 의해서 처리된다.

- 따라서 컴파일러는 함수의 인라인화가 성능에 해가 된다고 판단할 경우, 키워드를 무시하기도 하고 필요한 경우 일부 함수를 임의로 인라인 처리하기도 한다.

- 템플릿을 이용하면 자료형에 의존적이지 않은 함수를 만들 수 있다.


01-5 이름공간(namespace)에 대한 소개

이름충돌을 막기 위해 namespace를 만들고 함수나 변수를 선언하여 사용한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
 
// BestComImpl이라는 namespace 안에 함수 SimpleFunc를 정의
namespace BestComImpl
{
    void SimpleFunc()
    {
        std::cout << "BestCom이 정의한 함수" << std::endl;
    }
}
 
// ProgComImpl이라는 namespace 안에 함수 SimpleFunc를 정의
namespace ProgComImpl
{
    void SimpleFunc()
    {
        std::cout << "ProgCom이 정의한 함수" << std::endl;
    }
}
 
// ::을 가리켜 범위지정 연산자(scope resolution operator라 한다.
int main()
{
    BestComImpl::SimpleFunc();    
    ProgComImpl::SimpleFunc();    
    return 0;
}
cs


연산자 :: 을 가리켜 '범위지정 연산자'라 한다. namespace를 지정할 때 사용한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
 
// BestComImpl이라는 namespace 안에 함수 SimpleFunc를 선언
namespace BestComImpl
{
    void SimpleFunc();
}
 
// ProgComImpl이라는 namespace 안에 함수 SimpleFunc를 선언
namespace ProgComImpl
{
    void SimpleFunc();
}
 
// ::을 가리켜 범위지정 연산자(scope resolution operator라 한다.
int main()
{
    BestComImpl::SimpleFunc();
    ProgComImpl::SimpleFunc();
    return 0;
}
 
// BestComImpl namespace에 선언된 함수 SimpleFunc를 정의
void BestComImpl::SimpleFunc()
{
    std::cout << "BestCom이 정의한 함수" << std::endl;
}
 
// ProgComImpl namespace에 선언된 함수 SimpleFunc를 정의
void ProgComImpl::SimpleFunc()
{
    std::cout << "ProgCom이 정의한 함수" << std::endl;
}
cs


namespace 기반에서 함수의 선언과 정의를 구분한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
 
// BestComImpl이라는 namespace 안에 함수 SimpleFunc를 선언
namespace BestComImpl
{
    void SimpleFunc();
}
 
namespace BestComImpl
{
    void PrettyFunc();
}
 
// ProgComImpl이라는 namespace 안에 함수 SimpleFunc를 선언
namespace ProgComImpl
{
    void SimpleFunc();
}
 
// ::을 가리켜 범위지정 연산자(scope resolution operator라 한다.
int main()
{
    BestComImpl::SimpleFunc();
    return 0;
}
 
// BestComImpl namespace에 선언된 함수 SimpleFunc를 정의
void BestComImpl::SimpleFunc()
{
    std::cout << "BestCom이 정의한 함수" << std::endl;
    PrettyFunc();                // 동일 namespace
    ProgComImpl::SimpleFunc();    // 다른 namespace
}
 
// BestComImpl namespace에 선언된 함수 PrettyFunc를 정의
void BestComImpl::PrettyFunc()
{
    std::cout << "So Pretty!!" << std::endl;
}
 
// ProgComImpl namespace에 선언된 함수 SimpleFunc를 정의
void ProgComImpl::SimpleFunc()
{
    std::cout << "ProgCom이 정의한 함수" << std::endl;
}
cs


같은 namespace에 정의된 함수를 호출할 때에는 namespace를 명시할 필요가 없다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
 
namespace Hybrid
{
    void HybFunc()
    {
        std::cout << "So simple function!" << std::endl;
        std::cout << "In namespace Hybrid!" << std::endl;
    }
}
 
int main()
{
    using Hybrid::HybFunc;    // HybFunc 를 Hybrid namespace에서 찾으라는 일종의 선언
    HybFunc();
    return 0;
}
cs


using 키워드를 이용하여 HybFunc 함수를 호출할 때 namespace 범위 지정 없이 그냥 호출 할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
 
using std::cin;
using std::cout;
using std::endl;
 
int main()
{
    int num = 20;
 
    cout << "Hello World!!" << endl;
    cout << "Hello " << "World!" << endl;
    cout << num << ' ' << 'A';
    cout << ' ' << 3.14 << endl;
    return 0;
}
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
 
using namespace std;
 
int main()
{
    int num = 20;
 
    cout << "Hello World!!" << endl;
    cout << "Hello " << "World!" << endl;
    cout << num << ' ' << 'A';
    cout << ' ' << 3.14 << endl;
    return 0;
}
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
using namespace std;
 
namespace AAA
{
    namespace BBB
    {
        namespace CCC
        {
            int num1;
            int num2;
        }
    }
}
 
int val = 100; // 전역변수
 
void SimpleFunc()
{
    int val = 20;    // 지역변수
    val += 3;        // 지역변수 val의 값 3 증가
    ::val += 7;        // 전역변수 val의 값 7 증가
    cout << val << endl;
    cout << ::val << endl;
}
 
int main()
{
    AAA::BBB::CCC::num1 = 20;
    AAA::BBB::CCC::num2 = 30;
 
    namespace ABC = AAA::BBB::CCC;
 
    cout << ABC::num1 << endl;
    cout << ABC::num2 << endl;
    SimpleFunc();
    return 0;
}
cs




저작자표시

중복조합(重複組合, combination with repetition)은 서로 다른 n개의 원소에서 중복을 허락하여 k개를 뽑는 경우의 수이다. 


기호로는 nHk로 표기하며, 그 값은 nHk = n+k-1Ck 이다.


예를 들어, 세개의 문자 A,B,C에서 중복을 허용하여 5개를 뽑는 경우의 수는 3H5 = 7C5 = 21이므로 21가지가 된다.


공식을 유도하자면, 중복조합 nHk는 k개의 원소들을 중복을 허용하여 순서에 상관없이 나열하는 것으로 볼 수 있다.


따라서 k개의 빈칸에 중복을 허용하여 n개의 원소(n개 종류의 원소)를 넣는 개수를 구하는 문제로 생각할 수 있다.


이 떄, n가지의 원소를 순서에 상관없이 나열해야 하므로, n - 1개의 칸막이를 두고 나열하는 것으로 생각할 수 있다.


예를 들어, A,B,C 세개의 문자에서 중복을 허용하여 5개를 뽑는 경우의 수를 생각해보자.


1.  A A A A A / /

2.  A A A A / B

3.  A A A / B B /

4.  A A / B B B /

5.  A / B B B B /

6.  B B B B B / /

7.  / B B B B / C

8.  / B B B / C C 

9.  / B B / C C C

10. / B / C C C C 

11. / / C C C C C

12. A A A A / / C

13. A A A / / C C

14. A A / / C C C 

15. A / / C C C C

16. A / B / C C C

17. A / B B / C C

18. A / B B B / C

19. A A / B / C C

20. A A A / B / C

21. A A / B B / C


이런식으로 총 k + n - 1 개의 칸에서 n - 1개의 칸막이를 배치하는 경우의 수로 생각할 수 있다.

따라서 nHk = n+k-1Cn-1 = n+k-1Ck가 된다. 따라서 위의 예는 n = 3이고, k = 5 이므로 3H5 = 3+5-1C5 = 7C5 = 7C2 = 21이 된다.   





저작자표시

1
2
3
4
const int num = 10;         // 변수 num을 상수화
const int* ptr1 = &val1;     // 포인터 ptr1을 이용해서 val1의 값을 변경할 수 없음
int* const ptr2 = &val2;     // 포인터 ptr2가 상수화 됨, ptr2의 값을 변경할 수 없음
const int* const ptr3 = &val3;    // 포인터 ptr3가 상수화 되었으며, ptr3를 이용해서 val3의 값을 변경할 수 없음
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
 
int val1 = 10;
int val2 = 20;
int main()
{
    const int* ptr1 = &val1;
    int* const ptr2 = &val2;
 
//    (*ptr1) = 20;    // 포인터 ptr1을 이용해서 val1의 값을 변경할 수 없음
    (*ptr2) = 30;
//    ptr2 = &val1;    // ptr2가 가리키는 주소를 변경할 수 없음, 즉 ptr2의 값을 변경할 수 없음
    printf("%d\n", val2);
}
cs


저작자표시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// Heap 정렬(내림차순)
 
#include <stdio.h>
#define N 100
 
int n;
int data[N + 1];
int heap[N + 1];
 
void input()
{
    int i;
    scanf("%d", &n);
    for (i = 0; i<n; i++)
        scanf("%d", &data[i]);        // n개의 데이터 입력
}
 
void process()
{
    int i, x;
    int heap_cnt = 1;
 
    for (i = 0; i < n; i++)
    {
        heap[heap_cnt] = data[i];
        x = heap_cnt;
 
        while (x > 1)
        {
            if (heap[x / 2] > heap[x])    // 부모가 자식보다 클 때
            {
                int temp = heap[x / 2];
                heap[x / 2] = heap[x];
                heap[x] = temp;
                x = x / 2;            // 포지션을 부모 자리로 변경
            }
            else break;
        }
        heap_cnt++;
    }
 
    printf("Heap Tree : ");
    for (i = 1; i <= n; i++)
        printf("% d", heap[i]);
    printf("\n");
 
    printf("Output : ");
    for (i = 0; i<n; i++)
    {
        printf("%d ", heap[1]);        // 첫 번째 데이터
        heap_cnt--;                    // 제일 마지막 보다 한 칸 뒤의 위치를 가리키므로 -1
        heap[1] = heap[heap_cnt];    // 제일 첫 번째 칸에다 제일 마지막 자식을 저장
        heap[heap_cnt] = 0;            // 마지막 칸을 비움
        x = 1;                        // 위치는 1
        while (x * 2 < heap_cnt)        // 제일 마지막 자식 까지
        {
            if (heap[x] <= heap[2 * x] && (heap[x] <= heap[2 * x + 1] || x * 2 + 1 >= heap_cnt))        // 부모가 자식보다 작다면
                break;
            else if (heap[x * 2] <= heap[x] && (heap[x * 2] <= heap[x * 2 + 1] || x * 2 + 1 >= heap_cnt))                        // 왼쪽 자식이 제일 작을 때
            {
                int temp = heap[x];
                heap[x] = heap[x * 2];
                heap[x * 2] = temp;                // 제일 작은 자식을 부모자리로 교환
                x = x * 2;
            }
            else // 오른쪽 자식이 제일 작을 때
            {
                int temp = heap[x];
                heap[x] = heap[x * 2 + 1];
                heap[x * 2 + 1] = temp;
                x = x * 2 + 1;
            }
        }
 
    }
    printf("\n");
 
}
 
 
int main()
{
    input();
    process();
}
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#define N 10
 
int heap[N + 1];
int sz = 1;
 
void push(int x)
{
    int i = sz++;
 
    while (i > 1)
    {
        // 부모 노드
        int p = i / 2;
 
        // 값의 역전 체크, 없으면 break
        if (heap[p] <= x) break;
 
        heap[i] = heap[p];
        i = p;
    }
    heap[i] = x;
}
 
int pop()
{
    // 최소 값
    int ret = heap[1];
 
    // 루트로 가져오는 값
    int x = heap[--sz];
 
    // 루트보다 작을 동안 값을 체크
    int i = 1;
    while (i * 2 < sz)
    {
        // 자식들을 비교
        int a = i * 2; 
        int b = i * 2 + 1;
        if (b < sz && heap[b] < heap[a]) a = b;
 
        // 더 이상 역전이 없다면 break
        if (heap[a] >= x) break;
 
        // 자식의 값을 저장
        heap[i] = heap[a];
        i = a;
    }
    heap[i] = x;
 
    return ret;
}
cs


저작자표시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <stdio.h>
#include <malloc.h>
 
typedef struct Node
{
    int Data;
    struct Node* NextNode;
}Node;
 
/*  노드 생성 */
Node* SLL_CreateNode(int NewData)
{
    Node* NewNode = (Node*)malloc(sizeof(Node));
 
    NewNode->Data = NewData;  /*  데이터를 저장한다. */
    NewNode->NextNode = NULL; /*  다음 노드에 대한 포인터는 NULL로 초기화 한다. */
 
    return NewNode;/*  노드의 주소를 반환한다. */
}
 
/*  노드 소멸 */
void SLL_DestroyNode(Node* Node)
{
    free(Node);
}
 
/*  노드 추가 */
void SLL_AppendNode(Node** Head, Node* NewNode)
{
    /*  헤드 노드가 NULL이라면 새로운 노드가 Head */
    if ((*Head) == NULL)
    {
        *Head = NewNode;
    }
    else
    {
        /*  테일을 찾아 NewNode를 연결한다. */
        Node* Tail = (*Head);
        while (Tail->NextNode != NULL)
        {
            Tail = Tail->NextNode;
        }
 
        Tail->NextNode = NewNode;
    }
}
 
/*  노드 삽입 */
void SLL_InsertAfter(Node* Current, Node* NewNode)
{
    NewNode->NextNode = Current->NextNode;
    Current->NextNode = NewNode;
}
 
void  SLL_InsertNewHead(Node** Head, Node* NewHead)
{
    if (Head == NULL)
    {
        (*Head) = NewHead;
    }
    else
    {
        NewHead->NextNode = (*Head);
        (*Head) = NewHead;
    }
}
 
void SLL_InsertBefore(Node** Head, Node* Current, Node* NewHead)
{
    if ((*Head) == Current)
    {
        SLL_InsertNewHead(Head, NewHead);
    }
    else
    {
        Node *BeforeCurrent = *Head;
        while (BeforeCurrent != NULL && BeforeCurrent->NextNode != Current)
        {
            BeforeCurrent = BeforeCurrent->NextNode;
        }
 
        if (BeforeCurrent != NULL)
        {
            NewHead->NextNode = Current;
            BeforeCurrent->NextNode = NewHead;
        }
    }
}
 
/*  노드 제거 */
void SLL_RemoveNode(Node** Head, Node* Remove)
{
    if (*Head == Remove)
    {
        *Head = Remove->NextNode;
    }
    else
    {
        Node* Current = *Head;
        while (Current != NULL && Current->NextNode != Remove)
        {
            Current = Current->NextNode;
        }
 
        if (Current != NULL)
            Current->NextNode = Remove->NextNode;
    }
    
    //SLL_DestroyNode(Remove);
}
 
/*  노드 탐색 */
Node* SLL_GetNodeAt(Node* Head, int Location)
{
    Node* Current = Head;
 
    while (Current != NULL && (--Location) >= 0)
    {
        Current = Current->NextNode;
    }
 
    return Current;
}
 
/*  노드 수 세기 */
int SLL_GetNodeCount(Node* Head)
{
    int   Count = 0;
    Node* Current = Head;
 
    while (Current != NULL)
    {
        Current = Current->NextNode;
        Count++;
    }
 
    return Count;
}
 
void SLL_DestroyAllNodes(Node** List)
{
 
}
 
int main()
{
    return 0;
}
cs


저작자표시

+ Recent posts

티스토리툴바