근데 왜 EUC-KR은 쓰면 깨지는 걸까?

EUC-KR

• ASCII 인코딩 방식의 확장
  • ASCII 인코딩 방식은 원래 영어만 고려한 1byte 길이의 인코딩 방식
  • 한글을 사용할 수 있도록 만든 2byte 길이의 국가 언어 코드

하지만 이 EUC-KR 방식은 우리나라에서만 쓸 수 있도록 만든 코드. 공통으로 사용되는 인코딩 방식이 아니므로 다른 환경에서는 한글이 깨지는 경우가 발생한다. 이를 해결하기 위해 새롭게 개발된 인코딩 방식이 UTF-8 용량이 더 작은 EUC-KR 방식을 선호하는 곳도 많았지만, 현재는 용량보다는 글로벌 환경을 고려해야 하므로 UTF-8을 많이 쓴다.

UTF-8

• 한글을 지원하는 3byte 크기의 국가 언어 코드

출처:https://suzxc2468.tistory.com/180

방법은

Windows > Preferences 에서 encod까지만 검색하면 나오는 아이들이 있다. 이 아이들에서 ISO-8859~~ 이거나 EUC-KR 로 설정되어 있는 모든 아이들을 UTF-8로 변경해주면 된다. (참고로 UTF-8은 ISO-10646/Unicode)

정리

1. Windows > Preferences 에서 encod까지만 검색
2. General

• Content Types > Java Class File : UTF-8 하고 Update
• Content Types > Text > JSP/XML/JavaPropertyFiles : UTF-8 하고 Update
• Workspace에서 UTF-8 하고 Update

3. Web

• CSS : UTF-8 하고 Update
• HTML : UTF-8 하고 Update
• JSP : UTF-8 하고 Update

총 8개를 UTF-8로 설정해줘야함.

이렇게 해줬는데도 JSP 파일은 UTF-8로 변경될 생각을 안한다.

알고보니...... 위의 방법은 파일을 생성하기 전 초기 셋팅 작업이었던 것. 이미 생성한 프로젝트에 대해서 UTF-8로 변경하는 방법은 Alt + Enter > Resources > Others를 UTF-8로 변경

이미 만들어놓은 파일의 인코딩 방식을 UTF-8로 변경하면 이처럼 다 깨진다는 부작용이 있다.

미리 백업해두자

출처 : https://yakongs.tistory.com/entry/%EC%9D%B4%ED%81%B4%EB%A6%BD%EC%8A%A4Eclipse-%ED%95%9C%EA%B8%80-%EA%B9%A8%EC%A7%90-UTF-8-%EC%9D%B8%EC%BD%94%EB%94%A9-%EC%84%A4%EC%A0%95-%EC%9D%B8%EC%BD%94%EB%94%A9-%EB%B3%80%EA%B2%BD

참고 : https://sayit.tistory.com/entry/UTF8-for-Eclipse

개발환경은 프레임워크 : 스프링 언어 : java jdk1.8 DB : MySQL DB연동은

1. 프레임워크 없이 연동
2. MyBatis로 변경
3. JPA로 변경

1. 프레임워크 없이 연동

fgets : 문자열 공백포함 입력

문자열 공백포함 입력방법

1. scanf("%[^\n]s", str);
2. fgets(str, sizeof(str), stdin);

/* 문자열 길이 카운트 */
    while (idx <= 1000)
    {
        if (str[idx] != '0')
        {
            cnt++;
        }
        else
        {
            break;
        }
        idx++;
    }
    cnt--;

    /* 동적할당 */
    char **tails = (char**)malloc(sizeof(char*) * cnt); /* 높이동적할당 */
    idx = 0;
    while (idx < cnt) /* 너비동적할당 */
    {
        tails[idx] = (char*)malloc(sizeof(char) * cnt);
        idx++;
    }

    /* 값넣어주기 */
    idx = 0;
    while(idx < cnt)
    {
        int idx2 = idx;
        while(idx2 < cnt)
        {
            tails[idx][idx2] = str[idx2];
            idx2++;
        }
        idx++;
    }

    /* 배열 출력 */
    idx = 0;
    while(idx < cnt)
    {
        int idx2 = idx;
        while(idx2 < cnt)
        {
            //printf("%c", tails[idx][idx2]);
            write(1, &tails[idx][idx2], 1);
            idx2++;
        }
        idx++;
        write(1, "\n", 1);
    }

    /* 동적 할당 해제 */
    idx = 0;
    while(idx < cnt)
    {
        free(tails[idx]);
        idx++;
    }
    free(tails);

