문제 링크

2565번: 전깃줄

풀이

LIS(최장 증가 부분 수열)을 이용하는 DP문제

1. 먼저 첫번째 전깃줄을 기준으로 오름차순 정렬을 한다.
2. 정렬된 전깃줄의 두번째 전깃줄 배열의 최장 증가 부분 수열을 구한다. 2-1. 이 수열이 겹치지 않는 전깃줄의 최대수가 될테니 n에서 빼주면 답이 나온다. 2-2. 입력값이 크지 않기 때문에 O(n^2)의 dp로 푼다. 현재 전깃줄의 dp를 1로 초기화해준 뒤, 이전 전깃줄보다 현재 전깃줄이 크다면 dp 값을 비교해 갱신한다.
3. 그렇게 dp의 최대값을 구해 n에서 빼면 된다.

코드

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

int main()
{
    int n;
    cin >> n;

    vector<vector<int>> v(n, vector<int>(2));
    for (int i = 0; i < n; i++)
    {
        cin >> v[i][0] >> v[i][1];
    }
    sort(v.begin(), v.end());

    vector<int> dp(n);
    int remove = 0;
    for (int i = 0; i < n; i++) // 현재 
    {
        dp[i] = 1;
        for (int j = 0; j < i; j++) // 이전
        {
            if (v[j][1] < v[i][1])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        remove = max(remove, dp[i]);
    }

    cout<<n-remove<<endl;

    return 0;
}

3273번: 두 수의 합

풀이

1. 서로 다른 정수이기 때문에 투포인터로 풀면 된다.
2. 오름차순 정렬 후 왼쪽 포인터, 오른쪽 포인터로 나누어서 2-1. 같으면 answer++ 후, left++, right++ 해준다. 2-2. 크다면 right--, 작다면 left++ 해준다.
3. 왼쪽 포인터가 오른쪽 포인터보다 같거나 커질 때까지 해준다.

코드

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

int main()
{
    int answer = 0;
    int n, k;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    cin >> k;

    sort(v.begin(), v.end());

    int left = 0;
    int right = n - 1;
    while (left < right)
    {
        if (v[left] + v[right] == k)
        {
            answer++;
            left++;
            right--;
        }
        else if (v[left] + v[right] > k)
        {
            right--;
        }
        else
        {
            left++;
        }
    }

    cout << answer << endl;
}

문제 링크

합승 택시 요금

풀이

다익스트라로 푸는 문제. 시간 초과 날 것 같았는데 안나네 ..

1. 먼저 인접리스트를 초기화한다.
2. 시작 노드부터 다익스트라로 최단 거리를 계산한다. 2-1. dijkstra 함수를 만들어 계산하였다. 모든 노드까지를 무한대로 두고 (나 같은 경우, 노드가 최대 200개, 요금은 최대 100,000이므로 20,000,000 이상은 안나올 것이라 생각해 정의해주었다) 우선 순위 큐를 이용해 최단 노드를 계속 갱신해준다.
3. 여기가 핵심 알고리즘인데, 2번까지 해서 최단 경로가 있는 벡터가 반환될 텐데, 바로 [a]와 [b]를 더해주면 처음부터 각자 가는 것이다. 3-1. 노드를 다 돌면서 시작 노드부터 해당 노드까지는 같이 가고, 해당 노드부터 a와 b까지는 각자 가는 것으로 다시 dijkstra를 구해준다.
4. 모든 루트를 다 돌면서 제일 적은 금액이 최소 금액이 될 것이다.

코드

#include <string>
#include <vector>
#include <queue>
#define INF 20000000

using namespace std;

vector<int> dijkstra(vector<vector<pair<int,int>>> &adj, int s)
{
    vector<int> dist(adj.size(), INF);
    dist[s] = 0;

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0,s});
    while(!pq.empty())
    {
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        for(int i=0;i<adj[cur].size();i++)
        {
            pair<int,int> node = adj[cur][i];
            if(cost+node.first < dist[node.second])
            {
                pq.push({node.first+cost, node.second});
                dist[node.second] = cost+node.first;
            }
        }
    }

    return dist;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;

    vector<vector<pair<int,int>>> adj(n+1); // 인접리스트
    for(int i=0;i<fares.size();i++) // 초기화
    {
        int stt = fares[i][0];
        int end = fares[i][1];
        int cost = fares[i][2];
        adj[stt].push_back({cost, end});
        adj[end].push_back({cost, stt});
    }

    vector<int> sttRoute = dijkstra(adj, s);
    answer = sttRoute[a] + sttRoute[b]; // 처음부터 각자 가는거
    for(int i=1;i<=n;i++)
    {
        if(i == s) continue;

        int tmp = sttRoute[i]; // i까지는 같이 가고

        vector<int> tmpArr = dijkstra(adj, i);
        tmp += tmpArr[a] + tmpArr[b]; // 각자 집 따로 가기

        answer = min(answer, tmp);
    }

    return answer;
}

문제 링크

길 찾기 게임

풀이

이진트리를 만들고 순회하는 문제

1. 먼저 Node 구조체를 만들어준다. 1-1. 순회해서 인덱스를 출력해야 하므로 data, 위치값인 x, y, 왼쪽 자식 노드 포인터 left와 오른쪽 자식 노드 포인터 right 1-2. 처음엔 생성자를 만들어줬는데 그럴 필요 없음 ..
2. Node 벡터를 만들어주고 초기화 해준 뒤, 정렬을 해주어야 함 2-1. y 값으로 내림차순 정렬, x 값으로 오름차순 정렬해준다. 해당 커스텀 정렬 함수는 compare
3. 정렬 후 0번째 노드는 제일 위에 있는 노드이므로 root가 된다. 1번째 노드부터 부모에 연결해준다. 해당 함수는 setParent 3-1. 부모 노드 포인터인 parent의 x값이 해당 노드 x값 보다 크다면 왼쪽에 있다는 것. 부모의 왼쪽 자식 노드가 NULL이라면 해당 노드가 그 부모의 왼쪽 자식 노드가 된다. 이미 자식이 있다면 해당 왼쪽 자식 노드를 다시 부모로 재귀호출해준다. 오른쪽도 마찬가지로 진행
4. 이진트리의 순회는 재귀호출로 쉽게 가능하다. 전위순회는 해당노드->왼쪽자식->오른쪽자식, 후위순회는 왼쪽자식->오른쪽자식->해당노드 순이 된다. 해당 노드일 때는 data 값을 넣고, 자식 노드일 때는 재귀호출 해주면 된다. 물론 NULL 체크도 해줘야 널 익셉션이 안뜸

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

