띠그랭

완전 탐색 - Brute Force Search

일단 완전 탐색을 할 수 있는 방법은 여러가지가 있는데,

1) Brute Force - 그냥 다 해보리기

2) BFS - 그래프로 표현하여 다 탐색하기

3) 재귀

4) 비트마스크

5) 순열

6) 백트래킹

등등 이 있다.

Brute Force

그냥 다 검색해보는 Brute Force를 공부해보자아.

for문과 if문을 이용하여 처음부터 쭈루룩 탐색해보는 방법.

여기서 중요한 것은 범위, 무작정 다 검색하기 때문에 시간초과가 날수 있다.

for문 1억번을 1초라고 보통 생각하기 때문에 이걸 잘 생각하며 풀어야 한다.

쉬운 문제로 일단 어떤 느낌인지 공부를 해보면

https://www.acmicpc.net/problem/1476

날짜 계산 1476번

이 문제는 for문 과 간단한 if문을 통해 1, 1 , 1부터 쭈루룩 돌아서 입력과 같은 값이 되었을 때 count한 값을 출력하는 심플한 문제

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 숫자를 E, 태양을 나타내는 숫자를 S, 달을 나타내는 숫자를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 지나면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

예제 입력 1

 
xxxxxxxxxx
1 16 16

예제 출력 1

 
xxxxxxxxxx
16

예제 입력 2

 
xxxxxxxxxx
1 1 1

예제 출력 2

 
xxxxxxxxxx
1

예제 입력 3

 
xxxxxxxxxx
1 2 3

예제 출력 3

 
xxxxxxxxxx
5266

소스 코드

 
xxxxxxxxxx
#include<iostream>
using namespace std;
int main()
{
    // 날짜 계산 1476번
    int E, S, M;
    int e = 1, s = 1, m = 1;
    int year = 1;
    cin >> E >> S >> M;
    while (!(E == e && S == s && M == m))
    {
        e++;
        s++;
        m++;
        if (e == 16) e = 1;
        if (s == 29) s = 1;
        if (m == 20) m = 1;
        year++;
    }
    cout << year << '\n';
    return 0;
}

리모콘 1107번

https://www.acmicpc.net/problem/1107

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 중복되서 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

예제 입력 1

 
xxxxxxxxxx
5457
3
6 7 8

예제 출력 1

 
xxxxxxxxxx
6

예제 입력 2

 
xxxxxxxxxx
100
5
0 1 2 3 4

예제 출력 2

 
xxxxxxxxxx
0

예제 입력 3

 
xxxxxxxxxx
500000
8
0 2 3 4 6 7 8 9

예제 출력

 
xxxxxxxxxx
11117

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
​
vector<int> v(10);
int res;
​
int check(int c)
{
    int len = 0;
    if(c == 0)
    {
        if(v[0]) return 0;
        else return 1;
    }
    
    while(c > 0)
    {
        if(v[c % 10]) return 0;
        len++;
        c /= 10;
    }
    return len;
}
​
int main()
{
    int c;
    int n;
    cin >> c;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        int tmp;
        cin >> tmp;
        v[tmp] = 1;
    }
    
    res = abs(c - 100);
    
    
    for(int i=0;i<=1000000;i++)
    {
        int len = check(i);
        if(len > 0)
        {
            int press = abs(c - i);
            if(res > len + press)
                res = len + press;
        }
    }
    
    cout << res << '\n';
    
    return 0;
}
​

완전 탐색 - 비트마스크

비트 연산

shift left (<<) , shift right (>>) 두개의 연산이 있다

A >> B (A 를 오른쪽으로 B비트만큼 이동)

1 >> 1 0(이진법)

10 >> 1 101(이진법)

10 >> 2 1010 을 오른쪽으로 2비트 이동 ==> 10 즉 2가 됨

A << B 는 A * 2^B

A >> B 는 A / 2^B

이것을 이용하여 할 수 있는 것은 정수를 통해 집합을 표현할 수 있다.

만약 10명의 학생이 있고, 0~9번 이라는 번호로 학생을 표현하고 싶을 때 1,3,5,7,9 번의 학생을 한 집합으로 표현한다면,