순서는

1. WSL 설치
2. 환경설정
3. WSL용 리눅스배포판 설치

1. WSL 설치 마이크로소프트 스토어(Microsoft store)에서 terminal 검색 후 windows terminal 설치

2. 환경설정 windows terminal을 관리자 권한으로 실행 후

dism.exe /online /enable-feature /featurename:Microsoft-Windows-Subsystem-Linux /all /norestart

dism.exe /online /enable-feature /featurename:VirtualMachinePlatform /all /norestart

두 명령어를 실행해준다.

WSL을 관리하기 위해서는 wsl 명령어를 사용해야하는데 동작하지 않는다. 재부팅을 해준다.

3. WSL용 리눅스 배포판을 설치 WSL을 사용하려면 리눅스 배포판이 있어야한다. 또 마이크로소프트 스토어에서 우분투를 검색한다.

설치한다. 설치가 완료되면 우분투를 실행한다.

꽤 오래걸린다.

리눅스 사용자 이름과 패스워드를 지정해준다.

이후 다시 wsl 명령어를 사용하면 동작한다. 이러면 설치가 잘 되었다.

(+) WSL에서 chmod가 작동하지 않는다. 아래 코드를 입력해주자

sudo umount /mnt/c
sudo mount -t drvfs C: /mnt/c -o metadata

그래프가 다 이어질 수도 있고 중간에 끊길 수도 있다. 이어지다가 끊기면 하나의 연결요소가 되는 것이다. 이 연결요소가 몇 개 있는지를 출력하는 문제이다.

DFS 함수는 연결된 요소들이 있으면 연속해서 호출된다. 그리고 더 이상 방문기록 없는 연결된 요소가 없으면 끝난다. 이어지다가 끊긴 것으로, 연결 요소 하나가 만들어졌다. 그리고 main()으로 돌아오는데, main()에서 인접리스트 요소 중 방문기록이 없으면 또 실행한다. 즉 main()에서 DFS를 실행할 때 연결요소 개수가 +1 되는 것이다.

BFS 함수는 큐가 빌 때까지 탐색한다. 즉 연결된 노드들을 탐색하고 끝나는 것이다. 이것도 DFS와 마찬가지로 더 이상 방문기록 없는 연결된 요소가 없으면 끝이나서 main()으로 돌아온다. 이때도 main()에서 BFS를 실행해줄 때 연결요소 개수가 +1 되는 것이다.

DFS 풀이

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

vector<int> vect[1001]; //인접리스트
int visited[1001];      //방문기록
int N, M;

/* DFS : 방문기록 남기는 용도 */
void DFS(int vertex)
{
    visited[vertex] = 1;
    for (int i = 0; i < vect[vertex].size(); i++) //최댓값 주의 : 벡터 그 원소에 해당하는 크기만큼 돌아야함
    {
        int idx = vect[vertex][i];
        if (visited[idx] == 0)
        {
            DFS(idx);
        }
    }
}

int main()
{
    int u, v;
    int cnt = 0;
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        vect[u].push_back(v);
        vect[v].push_back(u); //무방향 그래프이기 때문
    }

    for (int i = 1; i <= N; i++) //빠짐없이 탐색하기 위해
    {
        if (visited[i] == 0)
        {
            cnt++;
            DFS(i);
        }
    }
    cout << cnt << "\n";
}

BFS 풀이

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

vector<int> vect[1001];
int visited[1001];
int N, M;

void BFS(int start)
{
    queue<int> q;
    q.push(start);
    visited[start] = 1;

    while (q.size() != 0)
    {
        // start가 아닌 가장 앞의 값에 인근 정점을 push 해줘야함
        int current = q.front();
        q.pop();
        for (int i = 0; i < vect[current].size(); i++)
        {
            if (visited[vect[current][i]] == 0)
            {
                visited[vect[current][i]] = 1; 
                q.push(vect[current][i]);
                //BFS는 재귀가 아니라서 큐에 push 해주는 동시에 방문기록 남겨야함.
            }
        }
    }
}