struct Node
{
    int data;
    int x, y;
    Node* left;
    Node* right;

    Node(int _data, int _x, int _y) : data(_data), x(_x), y(_y)
    {
        left = NULL;
        right = NULL;
    }
};

bool compare(Node a, Node b)
{
    if (a.y == b.y) return a.x < b.x;
    else return a.y > b.y;
}

void setParent(Node* parent, Node* node)
{
    if (parent->x > node->x) // 왼쪽에 있음
    {
        if (parent->left == NULL)
        {
            parent->left = node;
            return;
        }
        setParent(parent->left, node);
    }
    else // 오른쪽에 있음
    {
        if (parent->right == NULL)
        {
            parent->right = node;
            return;
        }
        setParent(parent->right, node);
    }
}

void preorder(Node* root, vector<int> &pre)
{
    pre.push_back(root->data);
    if(root->left != NULL) preorder(root->left, pre);
    if(root->right != NULL) preorder(root->right, pre);
}

void postorder(Node* root, vector<int> &post)
{
    if(root->left != NULL) postorder(root->left, post);
    if(root->right != NULL) postorder(root->right, post);
    post.push_back(root->data);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;

    vector<Node> tree;
    for (int i = 0; i < nodeinfo.size(); i++)
    {
        tree.push_back({ i + 1, nodeinfo[i][0], nodeinfo[i][1] }); // x,y,인덱스
    }

    sort(tree.begin(), tree.end(), compare); // y 내림차순, x 오름차순 정렬

    Node* root = &tree[0]; // 루트 노드
    for (int i = 1; i < tree.size(); i++) // 트리 만들어주기
    {
        setParent(root, &tree[i]);
    }

    vector<int> answer1;
    preorder(root, answer1);

    vector<int> answer2;
    postorder(root, answer2);

    answer.push_back(answer1);
    answer.push_back(answer2);

    return answer;
}

문제 링크

택배상자

풀이

stack과 queue 문제

1. 메인 컨테이너는 queue이고, 서브 컨테이너는 stack이다. 먼저 queue인 main에 초기화를 해준다.
2. 주문을 보면서 main의 맨 앞 상자가 주문 상자보다 작거나 같다면 주문한 상자가 메인 컨테이너에 있다는 것이므로 찾을 때까지 pop한다. 이 때 메인 컨테이너가 비어있지 않아야 에러가 안뜬다. 2-1. 상자가 같다면 answer++해주고 break
3. 2번 조건이 아니라면 상자는 서브에 있다는 것. 서브 컨테이너에서는 더이상 옮길 곳이 없으므로 sub.top()이 주문한 상자가 아니라면 바로 break 3-1. 마찬가지로 같다면 answer++해주고 서브 컨테이너에서 pop해준다.

코드

#include <string>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

int solution(vector<int> order) {
    int answer = 0;

    queue<int> main;
    stack<int> sub;

    for(int i=1;i<=order.size();i++) // 메인 컨테이너 초기화
    {
        main.push(i);
    }

    for(int i=0;i<order.size();i++)
    {
        if(!main.empty() && main.front() <= order[i]) // 상자가 메인 컨테이너에 있다면
        {
            while(1)
            {
                int front = main.front();

                main.pop();
                if(front == order[i])
                {
                    answer++;
                    break;
                }
                sub.push(front);
            }
        }
        else // 상자가 서브 컨테이너에 있다면
        {
            if(sub.top() == order[i])
            {
                answer++;
                sub.pop();
            }
            else
            {
                break;
            }
        }
    }


    return answer;
}

[1차] 프렌즈4블록

풀이

테케 5번만 안풀리길래 뭐지 했는데 checkBoard에서 빈 칸일 때 continue 해줘야하는 걸, break 함..ㅋㅋ

1. 먼저 v에 초기화 해주고, while문을 돌려서 checkBoard가 true일 때 계속 반복해준다.
2. checkBoard는 터질 블럭이 있는지 체크하는 함수 2-1. 보드를 돌려보며 인덱스를 기준으로 오른쪽, 아래, 오른쪽 대각선 아래가 같은지 체크해서 같으면 터질 블럭으로 간주하고 set인 erase에 추가한다. (중복 블럭이 있을 수 있으니 바로 지우면 안됨) 2-2. 빈칸으로 네 개가 다 같아도 터질 블럭이라 간주하면 while문이 평생 안끝날 수도 있으니 빈 칸이면 continue 해준다.
3. eraseBlock은 블럭을 지우고 위에 있는 블럭들을 내리는 함수 3-1. erase를 돌면서 answer++해주고, 빈 칸으로 만들어준다. 3-2. 위에 행부터 밑으로 가면서 체크하는데, 방문하는 블럭 밑 칸이 빈칸일 경우 반복문을 통해 해당 블럭부터 0행까지 쫙 다 내려오게 한다. 내려오는 중에 빈칸인 블럭이 나온다면 위에도 빈칸이니까 바로 break
4. erase는 참조로 했기 때문에 clear를 잊지 않도록 한다.

코드

#include <string>
#include <vector>
#include <set>

using namespace std;
int answer = 0;

void eraseBlock(vector<vector<char>> &v, set<pair<int,int>> &erase)
{
    for(auto u:erase) // 지워질 블럭 '0'으로 체크
    {
        answer++;
        v[u.first][u.second] = '0';
    }

    for(int i=0;i<v.size()-1;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            if(v[i+1][j] == '0') // 밑에 있는게 지워질 블럭이라면
            {
                for(int k=i;k>=0;k--)
                {
                    if(v[k][j] == '0') break;
                    v[k+1][j] = v[k][j];
                    v[k][j]='0';
                }
            }
        }
    }
}