이런 식으로 표현이 가능하며, 2진법으로 표현한다면 1010101010(2) 으로 표현할 수 있다.

만약에 내가 5번 학생이 있는걸 확인하고 싶으면

 
xxxxxxxxxx
int sum = 682;
if(sum & (1 << 5)) cout << "5번 학생이 있다" << '\n';

이 집합 상태에서 어느 한 학생을 추가(삽입) 하고싶다면 OR(|) 연산을 이용하면 된다.

 
xxxxxxxxxx
sum = sum | (1 << 2);   // 2번 학생을 추가

여기서 + 연산을 사용하지 않은 이유는 carry가 발생하여, 다른 값에 영향을 줄수 있기 때문에 OR연산을 사용한다.

집합에서 어느 한 학생을 제거(삭제) 하고 싶다면 N0T(&)연산을 이용하면 된다.

 
xxxxxxxxxx
sum = sum & ~(1 << 5);  // 5번 학생을 제거

전체 집합 표현

공집합

A라는 집합에서 특정 n 을 추가 할때

A | (1 << n)

A라는 집합에서 특정 n 을 확인 할때

A & (1 << n)

A라는 집합에서 특정 n 을 제거 할때

A & ~(1 << n)

A라는 집합에서 각 값을 토글 할때

A ^ (1 << n)

비트마스크 연산 연습해보기

https://www.acmicpc.net/problem/11723

소스 코드

 
x
#include<iostream>
#include<string>
using namespace std;
​
int sum;
​
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string ins;
        cin >> ins;
        if(ins == "add")
        {
            int tmp;
            cin >> tmp;
            tmp--;
            sum = sum | (1 << tmp);
        }
        else if(ins == "remove")
        {
            int tmp;
            cin >> tmp;
            tmp--;
            sum = sum & ~(1 << tmp);
        }
        else if(ins == "check")
        {
            int tmp;
            cin >> tmp;
            if(sum & (1 << tmp)) cout << "1" << '\n';
            else cout << "0" << '\n';
        }
        else if(ins == "toggle")
        {
            int tmp;
            cin >> tmp;
            tmp--;
            sum = sum ^ (1 << tmp);
        }
        else if(ins == "all")
            sum = (1 << 20) - 1;
        else if(ins == "empty")
            sum = 0;
    }
    return 0;
}

열혈강호 11375번 - 이분매칭

문제

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.

각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

출력

첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

예제 입력

 
xxxxxxxxxx
5 5
2 1 2
1 1
2 2 3
3 3 4 5
1 1

예제 출력

 
xxxxxxxxxx
4

소스 코드

 
x
#include<iostream>
#include<vector>
#include<algorithm>
​
using namespace std;
​
int emp;    // 일하는 사람 수
int work;   // 작업의 수
int res;    // 결과
vector<vector<int>> v(1001);    // 어떤 사람이 무슨 일 할 수 있는지 저장
int visit[1001];        // i번째 사람의 이미 방문했는지 check
int match[1001];        // i번째 일을 누가 했는지 match[i]에 저장
​
int dfs(int person)
{
    if (visit[person]) return 0;        // 이미 dfs돌았다면 패스
    visit[person] = 1;
    
    for (int i = 0; i < v[person].size(); i++)
    {
        int here_work = v[person][i];       // 직원이 무슨 일 할 수 있는지 here_work에 저장
        if (!match[here_work] || dfs(match[here_work]))
        {
            match[here_work] = person;      // 그 작업을 현재 사람에게 매칭
            return 1;
        }
    }
    return 0;
}
​
int main()
{
    cin >> emp >> work;
    for (int i = 1; i <= emp; i++)
    {
        int seq;
        cin >> seq;
        for (int j = 1; j <= seq; j++)
        {
            int tmp;
            cin >> tmp;
            v[i].push_back(tmp);
        }
    }
    for (int i = 1; i <= emp; i++)
    {
        fill(visit, visit + emp, 0);
        if (dfs(i)) res++;
    }
​
    cout << res << '\n';
​
    return 0;
}

일곱 난쟁이 2309번 - 완탐(순열)

이 문제는 순열을 이용하여 푼 완전탐색 문제이다