int main()
{
    int cnt = 0; //연결요소 개수 세는 변수
    int u, v;
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        vect[u].push_back(v);
        vect[v].push_back(u);
    }

    //빠짐없이 탐색하기 위해
    for (int i = 1; i <= N; i++)
    {
        if (visited[i] == 0)
        {
            BFS(i);
            cnt++;
        }
    }
    cout << cnt;
}

저번에 인접행렬을 사용해봤으니 이번엔 인접리스트를 사용해보자. 이번엔 visited에 방문했다는 표시 1 말고 색깔을 넣을 것이다. 빨간색이면 RED(2), 파란색이면 BLUE(3)를 넣었다.

• 인접리스트, 방문기록, 노드 수, 간선 수를 전역에다 선언해준다. 인접리스트는 vector로 만들어주었다.
• main()에서 테스트케이스를 입력받고 각 테스트케이스별 노드 수, 간선 수와 각각 노드를 입력받았다. 그리고 인접리스트에 넣어줌

1. DFS

• 빠짐없이 방문하기 위해서 1부터 N까지 다 돌려줌 대신 방문기록 있는 것들만 DFS 돌려줌
• 처음 방문하는 점이면 방문기록에 RED 넣어줌
• 연결된 점 탐색하러 가는데 연결된 점도 방문한 적이 없다? 그럼 여기서 조건을 걸어줌. 탐색 시작한 노드가 RED라면 연결된 점에는 BLUE를, BLUE라면 RED를 넣어줌.
• 그리고 요소별로 방문. 이것을 반복함(재귀)

2. BFS

• 큐 만들어주고 시작점 큐에 push
• 큐 맨 앞 값 복사해주고 큐 pop
• 큐 맨 앞 값이 RED다? 그러면 인접리스트에 연결된 노드들은 모두 BLUE로 넣어줌. (BLUE면 RED로)

• check()함수로 이분그래프 검사를 할 것이다. 인접한 노드와 시작점 노드가 색이 같으면 이분그래프 X. 한번이라도 같은게 있으면 바로 리턴해버림
• 그리고 중요한 것이 있다. 이 문제는 테스트케이스가 있으므로 인접리스트와 방문기록을 여러 번 써야한다는 것. 그러기 위해서는 초기화 작업이 필요하므로 memset을 사용해준다.

DFS 풀이

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

#define RED 2
#define BLUE 3

vector<int> vect[20001]; //인접리스트
int visited[20001];      //방문기록
int V, E;

/* DFS 실행 */
void DFS(int start)
{
    //방문안한 점이면 RED
    if (visited[start] == 0)
        visited[start] = RED;

    //연결된 점들 방문
    for (int i = 0; i < vect[start].size(); i++)
    {
        int idx = vect[start][i];
        if (visited[idx] == 0) //방문 안한 점이면
        {
            //요소에 방문기록 남김(색칠하기)
            if (visited[start] == RED)
                visited[idx] = BLUE;
            else if (visited[start] == BLUE)
                visited[idx] = RED;

            //요소별로 방문
            DFS(idx);
        }
    }
}