bool checkBoard(vector<vector<char>> &v, set<pair<int,int>> &erase) // 터질 블럭이 있는지 체크
{
    bool flag = false;
    for(int i=0;i<v.size()-1;i++)
    {
        for(int j=0;j<v[i].size()-1;j++)
        {
            if(v[i][j] == '0') continue;
            if(v[i][j] == v[i][j+1] && v[i][j] == v[i+1][j] && v[i][j] == v[i+1][j+1])
            {
                erase.insert({i, j});
                erase.insert({i, j+1});
                erase.insert({i+1, j});
                erase.insert({i+1, j+1});
                flag = true;
            }
        }
    }
    return flag;
}

int solution(int m, int n, vector<string> board) {    
    vector<vector<char>> v(m, vector<char>(n));
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            v[i][j] = board[i][j];
        }
    }

    set<pair<int,int>> erase;
    while(checkBoard(v, erase)) // 지울 블럭이 있다면
    {
        eraseBlock(v, erase); // 지우기
        erase.clear();
    }

    return answer;
}

두가지 형태의 타이머 구현

타이쿤 개발하면서 손님들의 개별 타이머와 전체 타이머를 구현했다. 개별 타이머는 바 형식, 전체 타이머는 숫자로 표현함 모두 코루틴을 이용하여 구현하였다.

숫자 형식의 타이머 (ToString Format)

처음에 00:00 포맷으로 어떻게 만들지 했는데 ToStrnig으로 포맷 지정을 할 수 있었다. minute.ToString("00") 형식으로 지정하면 알아서 포맷에 맞게 바꾸어줌

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
using TMPro;

public class Timer : MonoBehaviour
{
    [SerializeField] private TMP_Text text;

    [SerializeField] private float time;
    [SerializeField] private float curTime;

    int minute;
    int second;

    private void Awake()
    {
        time = 70;
        StartCoroutine(StartTimer());
    }

    IEnumerator StartTimer()
    {
        curTime = time;
        while(curTime > 0)
        {
            curTime -= Time.deltaTime;
            minute = (int)curTime / 60;
            second = (int)curTime % 60;
            text.text = minute.ToString("00") + ":" + second.ToString("00");
            yield return null;

            if(curTime <= 0)
            {
                Debug.Log("시간 종료");
                curTime = 0;
                yield break;
            }
        }
    }
}

바 형식의 타이머 (Image)

인스펙터에서 끌어다 줄 Image는 Image Type을 Filled로 바꾸어주고 Fill Method를 이용해 어떤 방식으로 줄어들지 고를 수 있다. Fill Amount를 조절하면서 확인하면 쉬움

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;

public class CustomerTimer : MonoBehaviour
{
    [SerializeField] private Image gauge;

    private float time = 20;
    private float timeSpeed;

    private float curTime;

    public bool isEnd;

    private void Awake()
    {
        isEnd = false;
        StartCoroutine(OrderTimer());
    }

    IEnumerator OrderTimer()
    {
        curTime = time;
        while(curTime > 0)
        {
            curTime -= Time.deltaTime * timeSpeed;
            gauge.fillAmount = curTime / time;
            yield return null;

            if(curTime <= 0)
            {
                isEnd = true;
                curTime = 0;
                yield break;
            }
        }
    }

    public void InitTimeSpeed(float speed)
    {
        timeSpeed = speed;
    }

    public void PlusTime(float plus)
    {
        curTime += plus;
        if(curTime>time)
        {
            curTime = time;
        }
    }
}

문제 링크

숫자 변환하기

풀이

BFS를 이용하는 문제

1. x와 y가 같다면 return 0 -> 이 처리를 안해줘서 하나 틀렸었음 1-1. queue에 {x,0} 값을 push, x는 현재 값, 0은 연산 횟수. visited[x]=1도 해준다.
2. q가 빌 때까지 반복한다. 2-1. 차례대로 num+n, num*2, num*3을 계산해서 계산 값이 y를 넘거나, 이미 방문했다면(방문했다면 그 연산횟수가 최소일테니) continue, calc[i]==y라면 숫자를 찾은거니 return cnt+1
3. q에 현재 값 push, 방문처리해준다.
4. 해당 반복문이 끝나도 return 처리가 안되는거면 y를 못찾은 채 y를 넘어버린 것이므로 (못찾은 것이므로) return -1

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int BFS(int x, int y, int n)
{
    queue<pair<int,int>> q;
    vector<int> visited(y+1);

    if(x==y) return 0; // 이미 x와 y가 같다면

    q.push({x,0});
    visited[x] = 1;

    while(!q.empty())
    {
        int num = q.front().first;
        int cnt = q.front().second;
        q.pop();

        int calc[3] = {num+n, num*2, num*3};
        for(int i=0;i<3;i++)
        {
            if(calc[i]>y) continue; // 계산 값이 y를 넘으면
            if(visited[calc[i]]==1) continue; // 이미 방문했던 숫자라면
            if(calc[i]==y) return cnt+1; // 찾으면 return

            q.push({calc[i],cnt+1});
            visited[calc[i]] = 1;
        }
    }

    return -1;
}

int solution(int x, int y, int n) {
    int answer = 0;

    answer = BFS(x,y,n);

    return answer;
}

문제 링크

[3차] 파일명 정렬

풀이

문자열과 커스텀 정렬로 푸는 문제 여기서 sort함수로 풀면 1,2번만 맞고 stable_sort로 푸니까 다 맞았다.. stable_sort는 두 요소 간의 순서를 보장하는 함수! 예를 들어 {1,5,4,5,3}이라는 벡터를 정렬 할 때 {1,3,4,5,5}로 정렬이 될텐데 그냥 sort는 5 요소 두 개가 같은 값이니 순서가 보장 되지 않아 앞의 5가 뒤로 갈 수 있지만, stable_sort는 이 두 개의 5 순서를 보장한다.