9명의 난쟁이들 중에 7명을 고르고 조건을 만족하면 출력하는 문제

vector하나 만들어서 7개의 1과 2개의 0을 넣어 순열 쭈루루룩 돌린담에 조건을 만족하면 출력

이 방법은 next_permutation을 돌리기 전 맨처음 상태도 체크 해야하기 때문에 do_while 사용

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 일곱 난쟁이의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다.

예제 입력

 
xxxxxxxxxx
20
7
23
19
10
15
25
8
13

예제 출력

 
xxxxxxxxxx
7
8
10
13
19
20
23

소스코드

 
xxxxxxxxxx
// 2309번 일곱난쟁이
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
​
vector<int> v(9);
​
void input()
{
 for (int i = 0; i < 9; i++)
  cin >> v[i];
}
​
void DFS()
{
 vector<int> tmp;
​
 for (int i = 0; i < 2; i++)
  tmp.push_back(0);
​
 for (int i = 0; i < 7; i++)
  tmp.push_back(1);
​
 do {
  int sum = 0;
  for (int i = 0; i < tmp.size(); i++)
   if (tmp[i]) sum += v[i];
  if (sum == 100)
   break;
 } while (next_permutation(tmp.begin(), tmp.end()));
​
 vector<int> res;
 for (int i = 0; i < tmp.size(); i++)
 {
  if (tmp[i]) res.push_back(v[i]);
 }
 sort(res.begin(), res.end());
 for (int i = 0; i < res.size(); i++)
  cout << res[i] << '\n';
}
​
int main()
{
 input();
​
 DFS();
​
 return 0;
}

1244번 최대상금 - [S/W 문제해결 응용]

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD

이 문제는 이중 for문으로 완전탐색을 아주 그냥 돌려버렸다.

중복체크 안하고 돌리면 테스트케이스 7번까지는 돌아간다.

하지만 테스트케이스 8번부터 시간초과가 나버린다.

그러므로 중복체크 해야하므니다.

소스코드

 
xxxxxxxxxx
// 1244 최대상금 - 완탐
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
​
int T, seq;
vector<int> v;
int max_price;
int check[1000000][11];
​
int calc()
{
    int tmp = 0;
    for (int i = 0; i < v.size(); i++)
        tmp += (v[i] * pow(10, v.size() - i - 1));
    
    return tmp;
}
​
void swap(int f,int s)
{
    int first = v[f];
    int second = v[s];
    v[f] = second, v[s] = first;
}
​
void DFS(int n)
{
    if (n >= seq)
    {
        max_price = max(max_price, calc());
        return;
    }
​
    if (check[calc()][n]) return;       // 이 두줄이 중복체크용
    check[calc()][n] = 1;
​
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = i+1; j < v.size(); j++)
        {
            swap(i, j);
            DFS(n + 1);
            swap(i, j);
        }
    }
}
​
void input()
{
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        string tmp;
        cin >> tmp >> seq;
        for (int j = 0; j < tmp.size(); j++)
            v.push_back(tmp[j] - '0');
        DFS(0);
        cout << "#" << i << " " << max_price;
        max_price = 0;
        v.clear();
    }
}
​
int main()
{
    input();
    
    return 0;
}

로또 6603번 (완전탐색-순열)

https://www.acmicpc.net/problem/6603

algorithm에 있는 순열함수인 next_permutation을 이용하여

만약 7개 중에 6개를 골라야한다면, 배열에 0을 1개 , 1을 6개 넣어서 나올수 있는 모든 순열을 쫘르르륵 한다음에 1이 위치하고있는 인덱스를 활용하면, 7가지 숫자중 6개의 모든 조합을 추출할 수 있다. 말로는 이해하기 어려울수 있으니 소스를 참고바람.

문제

독일 로또는 {1, 2, ..., 49}에서 숫자 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 숫자 중 k(k>6)개의 숫자를 골라 집합 S를 만든 다음 그 숫자만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 숫자를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 숫자를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 k (6 < k < 13)이고, 다음 k개 숫자는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스 마다 숫자를 고르는 모든 방법을 출력한다. 이 때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력

 
xxxxxxxxxx
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