/* 이분그래프 검사 */
int check()
{
    //인접한 노드와 색이 같으면 이분그래프 X
    for (int i = 1; i <= V; i++)
    {
        //연결된게 자기자신 뿐일 경우엔 size가 0이라서 돌아가지 않는다.
        for (int j = 0; j < vect[i].size(); j++)
        {
            int idx = vect[i][j];
            if (visited[i] == visited[idx]) 
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    int T;    //테스트케이스
    int u, v; //노드 담을 변수

    cin >> T;
    while (T--)
    {
        cin >> V >> E;
        for (int i = 0; i < E; i++)
        {
            cin >> u >> v;
            vect[u].push_back(v);
            vect[v].push_back(u);
        }


        //빠짐없이 방문하기 위해 1부터 원소 개수까지 다 방문해봄
        for (int i = 1; i <= V; i++)
        {
            if (visited[i] == 0)
                DFS(i);
        }

        if (check() == 0) //이분그래프인지 검사
            cout << "NO\n";
        else
            cout << "YES\n";

        memset(visited, 0, sizeof(visited));
        memset(vect, 0, sizeof(vect));
    }
}

BFS 풀이

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

#define RED 1
#define BLUE 2

vector<int> vect[20001];
int visited[20001];
int V, E;

void BFS(int start)
{
    visited[start] = RED;
    queue<int> q;
    q.push(start);

    while(q.size()!=0) //큐가 빌 때 까지 반복(전체)
    {
        int now = q.front();
        q.pop();
        for(int i=0; i<vect[now].size(); i++)
        {
            if(visited[vect[now][i]] == 0)
            {
                q.push(vect[now][i]);

                if(visited[now] == RED) visited[vect[now][i]] = BLUE;
                else if(visited[now] == BLUE) visited[vect[now][i]] = RED;
            }
        }

    }

}

bool check()
{
    for (int i = 1; i <= V; i++)
    {
        for (int j = 0; j < vect[i].size(); j++)
        {
            if (visited[i] == visited[vect[i][j]])
                return false;
        }
    }
    return true;
}

int main()
{
    int K, u, v;
    cin >> K;

    while (K--)
    {
        cin >> V >> E;
        for (int i = 0; i < E; i++)
        {
            cin >> u >> v;
            vect[u].push_back(v);
            vect[v].push_back(u);
        }

        //빠짐없이 방문하기 위해 노드 개수만큼 BFS 돌려줘야함
        for (int i = 1; i <= V; i++)
        {
            if (visited[i] == 0)
            {
                BFS(i);
            }
        }

        //이분그래프 검사
        if (check())
            cout << "YES\n";
        else
            cout << "NO\n";

        memset(visited, 0, sizeof(visited));
        memset(vect, 0, sizeof(vect));
    }
}

BFS와 DFS문제는 처음이다. 다른 블로그를 참고하며 풀었다. BFS는 큐 [선입선출 FIFO] DFS는 재귀 + 브루트포스(완전탐색) [후입선출 LIFO] 를 사용한 방식이었다. DFS는 스택을 사용하는 후입선출 방식이다. 재귀를 통해 시스템 스택을 사용한다.

그래프 표현 방식에는 인접 행렬과 인접 리스트가 있다. 인접 행렬은 2차원 배열(행렬) 형태이고 인접 리스트는 vector와 같은 배열 형태이다. 공간복잡도는 인접행렬 O(V^2), 인접리스트 O(V+E) 이고 시간복잡도는 각 노드별로 연결된 모든 노드 탐색 시 인접행렬 O(V), 인접리스트 O(E)이다.

인접리스트는 인접행렬보다 공간복잡도도 작고, 탐색시간도 비교적 빠른편이라서 인접리스트가 많이 쓰인다고 한다. 여기서는 인접행렬을 사용하였다.

• 먼저 DFS, BFS를 수행하기 위해선 그래프(인접행렬)와 방문기록이 필요하다.
• 인접행렬, 방문기록, 노드 수, 간선 수를 전역으로 선언한다.
• 전역으로 선언해주면 자동으로 0으로 초기화된다.
• main()에서 노드, 간선 개수와 시작점을 입력받고 인접행렬에서 입력받은 두 노드가 만나는 곳에 1을 넣어준다. (1 = 연결됨을 의미)
• DFS를 수행하고, 순서대로 출력해준다.
• memset을 이용하여 초기화해준다. memset 사용법
• BFS를 수행하고, 순서대로 출력해주고 끝

1. DFS 방문기록에 넣어주고, 연결된 다른 요소들이 있는데 방문기록이 없을 경우 그 요소에 대해 DFS를 수행하고 이를 반복한다.(재귀) 2. BFS 방문기록에 넣어주고 큐를 생성한다. 큐에 현재노드를 push하고, 큐의 맨 앞 노드를 복사한 다음에 큐에서 지워준다. 복사한 노드와 연결된 다른 노드들이 있을 것이다. 그럼 그 노드들을 큐에 넣어준다. 순서는 상관없다. 그리고 그 노드들도 방문기록에 남겨준다. 이것을 큐가 빌 때까지 반복한다.

뭔가 BFS보다 DFS가 더 쉽게 느껴졌던 것 같다. 큐를 많이 사용해보지 않아서 그런걸까 골고루 적용해보면서 익혀야겠다.

코드

#include <iostream>
#include <queue>    //BFS에서 활용
#include <string.h> //memset 쓰려면 필요
using namespace std;

/* 전역으로 정의 - 자동 0 초기화 */
int arr[1001][1001]; //인접행렬
int visited[1001];   //방문기록
int N, M, V;

/* DFS - 재귀(시스템 스택 사용) (후입선출 LIFO) */
void DFS(int V)
{
    visited[V] = 1;   //시작점 방문기록
    cout << V << " "; //방문한 노드 출력

    for (int i = 1; i <= N; i++)
    {
        if (arr[V][i] == 1 && visited[i] == 0)
        {
            DFS(i); //스택에 i 넣는 셈
        }
        if (i == N)
            return;
    }
}

/* BFS - 큐 사용 (선입선출 FIFO) */
void BFS(int V)
{
    queue<int> q; //큐 생성
    q.push(V);    //시작노드 큐에 넣음

    while (!q.empty())
    {
        int next = q.front(); //큐 맨 앞에 값을 방문
        visited[next] = 1;    //방문기록
        cout << next << " ";  //방문한 노드 출력
        q.pop();              //큐에서 뺌

        //방문했던 노드와 가까운 노드 큐에 넣어줌
        for (int i = 1; i <= N; i++)
        {
            if (arr[next][i] == 1 && visited[i] == 0)
            {
                q.push(i);         //큐에 넣어줌
                visited[i] = 1; // i 점은 미리 방문기록 - 안하면 중복으로 방문할 수도 있다
            }
        }
    }

}

int main()
{
    int u, v;
    cin >> N >> M >> V;

    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        arr[u][v] = 1;
        arr[v][u] = 1; //자리바꿔서도 해주는 이유 : 무방향이기 때문
    }                  //입력 즉시 인접행렬에 넣어줌, 다 돌면 인접행렬 완성

    DFS(V); // DFS 수행

    cout << "\n";                        //개행
    memset(visited, 0, sizeof(visited)); //방문기록 visited 초기화

    BFS(V); // BFS 수행
}

📌참고 https://velog.io/@leobit/%EB%B3%B5%EC%9E%A1%EB%8F%84Complexity

1. fill : 특정 값으로 초기화
2. memset : 0또는 1로 초기화

사용방법

1. fill

필요한 헤더파일 : #include<algorithm> fill(시작주소, 끝주소, 특정 값); -> fill(arr, arr+N, 1);

2. memset

필요한 헤더파일 : #include<string.h> memset(시작주소, 0 또는 1, 배열크기); -> memset(arr, 0, sizeof(arr));

알고리즘 문제를 풀 때는 0으로 초기화 하는 경우가 많아 memset을 자주 사용한다.

캐시

자주 사용되는 데이터를 메모리에서 복사해놓는 임시 저장장소

메모리

프로세스의 메모리 구조

메모리 상에서 힙 영역(낮은주소->높은주소), 스택 영역(높은주소->낮은주소)은 서로 반대로 데이터를 채워 나가서 서로의 영역을 침범할 수도 있다.

• Stack Overflow : 스택이 힙 영역을 침범함
• Heap Overflow : 힙이 스택 영역을 침범함

이 문제는 주목해야할 부분이 있다. 바로 이것

간단하게 생각해보면 N개의 원소를 가지는 배열을 만들어 주고 배열에 원소를 입력 받아서 sort() 해준 후 출력하면 된다. 근데 이렇게 하면 메모리가 초과가 난다. N은 1부터 1000만까지다. int 배열이니까 4byte x 1000만 = 40MB다. 8MB? 어림도 없다.

그럼 어떻게 해야할까 문제에서 제한을 준게 또 하나 있다. N개의 수를 입력받을 때 입력받는 수는 10000보다 작다는 것이다. 크기가 10001인 배열을 만들고, 입력 값이 idx와 동일하면 value로 개수를 +1 해서 넣어주는 것이다. 풀이는 아래와 같다.

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, idx;
    int cnt[10001] = {};
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        cin >> idx;
        cnt[idx] += 1;
    }

    for (int i = 1; i <= 10000; i++)
    {
        for (int j = 1; j <= cnt[i]; j++)
        {
            cout << i << "\n";
        }
    }
}