1. 구조체로 File을 정의해 name에는 원래 파일명, head와 number에는 문제대로 넣기로 한다.
2. seperate 함수를 이용해 파일명을 head와 number로 나눈다. tail은 정렬하는 데에 필요없으니 패스 2-1. file[i]이 숫자면 numberFlag를 true로 하고 number string에 넣어준다. 2-2. 문자인데 numberFlag가 false면 아직 number가 없었다는 뜻, 즉 head란 뜻이므로 head에 toupper로 대문자 변환해서 넣어준다. 대문자 변환을 하는 이유는 문제에서 대소문자 상관없이 처리하기 위함이다. 2-3. 문자인데 numberFlag가 true면 tail이라는 의미이므로 처리할 필요가 없어서break 2-4. 그렇게 완성된 head와 number를 구조체로 만들어 return. 정렬을 해야하기 때문에 number는 stoi로 int 형변환을 해준다.
3. 이제 커스텀 정렬을 해준다. 이를 위한 함수 compare은 구조체 File로 입력을 받아서 두 개의 head로 오름차순 정렬, head가 같다면 number로 정렬을 해준다.
4. 그렇게 정렬된 arr를 answer에 name만 push_back 해주면 끝.

코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

struct File
{
    string name;
    string head;
    int number;
};

File seperate(string file)
{
    string head = "";
    string number = "";
    bool numberFlag = false;

    for(int i=0;i<file.size();i++)
    {
        if('0'<=file[i] && file[i]<='9')
        {
            numberFlag = true;
            number+=file[i];
        }
        else
        {
            if(!numberFlag) head += toupper(file[i]);
            else break;
        }
    }


    File f = {file, head, stoi(number)};

    return f;
}

bool compare(File a, File b)
{
    if(a.head == b.head) return a.number < b.number;
    return a.head < b.head;
}

vector<string> solution(vector<string> files) {
    vector<string> answer;

    vector<File> arr;
    for(int i=0;i<files.size();i++)
    {
        arr.push_back(seperate(files[i]));
    }

    stable_sort(arr.begin(), arr.end(),compare);
    for(int i=0;i<arr.size();i++)
    {
        cout<<arr[i].head<<" "<<arr[i].number<<endl;
        answer.push_back(arr[i].name);
    }
    return answer;
}

문제 링크

행렬의 곱셈

풀이

행렬의 곱셈을 통해 2(행) X 3(열), 3 X 5 => 2 X 5의 행렬이 만들어짐 (첫번째 행렬의 열과 두번째 행렬의 행은 크기가 같아야 함)

이 행렬에서 (1,2)값을 구하고 싶다면? (0부터 시작하는 인덱스) [1][0]*[0][2] + [1][1]*[1][2] + [1][2]*[2][2]

1. arr1의 행이 i개, 열이 k개, arr2의 행이 k개, 열이 j개 일 때 행렬의 곱셈 결과는 i의 행과 j의 열이 만들어진다. 그렇게 answer의 사이즈를 미리 정해둔다.
2. 하나 하나씩 계산을 해준다. 2-1. arr1[i][k]*arr2[k][k]값을 모두 더해주면 answer[i][j]의 값이 나온다

코드

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    vector<vector<int>> answer(arr1.size(), vector<int>(arr2[0].size()));

    for(int i=0;i<answer.size();i++) // 행
    {
        for(int j=0;j<answer[i].size();j++) // 열
        {
            int tmp = 0;
            for(int k=0;k<arr2.size();k++)
            {
                tmp += arr1[i][k] * arr2[k][j];
            }
            answer[i][j] = tmp;
        }
    }
    return answer;
}

문제 링크

1091번: 카드 섞기

풀이

문제 해석을 잘못해서 조금 헤맸던 문제

1. Shake()함수에서 카드를 섞도록 한다. 1-1. tmp[S[i]] = arr[i]; 1-2. 한 번 섞을 때마다 answer++
2. 섞인 카드가 원하는 대로 가는지 확인하는 함수 Check() 2-1. P[arr[i]] != i%3 일 경우는 제대로 주어지지 않는다는 뜻이므로 false 리턴
3. Check()가 true 될 때까지 Shake() 하는데, 3-1. 이미 한 번 나온 카드 순서(arr)가 또 나올 경우, 계속 해도 원하는 카드의 순서가 안나온다는 의미 3-2. 이 것의 체크는 set으로 한다. 3-3. set에 있으면 -1 리턴, 없으면 set에 insert

코드

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int n;
vector<int> P;
vector<int> S;
vector<int> arr;
int answer = 0;

set<vector<int>> order;

bool Check()
{
    for (int i = 0; i < n; i++)
    {
        if (P[arr[i]] != i%3) return false;
    }
    return true;
}

void Shake()
{    
    if (Check())
    {
        cout << answer << endl;
        return;
    }

    vector<int> tmp(n);
    for (int i = 0; i < n; i++) // 섞기
    {
        tmp[S[i]] = arr[i];
    }
    arr = tmp;

    if (order.find(arr) != order.end()) // 이미 검사한 카드 순서라면
    {
        cout << -1 << endl;
        return;
    }
    order.insert(arr);

    answer++;

    Shake();
}