예제 출력

 
xxxxxxxxxx
​
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
​
1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

소스코드

 
xxxxxxxxxx
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int k;
    while (cin >> k)
    {
        if (k == 0) break;
        vector<int> v(k);
        for (int i = 0; i < k; i++)
            cin >> v[i];
​
        vector<int> d(k);
        for (int i = 0; i < k - 6; i++)
            d[i] = 0;
        
        for (int i = k - 6; i < k; i++)
            d[i] = 1;
        
        vector<vector<int>> ans;
        do {
            vector<int> current;
            for (int i = 0; i < k; i++)
            {
                if (d[i] == 1)
                    current.push_back(v[i]);
            }
            ans.push_back(current);
        } while (next_permutation(d.begin(), d.end()));
​
        sort(ans.begin(), ans.end());
        
        for (int i = 0; i < ans.size(); i++)
        {
            for (int j = 0; j < ans[i].size(); j++)
                cout << ans[i][j] << ' ';
            cout << '\n';
        }
        cout << '\n';
    }
    return 0;
}

쿠키와 세션의 차이점

우리가 특정한 웹사이트에서 로그인을 할 때, "ID와 비밀번호를 저장하시겠습니까?" 하는 말은 쿠키를 만들것이냐 란 말이드아

그럼 쿠키와 세션을 왜 사용할까?

HTTP프로토콜의 특성상 존재하는 단점을 보완하기 위해 존재하는데

두가지의 특성이 무엇이냐 하면 Connectionless 와 Stateless입니다

• Connectionless - 클라이언트가 서버로 Request를 보내고 , 서버가 클라이언트에게 Response를 하면 접속을 끊는 특성
• Stateless - 접속을 끊는 순간 클라이언트와 서버의 통신은 끝나고 상태 정보를 유지하는 특성

이 특성은 통신을 유지하지 않기 때문에, 그 쪽에 대한 자원의 낭비를 줄일 수 있지만, 만약 같은 웹사이트를 들어 갈 때마다 내가 누구인지 인증을 해야합니다.

예를 들어 네이버 로그인을 한 후 서비스를 이용시 다른 서비스를 이용할 때 다시 로그인을 해야 하는 상황이 발생합니다.

쿠키와 세션은 HTTP프로토콜을 이용 할때 서버가 클라이언트를 식별할 수 있게 도와주는 역할을 해주는 것

쿠키와 세션에 대해 알아보자

쿠키(Cookie)

• 서버측에서 클라이언트측에 상태 정보를 저장하고 추출할 수 있는 메커니즘
• 클라이언트의 매 요청마다 웹 브라우저로부터 서버에게 전송되는 정보패킷의 일종
• HTTP에서 클라이언트의 상태 정보를 클라이언트의 하드 디스크에 저장하였다가 필요 시 정보를 참조하거나 재사용할 수 있음

쿠키 원리

클라이언트가 웹브라우저를 통하여 웹페이지 접속 -> 클라이언트가 요청한 웹페이지(HTTP)를 전송하면서 쿠키 설정(클라이언트의 하드디스크에 저장) -> 웹페이지에 재방문시 HTTP요청과 함께 쿠키도 같이 전송

사용 예

• 방문했던 사이트에 다시 방문 하였을때 아이디와 비밀번호 자동 입력
• 팝업에서 "오늘 이 창을 다시 보지 않음"체크
• 쇼핑몰의 장바구니 역할

쿠키의 제약조건

• 클라이언트에 총 300개 까지 쿠기 저장가능
• 하나의 도메인 당 20개의 쿠키값만을 가질 수 있음
• 하나의 쿠키 값은 4096Byte까지 저장 가능

만약에 한 도메인당 쿠키값이 20개를 초과해버리면, 가장 적게 사용된 쿠키부터 사라짐.

세션(Session)

• 사용자가 웹 서버에 접속해 있는 상태
• 사용자가 브라우저를 열어 서버에 접속한뒤 접속을 끊을(브라우저 종료)시점까지를 세션
• 클라이언트가 웹서버에 Request를 보내면, 해당 서버의 엔진이 클라이언트에게 유일한 ID(쿠키)를 부여, ID를 세션이라고 함
• 세션의 정보를 서버에 저장, 따라서 보안면에서 쿠키보다 우수