벡터의 자료형으로 구조체를 사용했다. 국어 점수를 내림차순으로 정렬, 국어 점수가 같으면 영어 점수를 오름차순으로 정렬, 영어 점수가 같으면 수학 점수를 내림차순으로 정렬하는 문제다.

sort()와 비교함수 compare()을 사용해서 문제를 풀었다.

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

struct student
{
    int kor;
    int eng;
    int math;
    string name;
};

//전체 비교
bool compare(const student& now, const student& last)
{
    if(now.kor != last.kor) return now.kor > last.kor;
    else 
    {
        if(now.eng != last.eng) return now.eng < last.eng;
        else 
        {
            if(now.math != last.math) return now.math > last.math;
                return now.name < last.name;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin>>N;

    vector<student> students(N);

    //입력
    for(int i=0; i<N; i++)
        cin >> students[i].name >> students[i].kor >> students[i].eng >> students[i].math;

    //정렬
    sort(students.begin(), students.end(), compare);

    //출력
    //cout<<"answer==\n";
    for(int i=0; i<N; i++)
        cout << students[i].name<< "\n";
}

이 문제는 두 가지 방법으로 풀었다. 답을 제출하면 계속 틀렸습니다가 나왔고 내가 무슨 부분을 놓치고 있는지 잘 모르겠더라. 그래서 고민 끝에 질문 게시판에 처음으로 글을 올렸고 어떤 천사 같은 분이 도움을 주셨다. 감사합니다 🙇‍♀️

내가 놓치고 있었던 부분은 조건을 하나 걸어주지 않았던 것이다. 정확히 말하면 sort()를 모르고 썼다.

이 문제를 풀 때 고려해줘야하는 조건은 2개다.

1. 나이 순으로 정렬한다.
2. 나이가 같으면 가입한 순으로 정렬한다.

오류가 났던 코드는 배열에 입력 값을 저장하고 sort()로 나이 순서대로 정렬했다. sort()를 쓰면 나이 순서대로 정렬 되고 같은 나이면 입력한 순서대로 출력하는줄 알았다.

그러나 그것은 아주 큰 오해

sort()는 배열의 두 원소를 비교하는 도구로 사용된다. 그런데 배열의 원소가 한 개가 아니라 지금처럼 여러 개로 묶여있다면? 배열의 x좌표를 주루룩 정렬했다고 치자. 만약 x좌표가 같은 것들이 있을 때, y좌표는 어떤 순서로 정렬될까?

sort()는 첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력한다는 보장이 없다. 그래서 예측이 불가능한 불안정 정렬이다. 그럼 나머지 원소들을 입력 순서대로 출력하려면 어떻게 해야할까. 방법은 2가지다.

1. sort() 비교 함수(compare) 내에 조건을 추가해준다. 멤버 변수로 idx를 추가해주었다. 나이가 같을 경우, idx를 오름차순으로 정렬하도록 했다.
2. stable_sort() 를 사용한다. stable_sort()는 sort()와 비슷하지만 다른 정렬 도구다. 첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력을 보장한다. 즉 동일한 값에 대해 기존 순서가 보장되는, 예측할 수 있는 안정적인 정렬이다.

*sort() *

• 첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력한다는 보장이 없다.
• 동일한 값에 대해 기존 순서가 뒤바뀔 수 있다.
• 예측이 불가능한 불안정 정렬

stable_sort()

• 첫 번째 원소가 같을 경우, 두 번째 원소의 입력 순서대로 출력을 보장한다.

• 동일한 값에 대해 기존 순서가 보장된다.

• 예측 가능한 안정적 정렬

  그래서 여기서는 나이 순서대로 정렬하고 나이가 같으면 입력 순서대로 받기 위해 stable_sort()를 사용했다. 사용법은 sort()와 동일하다.

비교함수에 조건 추가

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

struct person
{
    int age, idx;
    string name; //int로 바꿔주면 오류 안남
};

bool compare(const person& now, const person& last)
{
    if(now.age != last.age) return now.age < last.age;
    return now.idx < last.idx;
}

int main()
{    
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    person people[100001]; //구조체 배열

    for (int i = 0; i < N; i++) //배열에 값 넣어줌
    {    
        cin >> people[i].age >> people[i].name;
        people[i].idx = i;
    }

    //정렬
    //stable_sort(people, people + N, compare);
    sort(people, people + N, compare);

    //답 출력
    for (int i = 0; i < N; i++)
        cout << people[i].age << " " << people[i].name << "\n";
}

stable_sort() 사용

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

struct person
{
    int age;
    string name; //int로 바꿔주면 오류 안남
};

bool compare(const person& now, const person& last)
{
    if(now.age != last.age) return now.age < last.age;
    return false;
}

int main()
{    
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    person people[100001]; //구조체 배열

    for (int i = 0; i < N; i++) //배열에 값 넣어줌
        cin >> people[i].age >> people[i].name;

    //정렬
    stable_sort(people, people + N, compare);

    //답 출력
    for (int i = 0; i < N; i++)
        cout << people[i].age << " " << people[i].name << "\n";
}

좌표를 입력 받고 배열에 저장한 후 정렬해서 출력하는 문제이다. 구조체를 만들고 멤버 변수로 x, y 좌표를 정의했다.

이 문제에서 주목할 부분은 바로 x좌표가 같으면 y좌표가 증가하는 순서로 정렬한다는 것이다.

나는 배열 원소들의 정렬을 위해 sort()를 썼는데, 이 sort()에는 주의할 점이 있다.

우선 sort()는 3개의 매개변수를 가진다. sort(A, B, 함수명) A는 배열의 시작 주소, B는 배열의 끝 주소다. 함수명에는 배열의 원소들을 비교하기 위한 함수의 이름만 적어준다. 파라미터까지 적어줄 필요 없다. sort()함수에 대한 자세한 건 여기에 정리했다.

여기서 sort(A,B) 같이 매개변수 2개만 있는 경우도 본 적이 있다. 이 때는 디폴트 값으로 오름차순으로 정렬한다는 뜻이다.

sort()의 비교함수(compare())가 true를 리턴하면 자리를 바꾸고, false를 리턴하면 자리를 바꾸지 않는다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct position
{
    int x, y;
};

bool compare(position now, position last)
{
    if (now.x > last.x) return false;
    if (now.x == last.x && now.y > last.y) return false;
    else return true;
}

int main()
{
    int N;
    scanf("%d", &N);
    struct position arr[100001];

    for (int i = 0; i < N; i++)
    {
        scanf("%d %d", &arr[i].x, &arr[i].y);
    }

    //정렬
    sort(arr, arr + N, compare);

    for (int i = 0; i <N; i++)
        printf("%d %d\n", arr[i].x, arr[i].y);
}

프로그램을 실행하면 프로세스가 된다.

프로세스란 실행중인 프로그램이다. 프로그램이 실행되려면 OS에서 주소공간, 파일, 메모리 등을 할당받아야 하는데, 이러한 것들을 할당받아서 실행 중인 상태를 말한다.

ios::sync_with_stdio(false); cin.tie(NULL);

출처 https://coding-insider.tistory.com/entry/cin-cout-%EC%9E%85%EC%B6%9C%EB%A0%A5-%EC%86%8D%EB%8F%84-%EB%B9%A0%EB%A5%B4%EA%B2%8C%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95

C++로 알고리즘을 풀 때 cin, cout은 속도가 느리다. C++의 cin, cout는 scanf, printf에 비해 속도가 현저히 느리다. cin, cout을 printf, scanf만큼 빠르게 쓸 수 있는 방법이 있다.

ios::sync_with_stdio(false); cin.tie(NULL);

이 두 줄이 무슨 뜻일까

ios::sync_with_stdio(false);

stdio.h는 C에서 printf, scanf를 사용할 수 있는 헤더이다. iostream은 C++에서 cout, cin을 사용할 수 있는 헤더이다.

cin, cout은 기본적으로 C의 stdio.h와 동기화되어있다. stdio.h의 버퍼와 iostream의 버퍼를 같이 쓴다는 말이다. 동기화를 유지하는 작업이 추가되다 보니 상대적으로 속도가 느리다.

버퍼(buffer) : 데이터가 전송될 때 일시적으로 그 데이터를 보관하는 메모리 영역

여기서 stdio.h와 동기화를 안해주면 어떻게 될까? iostream 버퍼만 쓰게되어 버퍼가 줄어든다. 그럼 속도가 빨라지는 것이다.

ios::sync_with_stdio의 기본 디폴트 값은 true이다. stdio.h와 동기화해서 쓰겠다는 것이다. ios::sync_with_stdio()에 false 값을 넣어주면 동기화가 해제된다.

stdio.h와 동기화해서 쓰는 이유는 입력 버퍼링을 방지하기 위함이라고 한다. 알고리즘에서는 입력 형식이 제한되어있어 입력 버퍼링 방지를 할 필요가 없다.

근데 유의할 점이 있다.

1. C의 입출력 방식과 동시 사용 불가 (printf, scanf, getchar, puts, gets)

-> 동기화를 해제했기 때문에 C의 버퍼와 C++의 버퍼가 독립적이다. 따라서 출력되는 순서를 보장할 수 없다.

2. 멀티쓰레드 불가 - 싱글쓰레드 환경에서만 사용(실무에서 사용 불가)

입출력 속도를 빠르게 하기 위한 일종의 편법이다.

cin.tie(NULL);

cin과 cout은 하나로 묶여있어서 서로 연결되어있다.(커플링) cin을 통해 입력이 발생하면 cout 출력 버퍼(buffer)를 플러시(flush)시켜 출력이된 후 입력을 받는다.

버퍼(buffer)는 꽉 차면 출력이 되는 방식이다. 플러시(flush)는 버퍼가 꽉 차지 않아도 즉시 출력해서 버퍼를 비워주는 것이다.

이게 무슨말이냐 cin과 cout은 서로 연결되어있어서 cin을 쓰면 출력 버퍼를 비우고 입력이 발생한다. 이러한 플러시 과정(버퍼를 비우는 작업)도 시간이 든다. 그래서 cin, cout의 상호 연결을 끊어주기 위해 cin.tie(NULL);를 사용한다.

개행문자

endl보다 "\n"이 더 빠르다. endl도 불러오는 것이기 때문이다.

11053 가장 긴 증가하는 부분수열을 풀어봤다면 수월하게 풀 수 있다.

탐색 순서는 i=3일 때 1, 2번째 i=4일 때 1, 2, 3번째와 비교한다.

입력받는 수를 담을 배열 arr[]와 i번째까지 증가하는 수열의 합을 담을 배열 dp[]를 정의해준다.

d[]의 모든 원소는 arr[] 자기자신 값으로 초기화해준다. 가장 긴 증가하는 수열이 자기자신 뿐으로 총 합이 자기자신일 수도 있다.

i=3일 때 j=1, 2 i=4일 때 j=1, 2, 3 이라고 하면

arr[i]가 arr[j]보다 작을 경우는 패쓰하고 arr[i]가 arr[j]보다 클 경우에는 d[i] = d[j] + arr[i]을 해준다. 여기서 주의할 점 arr[4]가 arr[2]보다 크고 arr[3]보다 큰데 d[2] = 1, d[3] = 100일 때 d[4]는 100이 되어야 한다. 그러면 매번 d[j]+arr[i]값을 비교했을 때 더 큰 값을 선택해주면 된다. 즉, d[i] = max(d[i], d[j]+arr[i])을 반복해주면 된다.

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

int main()
{
    int N;
    scanf("%d", &N);

    int arr[1001];
    for(int i=1; i<=N; i++) scanf("%d", &arr[i]);

    int dp[1001];
    for(int i = 1; i<=N; i++) dp[i] = arr[i];

    for(int i = 1; i<=N; i++)
    {
        for(int j = 1; j<i; j++)
        {
            if(arr[i] > arr[j])
            {
                dp[i] = max(dp[i], dp[j] + arr[i]);
            }
        }
    }
    sort(dp, dp+N+1);

    //for(int i=1; i<=N; i++) printf("%d  ",dp[i]);
    printf("%d",dp[N]);

}