int main(void)
{
    cin >> n;

    P.resize(n);
    S.resize(n);

    for (int i = 0; i < n; i++)
    {
        cin >> P[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> S[i];
    }

    arr.resize(n);
    for (int i = 0; i < n; i++)
    {
        arr[i] = i;
    }

    Shake();

    return 0;
}

문제 링크

Find the Point

풀이

p와 q의 입력을 받고 q를 기준으로 p를 180도 회전하는 문제 q값에 q와 p의 차이를 더해주면 됨

코드

vector<int> findPoint(int px, int py, int qx, int qy) {
    vector<int> result;

    result.push_back(qx+qx-px);
    result.push_back(qy+qy-py);

    return result;
}

문제 링크

1439번: 뒤집기

풀이

1. 먼저 0의 구역 개수와 1의 구역 개수를 세는 fCnt, tCnt
2. 맨 처음 글자에 따라 영역 시작 개수를 센다.
3. 그 다음 글자부터 끝까지 체크를 하는데, 현재 글자가 이전 글자(영역) c와 다를 경우 구역이 나누어지기 때문에 해당 글자의 영역 개수를 추가하고 이전 글자(영역) c를 갱신한다.
4. 그렇게 만들어진 fCnt와 tCnt 값 중 작은 값을 출력

코드

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

int main()
{
    string s="";
    cin >> s;

    int fCnt = 0;
    int tCnt = 0;

    char c = s[0];
    if (c == '0')
    {
        fCnt++;
    }
    else
    {
        tCnt++;
    }

    for (int i = 1; i < s.size(); i++)
    {
        if (s[i] != c)
        {
            if (s[i] == '0') fCnt++;
            else tCnt++;
            c = s[i];
        }
    }

    int answer = fCnt > tCnt ? tCnt : fCnt;
    cout << answer << endl;

    return 0;
}

문제 링크

10162번: 전자레인지

풀이

1. 먼저 a, b, c를 초단위 변환 후 c로도 안나누어지면 못 만드는 시간이므로 -1 출력
2. a부터 차례대로 나누어 Cnt에 넣는다. t는 계속해서 갱신한다
3. cnt를 출력

코드

#include <iostream>
using namespace std;

int main()
{
    int t;
    cin >> t;

    int a = 300;
    int b = 60;
    int c = 10;

    int aCnt = 0;
    int bCnt = 0;
    int cCnt = 0;

    if (t%c != 0) cout << -1 << endl;
    else
    {
        aCnt = t / a;
        t %= a;
        bCnt = t / b;
        t %= b;
        cCnt = t / c;
        t %= c;

        cout << aCnt << " " << bCnt << " " << cCnt << endl;
    }
    return 0;
}

컨트롤 클래스 (핸들러 클래스)

기능의 처리를 실제로 담당하는 클래스

기능 제공의 핵심이 되기 때문에 모든 객체지향 프로그램에서 반드시 존재하는 클래스

상속을 사용하는 이유

데이터가 담긴 클래스와 그것을 관리하는 핸들러 클래스. 데이터가 담긴 클래스의 종류가 많아질 경우 핸들러 클래스에서 변경할 부분이 많아짐 → 확장성이 떨어짐 하지만, 상속을 사용하면 핸들러 클래스에서 변경이 거의 없어짐

상속의 방법과 결과

class UnivStudent : public Person
{
    ...
}

UnivStudent 클래스가 Person 클래스를 상속 → UnivStudent 객체에는 UnivStudent 클래스에 선언된 멤버, Person 클래스에 선언되어 있는 멤버 존재

상속의 대상이 되는 클래스의 멤버까지도 객체 내에 존재

상속받은 클래스의 생성자 정의

• 상속받은 클래스에서는 상속한 클래스의 초기화할 의무를 가짐
• 상속받은 클래스의 생성자에서 상속한 클래스의 생성자를 호출하는 형태로 초기화

UnivStudent(char* myname, int myage, char *mymajor)
    : Person(myname, myage)
{
    ...
}

이니셜라이저를 이용해 상속하는 클래스의 생성자 호출

상속에 대한 접근제한

접근제한의 기준은 클래스 → 상속 받은 클래스에서 상속하는 클래스의 private 선언 멤버에 접근 불가

정보의 은닉은 하나의 객체 내에서도 진행

상속 용어의 정리

상위 클래스 ↔ 하위 클래스 기초(base) 클래스 ↔ 유도(derived) 클래스 슈퍼(super) 클래스 ↔ 서브(sub) 클래스 부모 클래스 ↔ 자식 클래스

✨ 유도 클래스의 객체 생성과정

• 유도 클래스의 객체생성 과정에서 기초 클래스의 생성자는 100% 호출
• 유도 클래스의 생성자에서 기초 클래스의 생성자 호출을 명시하지 않으면, 기초 클래스의 void 생성자 호출

class SoDerived : public SoBase

SoDerived dr3(23,24);

1. 메모리 공간 할당
2. SoDerived의 생성자 호출
3. 상속하는 것을 확인 후, 이니셜라이저 확인 → 기초 클래스 생성자 호출
4. 해당하는 기초 클래스 생성자 호출이 완료되면 기초 클래스 멤버변수 초기화
5. 유도 클래스의 생성자 실행 완료되며, 유도 클래스 멤버변수 초기화

SoDerived dr1;

1. 메모리 공간 할당
2. SoDerived의 생성자 호출
3. 상속하는 것을 확인 후, 이니셜라이저 명시 X
4. 기초 클래스의 void 생성자를 대신 호출, 기초 클래스 멤버변수 초기화
5. 유도 클래스의 나머지 부분 실행 완료

클래스의 멤버는 해당 클래스의 생성자를 통해 초기화

유도 클래스 객체의 소멸과정

• 유도 클래스의 객체가 소멸될 때는, 유도 클래스의 소멸자가 실행되고 난 다음에 기초 클래스의 소멸자 실행
• 스택에 생성된 객체의 소멸순서는 생성순서와 반대

→ 생성자에서 동적 할당한 메모리 공간은 소멸자에서 해제

protected 선언

접근의 범위 : private < protected < pulic

protected로 선언된 멤버변수는 이를 상속하는 유도 클래스에서 접근 가능

기초 클래스와 유도 클래스 사이에서도 '정보은닉'은 지켜지는게 좋음

세가지 형태의 상속

class Derived : public Base // public 상속
{
    ...
}

class Derived : protected Base // protected 상속
{
    ...
}

class Derived : private Base // private 상속
{
    ...
}

protected 상속 : protected보다 접근의 범위가 넓은 멤버는 protected로 변경시켜 상속 private 상속 : private 상속을 다시 상속할 경우, 의미 없는 상속이 됨 public 상속 : private을 제외한 나머지는 그냥 그대로 상속

상속을 위한 조건

상속을 위한 기본 조건 : IS-A 관계의 성립

• 무선 전화기 is a 전화기
• 노트북 컴퓨터 is a 컴퓨터

HAS-A 관계도 상속의 조건은 되지만 복합 관계로 이를 대신하는 것이 일반적

상속으로 묶인 두 개의 클래스는 강한 연관성을 띔

const 객체

const SoSimple sim(20); 객체의 상수화 : 이 객체를 대상으로는 const 멤버 함수만 호출 가능

const의 유무도 함수 오버로딩의 조건에 해당이 됨 void SimpleFunc() {...} void SimpleFunc() const {...}

매개변수로 const 참조자로 받으면, const 멤버 함수를 호출

클래스와 함수에 대한 friend 선언

• A 클래스가 B 클래스를 대상으로 friend 선언 시, B 클래스는 A 클래스의 private 멤버에 접근 가능
• A 클래스도 B 클래스의 private 멤버에 직접 접근 가능하려면, B 클래스도 A 클래스 대상으로 friend 선언을 해야 함

class Boy
{
private:
    int height;
    friend class Girl; // Girl 클래스에서 Boy 클래스 멤버 변수 접근 가능
public:
    Boy(int len) : height(len)
    { }
    ....
}

friend class Girl; 의미

• Girl은 클래스의 이름이다 → 위에서 미리 선언하지 않아도 됨
• 바로 그 Girl 클래스를 friend로 선언

정보은닉을 무너뜨리기 때문에 되도록 사용하지 않고, 거의 연산자 오버로딩에서 사용됨

함수의 friend 선언 : 전역 함수와 클래스의 멤버함수를 대상으로 friend 선언 가능

C++에서의 static

static의 개념

• 전역변수에 선언된 static의 의미 : 선언된 파일 내에서만 참조를 허용하겠다는 의미
• 함수 내에 선언된 static의 의미 : 한번만 초기화되고, 지역변수와 달리 함수를 빠져나가도 소멸되지 않음

전역변수 사용 시 필요 없는 접근이 있을 수 있으므로 → 클래스 내에 static 멤버로 선언

static 멤버변수(클래스 변수) 일반 멤버변수와 달리 클래스당 하나씩만 생성 → 메모리 공간에 딱 하나만 할당 되어 공유됨, 객체 안에 존재하는 것이 아닌, 객체에게 멤버변수처럼 접근할 수 있는 권한을 준 것

static 변수를 생성자에서 초기화하면 안 되는 이유 : 객체가 생성될 때 생성되는 변수가 아니라, 이미 메모리 공간에 할당이 이뤄진 변수이기 때문 int SoSimple::simObjCnt=0;과 같이 초기화 → SoSimple 클래스의 static 멤버변수 simObjCnt가 메모리 공간에 저장될 때 0으로 초기화하라는 뜻

static 멤버변수의 또 다른 접근방법 static 멤버가 private 선언 : 해당 클래스의 객체들만 접근 가능 static 멤버가 public 선언 : 클래스의 이름, 객체의 이름을 통해 어디서든 접근 가능

static 멤버함수

• 선언된 클래스의 모든 객체가 공유
• public 선언 시, 클래스의 이름을 이용해 호출 가능
• 객체의 멤버로 존재하는 것이 아님
• static 멤버함수 내에서는 static 멤버변수와 static 멤버함수만 호출 가능

const static 멤버

클래스 내에 선언된 const 멤버변수(상수)의 초기화는 이니셜라이저를 통해야만 가능. but, const static으로 선언되는 멤버변수(상수)는 선언과 동시에 초기화 가능 const static int RUSSIA = 1707540;

const static 멤버변수는, 클래스가 정의될 때 지정된 값이 유지되는 상수

키워드 mutable

const 함수 내에서 값의 변경을 예외적으로 허용

C++ 스타일의 초기화

C++의 선언과 초기화는 int num=20; int &ref=num; 도 가능하고 int num(20); int &ref(num); 도 가능함

마찬가지로 SoSimple sim2=sim1; 는 SoSimple sim2(sim1);과 같음 sim2 객체를 새로 생성해, 객체 sim1과 sim2간의 멤버 대 멤버 복사가 일어남

복사 생성자

C++의 모든 객체는 생성자의 호출을 동반하므로, 위 문장에서 sim1을 인자로 받을 수 있는 생성자의 호출을 통해 객체생성을 완료함 → 이것이 복사 생성자

SoSimple(SoSimple &copy)
{
     ...
}

SoSimple sim2=sim1; → SoSimple sim2(sim1); 으로 묵시적 변환이 되어 객체 생성

복사 생성자의 이름은 생성자가 호출되는 시점이 다른 일반 생성자와 차이가 있기 때문에 붙음

SoSimple(const SoSimple &copy)
{
     ...
}

이렇게 const 키워드를 삽입해 원본이 변경되는 것을 막는 것이 좋다 (이것이 일반적인 복사 생성자)

디폴트 복사 생성자

복사 생성자를 정의하지 않으면, 멤버 대 멤버의 복사를 진행하는 디폴트 복사 생성자가 자동 삽입

복사 생성자를 반드시 정의해야 하는 경우가 있음

키워드 explicit

복사 생성자의 묵시적 호출을 허용하지 않는 키워드 explicit

SoSimple sim2=sim1;을 SoSimple sim2(sim1);로 변환시키지 않음 → 대입 연산자를 이용한 객체 생성 및 초기화 불가능

explicit SoSimple(const SoSimple &copy) : num1(copy.num1), num2(copy.num2)
{
    ...
}

전달인자가 하나인 생성자에도 explicit 선언하면, 묵시적 변환을 허용하지 않음 ex) AAA obj=3 불가능, AAA obj(3)으로만 가능