HTTP 프로토콜은 비접속형 프로토콜이므로, 매 접속시마다 새로운 네트워크 연결이 이루어진다

이 ID는 쿠키를 사용하여 유지되며, 이 쿠키의 이름이 JSESSIONID이며, 서버는 JSESSIONID를 웹 브라우저에 전달하고, 클라이언트는 새로운 접속시 쿠키를 통해서 세션 ID값을 서버에 전달한다.

• 세션 ID를 임시로 저장하여 페이지 이동 시 이용하거나, 클라이언트가 재 접속 했을 때 클라이언트를 구분할 수 있는 유일한 수단

세션의 단점

• 서버에 저장되는 세션때문에 서버에 처리를 요규하는 부하와 저장 공간을 필요로 함

쿠키와 세션의 차이점

쿠키(Cookie)와 세션(Session)은 기능상 비슷한 역할을 하고, 동작원리도 비슷하다. 왜냐하면, 일반적인 세션은 쿠키를 바탕으로 동작하기 때문, 그러다 가장 중요한 차이점은 저장되는 곳이 다르다

쿠키는 클라이언트의 하드디스크에 저장되고, 세션은 서버에 저장된다.

그래서 쿠키는 서버의 자원을 전혀 이용하지않으며, 세션은 서버에 저장되기 때문에 서버의 자원을 사용할 수 있다.

마지막으로 짧게 간추리면

쿠키와 세션은 HTTP프로토콜의 웹사이트를 접속할 때 생기는 단점(Connectless , Stateless)을 보완하기 위해 사용되며, 쿠키는 클라이언트의 하드디스크에 저장되며 웹브라우저에서 서버로 HTTP프로토콜을 통해 웹사이트를 요청할때 같이 보내는 녀석.()

세션은 서버에 저장되며, 클라이언트에 각각의 ID(쿠키)를 부여하며 이것을 세션이라 한다. 이놈을 통해 나중에 웹사이트에 재접속 할때 클라이언트를 구분짓는 유일한 수단이 된다.

웹브라우저가 서버와 통신하는 과정

우리가 일상생활에서 컴퓨터나 스마트폰의 웹브라우저(chrome , explorer, Safari)를 통해 보고 싶은 웹페이지를 볼때 무슨 일이 발생하는지 알아봅시당.

클라이언트와 서버

웹브라우저는 요청 , 웹서버는 응답

클라이언트란 웹브라우저(chrome, explorer 등)와 같은 웹에 접근할 수 있는 소프트웨어와 인터넷이 연결된 장치(데스크탑, 스마트폰)들을 말합니다.

서버는 웹페이지, 사이트,또는 앱을 저장하는 컴퓨터입니다. 클라이언트의 장비가 웹페이젱 접근하길 원할 때, 서버로부터 클라이언트의 장치로 사용자의 웹브라우저에게 보여지기 위한 웹페이지의 사본이 다운로드 됩니다.

기본적으로 알아야 하는 것들

지금은, 웹이 도로라고 상상해봅시다. 도로의 한 쪽 끝은 여러분의 집 같은 클라이언트 입니다. 다른 한 쪽 끝은 여러분이 뭔가를 사길 원하는 상점같은 서버입니다.

• 인터넷 연결: 여러분이 웹에서 데이터를 보내고 받을 수 있게 해줍니다. 기본적으로 여러분의 집과 상점 사이의 거리와 같습니다.

• TCP/IP: Transmission Control Protocol (전송 제어 규약) 과 Internet Protocol (인터넷 규약) 은 데이터가 어떻게 웹을 건너 여행해야 하는지 정의하는 통신 규약입니다. 이것은 주문을 하고, 상점에 가고, 또 여러분의 상품을 살 수 있게 해주는 운송 장치와 같습니다. 우리 예시에서, 이것은 차 또는 자전거 (또는 여러분의 두 다리) 와 같습니다.