깊은 복사와 얕은 복사

디폴트 복사 생성자는 멤버 대 멤버의 복사를 진행 → 얕은 복사 이는 멤버변수가 힙의 메모리 공간을 참조하는 경우에 문제가 생김

디폴트 복사 생성자의 문제점 : 동적 할당으로 멤버변수를 정의 했다면(char *과 같은), 디폴트 복사 생성자로 멤버 대 멤버 복사를 진행 했을 때 주소를 복사하기 때문에, 하나의 문자열을 두 개의 객체가 동시에 참조함 한 객체의 소멸자에서 delete 연산을 하고, 다른 객체의 소멸자에서도 delete 연산을 하면 이미 지워진 문자열을 대상으로 delete 연산을 하기 때문에 문제 발생

깊은 복사를 위한 복사 생성자의 정의

객체 별로 각각의 문자열을 참조하게 만들면 소멸과정에서 문제가 발생하지 않음 → 멤버뿐만 아니라 포인터로 참조하는 대상까지 깊게 복사 : 깊은 복사

Person(const Person& copy) : age(copy.age)
{
    name = new char[strlne(copy.name)+1];
    strcpy(name, copy.name);
}

→ 이 생성자가 하는 일

• 멤버변수 age의 멤버 대 멤버 복사
• 메모리 공간 할당 후 문자열 복사, 할당된 메모리 주소 값 멤버 name 저장

복사 생성자의 호출 시점

• case 1 : 기존에 생성된 객체를 이용해 새로운 객체를 초기화 하는 경우
• case 2 : Call by value 방식의 함수호출 과정에서 객체를 인자로 전달하는 경우
• case 3 : 객체를 반환하되, 참조형으로 반환하지 않는 경우

메모리 공간의 할당과 초기화가 동시에 일어나는 상황 : int num1=num2; → num1이라는 메모리 공간을 할당과 동시에 num2에 저장된 값으로 초기화

int SimpleFunc(int n)
{
    ....
}
int main(void)
{
    int num=10;
    SimpleFunc(num);
}

→ 매개변수 n이 할당과 동시에 변수 num에 저장된 값으로 초기화

int SimpleFunc(int n)
{
    ...
    return n;
}
int main(void)
{
    int num=10;
    cout<<SimpleFunc(num)<<endl;
    ...
}

→ 반환하는 순간 메모리 공간이 할당되면서 동시에 반환 값으로 초기화 변수에 저장하는 것과 별개로, 값을 반환하면 반환된 값은 별도의 메모리 공간이 할당되어 저장 됨

이는 객체도 마찬가지

할당 이후 복사 생성자를 통한 초기화

SoSimple SimpleFuncObj(SoSimple ob)
{
    return ob;
}

라는 함수가 있는데 SimpleFuncObj(obj); 가 호출될 경우

1. ob 객체에 obj가 전달되며 ob의 복사 생성자 호출
2. 임시객체에 ob가 전달되며 임시객체의 복사 생성자 호출
3. 최종적으로 반환되는 객체는 임시객체, 함수호출이 완료되면 지역적으로 선언된 객체 ob는 소멸되고 임시객체와 obj 객체만 남음

임시 객체

Temporary(200); 과 같이 값을 저장하지 않고 호출하면 임시객체 생성 임시객체가 생성된 위치에는 임시객체의 참조 값이 반환 Temporary(200).ShowTempInfo();이면 (임시객체의 참조 값).ShowTempInfo();와 같은 형태 → 멤버함수의 호출 가능

참조 값이 반환되기 때문에 const Temporary &ref=Temporary(200);의 형태도 가능(상수 참조자)

• 임시객체는 다음 행으로 넘어가면 바로 소멸
• 참조자에 참조되는 임시객체는 바로 소멸되지는 않음

SoSimple tempRef=SimpleFuncObj(obj); 에서 SimpleFuncObj의 반환 값인 임시객체에 tempRef라는 이름을 할당해줌 (객체의 추가 생성 없이)

정보은닉

제한된 방법으로의 접근만 허용을 해서 잘못된 값이 저장되지 않도록 도와야 하고, 또 실수를 했을 때, 실수가 쉽게 발견되도록 해야 한다.

멤버변수를 prive 선언, 해당 변수에 접근하는 함수(엑세스 함수)를 별도로 정의 → 안전한 형태로 변수의 접근을 유도하는 것이 바로 정보은닉

엑세스 함수 : 클래스 외부에서 멤버변수 접근을 목적으로 정의되는 함수

const 함수 : 이 함수 내에서는 멤버변수에 저장된 값을 변경하지 않는 것을 선언, 이 함수 내에서는 const가 아닌 함수의 호출이 제한 → 코드의 안정성이 높아짐 int GetX() const; int GetY() const; void ShowRecInfo() const;

캡슐화

하나의 목적 하에 둘 이상의 기능이 모여 하나의 목적을 달성하기 위함 관련 있는 함수와 변수를 하나의 클래스 안에 묶는 것

캡슐화의 범위를 결정하는 일은 쉽지 않다

캡슐화는 기본적으로 정보은닉을 포함하는 개념

생성자

생성자를 이용해 객체를 생성과 동시에 초기화할 수 있음

class SimpleClass
{
private:
    int num;
public:
    SimpleClass(int n) // 생성자
    {
        num=n;
    }
    int GetNum() const
    {
        return num;
    }
}

생성자의 형태 : 클래스의 이름과 함수의 이름이 동일, 반환형이 선언되어 있지 않으며, 실제로 반환하지 않음 객체 생성시 딱 한번 호출

객체생성과정에서 자동으로 호출되는 생성자에게 전달할 인자의 정보를 추가 SimpleClass sc; → SimpleClass sc(20); SimpleClass *ptr = new SimpleClass; → SimpleClass *ptr = new SimpleClass(30);

• 생성자도 함수의 일종이니 오버로딩 가능
• 생성자도 함수의 일종이니 매개변수에 '디폴트 값' 설정 가능

매개변수가 없는 생성자를 이용해 객체 생성시 SimpleClass sc1;과 같이 소괄호 생략 소괄호는 밑과 같은 함수의 원형선언에만 사용

SimpleClass(int n1=0, int n2=0)
{
    num1=n1;
    num2=n2;
}

멤버 이니셜라이저

멤버 이니셜라이저를 이용한 멤버 초기화 : 멤버변수로 선언된 객체의 생성자 호출에 활용 :upLeft(x1, y1), lowRight(x2,y2) : 객체 upLeft 생성과정에서 x1과 y1을 인자로 전달받는 생성자 호출, 객체 lowRight 생성과정에서 x2와 y2를 인자로 전달 받는 생성자 호출

객체의 생성과정

• 1단계 : 메모리 공간의 할당
• 2단계 : 이니셜라이저를 이용한 멤버변수(객체)의 초기화
• 3단계 : 생성자의 몸체부분 실행

멤버 이니셜라이저를 이용한 변수 및 const 상수(변수) 초기화 : 객체가 아닌 멤버변수도 초기화 가능 num1(n1) : num1을 n1의 값으로 초기화

• 초기화의 대상을 명확히 인식 가능
• 성능에 약간의 이점 : 선언과 동시에 초기화가 이뤄지는 형태의 바이너리 코드 생성
• const 변수는 선언과 동시에 초기화해야 하므로 이니셜라이저를 이용해 초기화
• 참조자도 선언과 동시에 초기화가 이뤄져야 하므로 이니셜라이저를 이용해 초기화

디폴트 생성자