• DNS: Domain Name System Servers (도메인 이름 시스템 서버) 는 웹사이트를 위한 주소록과 같습니다. 여러분이 브라우저에 웹 주소를 입력할 때, 브라우저는 그 웹사이트를 검색하기 전에 DNS 를 살펴봅니다. 브라우저는 HTTP 메시지를 올바른 장소로 전송하기 위해 그 웹사이트가 있는 서버가 어떤것인지 찾아야 합니다 (아래를 보세요). 이것은 여려분이 접근하기 위해 상점의 주소를 찾아보는 것과 같습니다.

• HTTP: Hypertext Transfer Protocol (하이퍼텍스트 전송 규약) 은 클라이언트와 서버가 서로 통신할 수 있게 하기 위한 언어를 정의하는 어플리케이션 규약 입니다. 이것은 여러분의 상품을 주문하기 위해 여러분이 사용하는 언어와 같습니다.

• 컴포넌트 파일

  : 한 웹사이트는 여러분이 상점에서 사는 다양한 종류의 상품들과 같이 많은 다른 파일들로 만들어집니다. 이 파일들은 두개의 주요한 타입이 있습니다:

  • 코드 파일: 다른 기술들도 잠시 뒤 보게 되실것이지만, 웹사이트는 근본적으로 HTML, CSS, 그리고 JavaScript 로 생성됩니다.
  • 자원: 이것은 이미지, 음악, 비디오, 단어 문서, 그리고 PDF 같은, 웹사이트를 만드는 모든 다른 것들을 위한 공동적인 이름입니다.

웹브라우저의 동작 과정

여러분이 브라우저에 웹 주소를 입력할 때 (우리의 비유에서 상점으로 걸어가는 것과 유사합니다):

1. 브라우저는 DNS 서버로 가서 웹사이트가 있는 서버의 진짜 주소를 찾습니다 (여러분이 상점의 주소를 찾습니다).
2. 그 다음 브라우저는 서버에게 웹사이트의 사본을 클라이언트에게 보내달라는 HTTP 요청 메세지를 서버로 전송합니다.(상점으로 가서 상품을 주문합니다.) 이 메세지, 그리고 클라이언트와 서버 사이에 전송된 모든 데이터는 TCP/IP 연결을 통해서 전송됩니다.
3. 이 메세지를 받은 서버는 클라이언트의 요청을 승인하고, "200 OK" 메세지를 클라이언트에게 전송합니다. "200 OK"는 "물론이죠. 당신은 웹 사이트를 볼 수 있어요! 여기 있어요" 라는 의미입니다. 그 다음 서버는 웹사이트의 파일들을 데이터 패킷이라 불리는 작은 일련의 덩어리들로 브라우저에 전송하기 시작합니다.(상점은 여러분이 주문한 상품을 전달하고, 여러분은 그것을 집으로 가져갑니다.)
4. 브라우저는 이 작은 덩어리들을 완전한 웹 사이트로 조립하고, 당신에게 보여줍니다. (상품이 당신의 문에 도착합니다. — 새 것이죠, 멋저요!)

DNS(Domain Name Server)란

실제 웹 주소는 멋지거나, 여러분이 선호하는 웹사이트를 찾기위한 주소 막대에 입력하는 기억할만한 문자가 아닙니다. 그것은 숫자들의 문자열입니다, 이렇게요: 63.245.217.105.

이것은 IP 주소라고 하고, 웹의 하나뿐인 특정 위치를 나타냅니다. 그런데, 기억하기 아주 쉽진 않습니다, 그렇죠? 그것이 도메인 이름 서버가 발명된 이유입니다. 도메인 이름 서버는 여러분이 브라우저에 입력하는 웹주소 ("mozilla.org" 같은) 를 웹사이트의 실제 (IP) 주소에 맞춰주는 특별한 서버입니다.

웹사이트는 그들의 IP 주소를 통해 직접 접근될 수도 있습니다. 새 브라우저 탭의 주소막대에 63.245.217.105를 입력하는것으로 모질라 웹사이트에 가보세요.

패킷 설명