객체가 되기 위해서는 반드시 하나의 생성자가 호출되어야 함 → 생성자 정의가 없는 클래스에는 컴파일러에 의해 디폴트 생성자가 자동 삽입

디폴트 생성자는 인자를 받지 않고, 내부적으로 아무런 일도 하지 않음

AAA *ptr = new AAA;와 같은 new를 이용한 객체 생성에도 생성자 호출 그런데, AAA *ptr = (AAA*)malloc(sizeof(AAA));와 같은 malloc 함수호출시 생성자 호출이 안됨 객체 동적 할당시 반드시 new 연산자 이용

매개변수가 void형으로 선언되는 디폴트 생성자는, 생성자가 하나도 정의되어 있지 않을 때만 삽입 → 다른 형태로 객체생성이 불가능

private 생성자

객체의 생성이 클래스 외부에서 진행되면 public 선언 객체의 생성이 클래스 내부에서 진행되면 private 선언

소멸자

소멸자의 형태 : 클래스의 이름 앞에 ~가 붙은 형태의 이름, 반환형이 선언되어 있지 않으며, 실제로 반환하지 않음, 매개변수는 void형으로 선언되어야 하기 때문에 오버로딩도, 디폴트 값 설정도 불가능 ~AAA() {...}

소멸자는 객체소멸 과정에서 자동으로 호출 직접 소멸자를 정의하지 않으면, 디폴트 생성자와 마찬가지로 아무런 일도 하지 않는 디폴트 소멸자 자동 삽입

소멸자의 사용 : 생성자에서 할당한 리소스의 소멸에 사용 ex) 생성자 내에서 new 연산자로 할당해 놓은 메모리 공간을, delete 연산자를 이용해 이 메모리 공간 소멸

클래스와 배열

객체 기반의 배열 : SoSimple arr[10]; 동적 할당 : SoSimple *ptrArr = new SoSimple[10];

배열을 선언하는 경우에도 생성자 호출이 되지만, 호출할 생성자들 별도로 명시하지 못함(생성자에 인자를 전달하지 못함) → SoSimple() {...} 의 생성자가 정의되어야 함

객체 포인터 배열 : 객체의 주소 값 저장이 가능한 포인터 변수로 이뤄진 배열 Person * parr[3];

객체를 저장할 때는 저장의 대상을 1. 객체로 하느냐 2. 객체의 주소 값으로 하느냐 결정해야함

this 포인터

객체 자신을 가리키는 용도로 사용되는 포인터

SoSimple * GetThisPointer()
{
    return this;
}

this는 객체자신의 주소 값을 의미

매개변수와 멤버변수의 이름이 같을 때는 this 포인터를 이용해 접근 this->num=207;

멤버 이니셜라이저에서는 this 포인터를 사용할 수 없지만, 저장하는 변수는 멤버변수로, 저장되는 값은 매개변수로 인식하기 때문에, 그냥 써도 됨 :num1(num1), num2(num2)

Self-Reference의 반환

Self-Reference : 객체 자신을 참조할 수 있는 참조자

SelfRef& Adder(int n)
{
    num+=n;
    return *this;
}

객체 자신을 참조할 수 있는 참조의 정보(참조 값) 반환

참조의 정보(참조 값)에 대한 이해 : int num=7; int &ref=num; 이면 참조자 ref에 변수 num을 참조할 수 있는 참조의 정보가 전달됨 대입 연산자의 왼편에 '참조자의 선언'이 오거나, 반환형으로 '참조형'이 선언되면, 그 때 전달되는 정보를 표현하기 위해 '참조의 정보' 또는 '참조 값'이라 표현

문제 링크

1004번: 어린 왕자

풀이

기하 문제

1. 입력 받은 각 원마다 check 함수 호출
2. 출발 지점과 도착 지점이 원 내부에 같이 있으면 경계를 안넘어도 되므로 return 0 2-1. 둘 중 하나만 원 내부에 있으면 경계를 넘어야 하므로 return 1 2-2. 둘 다 밖에 있을 경우도 return 0
3. answer에 반환값을 저장해 출력한다.

코드

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

int x, y, x2, y2;

bool check(int cx, int cy, int r)
{
    if (pow(cx - x, 2) + pow(cy - y, 2) <= r * r && pow(cx - x2, 2) + pow(cy - y2, 2) <= r * r) return 0;
    else if (pow(cx - x, 2) + pow(cy - y, 2) <= r * r) return 1;
    else if (pow(cx - x2, 2) + pow(cy - y2, 2) <= r * r) return 1;
    return 0;
}

int main(void)
{
    int t;
    cin >> t;

    for (int i = 0; i < t; i++)
    {
        cin >> x >> y >> x2 >> y2;

        int n;
        cin >> n;

        int answer = 0;
        for (int i = 0; i < n; i++)
        {
            int cx, cy, r;
            cin >> cx >> cy >> r;
            answer += check(cx, cy, r);
        }

        cout << answer << endl;
    }

    return 0;
}

문제 링크

1358번: 하키

풀이

간단한 기하 문제

1. 먼저 선수들의 위치를 입력받아 check 함수를 호출한다.
2. check 함수는 각각 직사각형, 왼쪽 반원, 오른쪽 반원 내에 있는지 체크해서 return한다. 2-1. 직사각형의 왼쪽 아래 점과 오른쪽 위에 점 내부에 있으면 return 2-2. 반원은, 원 중심 좌표와 선수들의 위치 사이 거리를 계산해 반지름보다 작다면 return한다.

코드

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

int w, h, x, y;

bool check(int px, int py)
{
    if (x <= px && px <= x + w && y <= py && py <= y + h) // 직사각형 내부
    {
        return 1;
    }
    else if (pow(x - px, 2) + pow(y + h / 2 - py, 2) <= pow(h / 2, 2))
    {
        return 1;
    }
    else if (pow(x + w - px, 2) + pow(y + h / 2 - py, 2) <= pow(h / 2, 2))
    {
        return 1;
    }
    return 0;
}

int main(void)
{
    int p;
    int answer = 0;
    cin >> w >> h >> x >> y >> p;
    for (int i = 0; i < p; i++)
    {
        int px, py;
        cin >> px >> py;
        answer += check(px, py);
    }

    cout << answer << endl;

    return 0;
}