앞서 우리는 서버에서 클라이언트로 전송되는 데이터의 포맷을 설명하기 위해 "패킷" 이라는 용어를 사용했습니다. 이게 무엇을 의미하는 걸까요? 기본적으로, 데이터가 웹을 거쳐서 전송될 때, 수천개의 작은 덩어리들로 전송됩니다. 그래서 다양한 웹 사용자들은 동시에 같은 웹 사이트를 다운로드 할 수 있게 됩니다. 만약 웹 사이트가 하나의 큰 덩어리들로 전송된다면, 오직 한 번에 하나의 사용자만 다운로드 할 수 있을 것입니다. 이는 분명 웹을 매우 비효율적이고, 사용하기에 재미없게 만들 것입니다.

마지막으로 짧게 간추리면

웹브라우저에서 들어가고 싶은 웹사이트를 DNS를 통해 실제 주소(IP)를 알아낸 다음, HTTP 요청 메세지를 서버에게 보냄, 물론 TCP/IP 연결방식으로... 그 후 서버는 웹브라우저에게 패킷들을 쫘르르륵 보낸다음 웹브라우저가 그것들을 조립해서 사용자에게 보여준드아.

출처 : https://developer.mozilla.org/ko/docs/Learn/Getting_started_with_the_web/%EC%9B%B9%EC%9D%98_%EB%8F%99%EC%9E%91_%EB%B0%A9%EC%8B%9D

Post 와 GET의 차이

짧게 한 문장으로 표현하자면 , Get은 정보를 가져오는 것, POST는 수행하는 것이다

GET방식은 URL 형식으로 웹서버 측 데이터를 요청합니다.

• URL에 이어붙이기 때문에 길이제한이 있음

• DB를 수정하지 않고 저장된 Data를 단순 요청하는 정도로 사용 (DB의 SELECT와 같은 역할)

   

POST방식은 HTTP body안에 form을 이용하여 웹서버측에 데이터를 요청합니다

• POST는 많은 양을 보내기에 적합
• DB에 저장/수정하는 경우에 POST를 사용

즉 http://url/bbslist.html?id=5&pagenum=2 같이 하는 것이 GET방식이고 form을 이용해서 submit을 하는 형태가 POST입니다.

좀 자세히 설명하면 GET은 Select적인 성향을 가지고 있습니다. GET은 서버에서 어떤 데이터를 가져와서 보여준다거나 하는 용도이지 서버의 값이나 상태등을 바꾸지 않습니다. 게시판의 리스트라던지 글보기 기능 같은 것이 이에 해당하죠.(방문자의 로그를 남긴다거나 글읽은 횟수를 올려준다거나 하는건 예외입니다.) 반면에 POST는 서버의 값이나 상태를 바꾸기 위해서 사용합니다. 글쓰기를 하면 글의 내용이 DB에 저장이 되고 수정을 하면 디비값이 수정이 되죠. 이럴 경우에 POST를 사용합니다.

https://www.acmicpc.net/problem/1697

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력

 
5 17

예제 출력

 
4

기본적인 BFS문제이다. Queue에 다음에 갈 수 있는 좌표를 저장하고, Vector을 이용하여 해당 Vector<좌표>에 값이 없을 경우 방문하지 않는 곳이므로 다음에 방문 하게 했다.

BFS를 이용했음으로 가장 빠른 시간을 위한 조건은 따로 필요하지 않았다.

 
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
​
vector<int> v(100001);
​
void BFS(int start, int end)
{
    queue<int> q;
    q.push(start);
    v[start] = 1;
    while (1)
    {
        if (q.empty()) break;
        int now = q.front();
        q.pop();
​
        if (now - 1 >= 0)
        {
            if (!v[now - 1])
            {
                v[now - 1] = v[now] + 1;
                q.push(now - 1);
            }
        }
​
        if (now + 1 <= 100000)
        {
            if (!v[now + 1])
            {
                v[now + 1] = v[now] + 1;
                q.push(now + 1);
            }
        }
​
        if (now * 2 <= 100000)
        {
            if (!v[now * 2])
            {
                v[now * 2] = v[now] + 1;
                q.push(now * 2);
            }
        }
​
        if (v[end])
        {
            cout << v[end] - 1 << '\n';
            break;
        }
    }
}
​
int main()
{
    int s, e;
    cin >> s >> e;
​
    BFS(s,e);
​
    return 0;
}