GitHub Pages는 GitHub의 Repository의 올린 코드에 따라 웹 페이지를 간단하게 호스팅할 수 있는 깃허브의 기능

• 일반적으로 웹에 호스팅을 하려면 돈을 내고 또는 무료로 저성능의 서버를 얻고 호스팅을 하는데, 금전적인 문제가 생기거나, 무료로 하려면 세팅이 번거로움
• GitHub Pages을 쓰는게 매우 간편
• 기본적으로 pages는 최상위 폴더(root)의 index.html을 가리키며, 해당 파일이 존재하지 않으면 README.md를 띄워준다고 함

2. Settings

2-1. gh-pages 패키지 설치

npm install gh-pages

2-2. Repository

• 소스가 올라가 있는 레포 설정에서 브랜치를 gh-pages로 바꿔주고 좀 기다리면 위에 호스팅 url이 생김 (https://shinhn.github.io/React/)

2-3. package.json 수정

1. package.json 에 필요한 옵션 추가 (참고) 배포할 때 에러 나서 deploy 명령어를 빌드 할 때 생기는 문서 이름인 dist로 바꿔주니 잘 되더라

    "predeploy": "npm run build"
    "deploy": "gh-pages -d dist" 
    "homepage": "https://shinhn.github.io/React/"

2. 소스 한번 더 git에 올려주고

2-4. 빌드 및 배포

1. JSX 파일을 브라우저에 띄우기 위해서 브라우저가 이해할 수 있는 언어인 SS, JS, HTML 문법으로 바꿔주는 작업이 필요한데, 이걸 컴파일 또는 build라고 함
2. 터미널에서 빌드하면 dist에 필요한 문서가 생기는 걸 볼 수 있음

   npm run build

3. 터미널에서 deploy 해줬을 때 아래처럼 되면 잘 된 거

   npm run deploy

   

3. Result

이제 https://shinhn.github.io/React/ 들어가보면 호스팅 되어 있는 걸 알 수 있음

강의 들으면서 이것저것 갖다 붙인 거라 결과물이 너무 조잡한 관계로 결과는 스킵.. 암튼 잘 호스팅 되더라~

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42862#

풀이

- vector.erase()

1. 특정 인덱스 삭제 v.erase(v.begin() + idx);
2. 특정 범위 모든 값 삭제 v.erase(v.begin(), v.end());

- (참고) remove()

특정 값 삭제 remove(v.begin(), v.end(), num);

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

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;

    for(int i=0;i<lost.size();i++){
        for(int j=0;j<reserve.size();j++){
            if(lost[i] == reserve[j]){ // 여벌 체육복을 가져온 학생이 체육복을 도난당한 경우 -> 남은 체육복이 하나이기에 두 벡터에서 모두 제거
                lost.erase(lost.begin()+i);
                reserve.erase(reserve.begin()+j);

                i--; // lost 벡터에서 원소 하나를 지웠으므로 반복문 인덱스도 한칸 줄임
            }
        }
    }

    // 맨 앞부터 체육복을 빌려주기(greedy) 위한 정렬
    sort(lost.begin(), lost.end());
    sort(reserve.begin(), reserve.end());

    answer = n - lost.size();

    for(int i=0;i<lost.size();i++){
        for(int j=0;j<reserve.size();j++){
            if(lost[i]-1 == reserve[j] || lost[i]+1 == reserve[j]){ // 바로 앞이나 뒤에 빌려줄 사람이 있는 경우
                answer++;
                reserve.erase(reserve.begin()+j);
                break;
            }
        }
    }

    return answer;
}

SELECT ANIMAL_ID, NAME FROM ANIMAL_INS;
SELECT ANIMAL_ID, NAME AS '이름' FROM ANIMAL_INS;

WHERE

- AND, OR

SELECT userID, Name FROM usertbl WHERE birthYear >= 1970 AND height >= 182;
SELECT userID, Name FROM usertbl WHERE birthYear >= 1970 OR height >= 182;

- BETWEEN A AND B

SELECT name, height FROM usertbl WHERE height BETWEEN 180 AND 183;

- IN ('A','B' ... 'C')

SELECT name, addr FROM usertbl WHERE addr IN ('경남','전남','경북');

- LIKE '%~%'

SELECT name, height FROM usertbl WHERE name LIKE '김%';

ORDER BY

• 동물 보호소에 들어온 모든 동물의 아이디와 이름, 보호 시작일을 이름 순으로 조회
• 단, 이름이 같은 동물 중에서는 보호를 나중에 시작한 동물을 먼저 조회

SELECT ANIMAL_ID, NAME, DATETIME FROM ANIMAL_INS ORDER BY NAME, DATETIME DESC;

LIMIT

• 동물 보호소에 가장 먼저 들어온 동물의 이름을 조회

  SELECT NAME FROM ANIMAL_INS ORDER BY DATETIME LIMIT 1;

SUM, MAX, MIN

• 가장 최근에 들어온 동물은 언제 들어왔는지 조회

  SELECT MAX(DATETIME) AS '시간' FROM ANIMAL_INS;

• 가장 먼저 들어온 동물은 언제 들어왔는지 조회

SELECT MIN(DATETIME) AS '시간' FROM ANIMAL_INS;

GROUP BY

• 고양이와 개가 각각 몇 마리인지 조회
• 이때 고양이를 개보다 먼저 조회

SELECT ANIMAL_TYPE, COUNT(ANIMAL_TYPE) AS 'count' FROM ANIMAL_INS GROUP BY ANIMAL_TYPE ORDER BY ANIMAL_TYPE;

- HAVING

• 동물 이름 중 두 번 이상 쓰인 이름과 해당 이름이 쓰인 횟수를 조회
• 이름이 없는 동물은 집계에서 제외하며, 결과는 이름 순으로 조회

SELECT NAME, COUNT(NAME) AS 'COUNT' FROM ANIMAL_INS GROUP BY NAME HAVING COUNT >= 2 ORDER BY NAME;

CASE WHEN

TRUNCATE(숫자,버릴 자릿수)

• 만원 단위의 가격대 별로 상품 개수를 출력
• 이때 컬럼명은 각각 컬럼명은 PRICE_GROUP, PRODUCTS로 지정
• 가격대 정보는 각 구간의 최소금액(10,000원 이상 ~ 20,000 미만인 구간인 경우 10,000)으로 표시
• 가격대를 기준으로 오름차순 정렬

SELECT TRUNCATE(PRICE, -4) AS PRICE_GROUP, COUNT(*) AS PRODUCTS
FROM PRODUCT GROUP BY PRICE_GROUP ORDER BY PRICE_GROUP;

LEFT JOIN

https://school.programmers.co.kr/learn/courses/30/lessons/133026

SELECT INGREDIENT_TYPE, SUM(TOTAL_ORDER) AS TOTAL_ORDER
FROM FIRST_HALF LEFT JOIN ICECREAM_INFO ON FIRST_HALF.FLAVOR = ICECREAM_INFO.FLAVOR
GROUP BY INGREDIENT_TYPE;

IS NULL

• 이름이 없는 동물의 ID를 조회

SELECT ANIMAL_ID FROM ANIMAL_INS WHERE NAME IS NULL;

• 이름이 있는 동물의 ID를 조회

SELECT ANIMAL_ID FROM ANIMAL_INS WHERE NAME IS NOT NULL;

DATE_FORMAT

- YYYY/mm/dd 포맷

SELECT DATE_FORMAT('20200405','%Y/%m/%d')

-> 2020/04/05

- YYYY-mm-dd 포맷

SELECT DATE_FORMAT('20200405','%Y-%m-%d')

-> 2020-04-05

- 영어 표기로 변환

SELECT DATE_FORMAT('2020-04-05', '%W %M %Y');

-> Sunday April 2020

- 여러 지정값

DATE_FORMAT 지정값

DATEDIFF

• 대여 시작일이 2022년 9월에 속하는 대여 기록에 대해서
• 대여 기간이 30일 이상이면 '장기 대여' 그렇지 않으면 '단기 대여' 로 표시하는 컬럼(컬럼명: RENT_TYPE)을 추가하여 대여기록을 출력
• 결과는 대여 기록 ID를 기준으로 내림차순 정렬

SELECT
    HISTORY_ID,
    CAR_ID,
    DATE_FORMAT(START_DATE, '%Y-%m-%d') AS START_DATE,
    DATE_FORMAT(END_DATE, '%Y-%m-%d') AS END_DATE,
    CASE
        WHEN DATEDIFF(END_DATE, START_DATE) + 1 >= 30 THEN "장기 대여"
        ELSE "단기 대여"
    END AS RENT_TYPE
FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY
WHERE START_DATE BETWEEN '2022-09-01' AND '2022-09-30'
ORDER BY HISTORY_ID DESC;

• 유의할 점은 오늘 대여하고 오늘 반납해도 대여 기간은 하루이기 때문에 (END_DATE - START_DATE ) + 1 >= 30으로 계산해야 함

Reference

https://school.programmers.co.kr/learn/challenges?tab=sql_practice_kit https://paris-in-the-rain.tistory.com/100

문제

https://school.programmers.co.kr/learn/courses/30/lessons/86971

풀이

전선이 하나 끊어진 모든 경우에 따라 dfs로 두개의 네트워크의 크기를 구하는 문제

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

using namespace std;

int graph[101][101];
bool visited[101];

int dfs(int node, int n){
    if(visited[node]) return 0;
    visited[node] = true;

    int network_size = 1;

    for(int i=1;i<=n;i++){
        if(graph[node][i] == 1){
            network_size += dfs(i, n);
        }
    }

    return network_size;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 100;

    for(int i=0;i<wires.size();i++){
        int n1 = wires[i][0];
        int n2 = wires[i][1];
        graph[n1][n2] = 1;
        graph[n2][n1] = 1;
    }

    for(int i=0;i<wires.size();i++){
        // 전선 하나 끊음
        int n1 = wires[i][0];
        int n2 = wires[i][1];
        graph[n1][n2] = 0;
        graph[n2][n1] = 0;

        // 초기화
        fill(visited, visited + 101, false);

        // 각 네트워크 사이즈 측정
        vector<int> net_sizes;
        for(int j=1;j<=n;j++){
            int net_size = dfs(j, n);
            if(net_size != 0) net_sizes.push_back(net_size);
        }

        if(abs(net_sizes[0] - net_sizes[1]) < answer){
            answer = abs(net_sizes[0] - net_sizes[1]);
        }

        // 다시 전선 연결
        graph[n1][n2] = 1;
        graph[n2][n1] = 1;
    }

    return answer;
}

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

풀이

1. STL 사용

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

using namespace std;

int N;
vector<int> arr;

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

    cin >> N;

    for(int i=1;i<=N;i++){
        arr.push_back(i);
    }

    do{
        for(int i=0;i<N;i++){
            cout << arr[i] << " ";
        }
        cout << "\n";
    }while(next_permutation(arr.begin(), arr.end()));

    return 0;
}

2. 직접 구현 (브루트포스, dfs)

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

using namespace std;

int N;
int arr[9];
bool used[9];

void func(int idx){
    if(idx == N){
        for(int i=0;i<N;i++){
            cout << arr[i] << " ";
        }
        cout << "\n";
    }

    for(int i=1;i<=N;i++){
        if(used[i] == true) continue;

        used[i] = true;
        arr[idx] = i;
        func(idx+1);
        used[i] = false;
    }
}

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

    cin >> N;

    func(0);

    return 0;
}

상호 배타적 집합(disjoint set)을 표현하는데에 쓰는 자료구조이다. 상호 배타적 집합은, 서로 공통원소가 없는 집합을 의미한다.

필요한 이유

어떤 파티에 n명의 사람이 왔다고 하자. 레크레이션 강사가 생일이 같은 사람들끼리 뭉치라고 했을 때, 처음에는 모두 혼자 돌아다니다, 생일이 같은 사람을 찾게 되면 그 사람들 끼리는 팀을 이루어 함께 움직이게 된다. 다른 팀을 만났을 때, 생일이 같다는것을 알게 되면 두 팀은 뭉쳐서 한 팀을 구성하는 식으로 움직인다.

파티에 온 사람들의 전체 집합으로 놓고 보면, 팀은 이 집합을 여러개의 부분집합으로 쪼갠것 이다. 각 팀은 생일이 같은 사람들로 구성되었기 때문에, 두 개 이상의 팀에 속한 사람은 없다는 점에 유의하자. 이렇게 공통 원소가 없는, 다시말해 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조가 바로 유니온-파인드 구조이다.

이러한 것들을 컴퓨터 언어에서 다룰 수 있게 해주는 유니온-파인드 구조가 할 수 있어야 하는 연산은 다음과 같다.

1. 초기화 : n개의 원소가 각각의 집합에 포함되어 있도록 초기화
2. 합치기(union) 연산 : 두 원소 a,b가 주어질 때, 이들이 속한 두 집합을 하나로 합침
3. 찾기(find) 연산 : 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환

초기화 연산은 처음 구조를 만들때 외에는 그렇게 자주 쓰지 않으니, 상대적으로 자주 쓰는 두 연산의 이름을 따서 union-find 자료구조라고 한다.

구현1 (배열)

union-find 자료구조를 구현하는 가장 간단한 방법은 1차원 배열 하나를 이용해서 아래와 같이 만드는 것이다.

belongsTo[i] = i번 원소가 속하는 집합의 번호

처음에는 belongsTo[i] = i로 두면, 찾기 연산을 상수 시간안에 할 수 있다.

하지만 이 방법의 문제는 합치기 연산이다. 합치기 연산을 위해서는 belongsTo[]의 모든 원소를 순회하면서 한쪽 집합에 속한 원소들을 다른쪽 원소의 집합으로 옮겨야 하는데, 모든 원소를 순회하는데에는 O(N)의 시간이 걸린다.

찾기 연산이 O(1)이라는 사실은 매우 좋으나, 합치기 연산의 비용이 크기 때문에 다른 방법을 고안해볼 필요가 있다.

구현2 (트리)

배열표현의 "합치기 연산이 느리다"라는 단점을 극복하는 좋은 방법 중 하나는, 트리를 이용해서 이를 구현하는 것이다.

두 원소가 같은 트리에 속해있는지 확인하는 방법인 찾기(find) 연산 👉 원소가 속해있는 트리의 루트가 같은지를 비교하는 것

int parent[1000001];

int find(int node){ // 같은 집합인지 확인 (같은 뿌리인지 확인)
    if(parent[node] == node) return node; // 뿌리 노드일 경우 본인 리턴
    else return parent[node] = find(parent[node]); // 경로 압축 최적화
}

void uni(int a, int b){ // 합집합 (a 집합을 b 집합의 자식노드로 합침)
    int rootA = find(a);
    int rootB = find(b);

    parent[rootA] = rootB;
}

void init(){ // 부모 배열 초기화
    for(int i=0;i<=n;i++){
        parent[i] = i;
    }
}

• 트리와 루트는 항상 1:1 대응되므로(루트가 2개 이상 있는 트리는 존재하지 않으니까) 루트가 같다면 두 원소가 같은 트리에 있음을 자명하게 알 수 있다.

• 위의 연산을 구현하기 위해서 자식 노드들이 부모 노드의 정보를 알고 있어야 한다.

  • 하지만, 부모 노드는 자식 노드에게 갈 일이 없기 때문에 자식 노드에 대한 정보를 저장할 필요가 없다.
  • 또, 루트는 그 부모가 없으므로, 자기 자신을 부모로 지정한다.

시간복잡도

• find()의 시간 복잡도는 대상이 되는 트리의 높이에 비례하는 시간이 걸린다.
• 집합(트리)을 합치는 uni()함수의 시간복잡도 또한 find가 지배하기 때문에, 이 역시 트리의 높이에 비례한다.

- 최적화 (경로 압축 최적화)

find(u)를 통해서, 찾아낸 u가 속한 트리의 루트를 parent[u]에 반영한다면, 다음에 find(u)가 호출되었을 때, 경로를 찾아갈 필요 없이 빠르게 루트를 찾을 수 있다.

예제 : boj 1717 집합의 표현

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

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

using namespace std;

int n, m;
int u, a, b;
int parent[1000001];

int find(int node){ // 같은 집합인지 확인 (같은 뿌리인지 확인)
    if(parent[node] == node) return node; // 뿌리 노드일 경우 본인 리턴
    else return parent[node] = find(parent[node]); // 경로 압축 최적화
}

void uni(int a, int b){ // 합집합 (a 집합을 b 집합의 자식노드로 합침)
    int rootA = find(a);
    int rootB = find(b);

    parent[rootA] = rootB;
}

void init(){ // 부모 배열 초기화
    for(int i=0;i<=n;i++){
        parent[i] = i;
    }
}

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

    cin >> n >> m;

    init();

    for(int i=0;i<m;i++){
        cin >> u >> a >> b;

        if(u == 0){
            uni(a,b);
        }
        if(u == 1){ 
            if(find(a) == find(b)) cout << "YES" << "\n";
            else cout << "NO" << "\n";
        }
    }

    return 0;
}

Reference

https://velog.io/@kasterra/%EB%AA%85%EC%98%88-STL-union-find-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0

문제

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

풀이

dp로 풀면 시간 복잡도가 n제곱이 나오는데 이 문제는 n의 최댓값이 1,000,000이므로 n제곱으로 풀면 시간초과가 난다. 👉 이분탐색

dp를 통해 가장 긴 증가하는 부분 수열을 푸는 문제도 있으니 풀어보도록 하자. [boj] (s2) 11053 가장 긴 증가하는 부분 수열

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

using namespace std;

int N, ans=1;
int arr[1000001];
vector<int> permutation;

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

    cin >> N;

    for(int i=0;i<N;i++){
        cin >> arr[i];
    }

    permutation.push_back(arr[0]);
    for(int i=1;i<N;i++){
        if(arr[i] > permutation.back()){
            permutation.push_back(arr[i]);
        }
        else{
            // arr[i] 보다 크나 같은 값이 처음으로 나타나는 위치에 넣음 (대치)
            int idx = lower_bound(permutation.begin(), permutation.end(), arr[i]) - permutation.begin();
            permutation[idx] = arr[i];
        }
    }

    cout << permutation.size() << "\n";

    return 0;
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43236

풀이

https://mjmjmj98.tistory.com/78

n개의 바위를 빼보며 모든 경우의 수를 따져보기에는 시간초과가 남. 바위 사이의 최소 거리 중 최대 값을 이분탐색으로 가능한지 따져 찾음

이전에 풀었던 [boj] (g4) 2110 공유기 설치 와 흡사한 문제

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

using namespace std;

bool isPossible(int distance, vector<int> rocks, int n, int min_dist){

    int prev = 0; // 시작점
    int cnt = 0; // 제거할 바위의 수

    for(int i=0;i<rocks.size();i++){
        if(rocks[i] - prev < min_dist){ // 바위 제거
            cnt ++;
        }
        else prev = rocks[i];
    }
    if(distance - prev < min_dist) cnt++;

    if(cnt <= n) return true;

    return false;
}

int solution(int distance, vector<int> rocks, int n) {
    int answer;

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

    int low = 0, high = distance;
    while(low <= high){
        int mid = (low + high)/2;

        if(isPossible(distance, rocks, n, mid)){
            answer = mid;
            low = mid + 1;
        }
        else high = mid - 1;
    }

    return answer;
}

문제

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

풀이

집의 개수 N이 최대 200,000 개 이므로 모든 경우의 수를 세어서 구할 수 없음 O(200,000^2) -> 이분탐색을 통해 가장 인접한 두 공유기 사이의 거리를 최대로 갖는 사이 거리를 찾을 수 있음

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

using namespace std;

int N, C, ans = 0;
int house[200001];

bool isPossible(int dist){ // dist : 가장 인접한 두 공유기 사이의 거리

    int cnt = 1; // 첫번째 집에 공유기 설치하고 시작
    int prev = house[0];

    for(int i=1;i<N;i++){
        if(house[i]-prev >= dist){ // 가장 인접한 두 공유기 사이의 거리의 최댓값이 dist가 되어야 하므로 dist 보다 멀리 떨어져 있는 경우에만 공유기 설치
            cnt ++;
            prev = house[i];
        }
    }

    if(cnt >= C) return true;

    return false;
}

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

    cin >> N >> C;

    for(int i=0;i<N;i++){
        cin >> house[i];
    }

    sort(house, house + N);

    int low = 1, high = house[N-1] - house[0]; // 인접한 두 공유기 사이 거리 범위는 1 ~ (첫째 집에서 마지막 집까지의 거리)
    while(low <= high){
        int mid = (low + high)/2;

        if(isPossible(mid)) {
            ans = mid;
            low = mid + 1;
        }
        else high = mid - 1;
    }

    cout << ans << "\n";

    return 0;
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43238

풀이

https://0xd00d00.github.io/2021/06/29/programmers_entry_test.html

각 심사대는 동시에 심사를 하기 때문에 실제 심사처럼 생각하면 계산하기 복잡하다. 동시에 심사를 하기 때문에 인당 몇분이 걸리는지가 아니라, 각 심사대가 1분에 몇명 심사를 하는지 계산하면 각 심사대는 동시에 심사하여 총 n 명을 심사하는데 얼마나 걸리는지 계산하기 편함

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;

    long long low = 1;
    long long high = n*((long long)*max_element(times.begin(), times.end())); // 주의 : vector는 int형이므로 형변환을 해줘야 함

    while(low <= high){
        long long mid = (low+high)/2;

        long long people = 0; // 심사를 마친 사람의 수
        for(int i=0;i<times.size();i++){
            people += mid/times[i];
        }

        if(n <= people) {
            answer = mid;
            high = mid - 1;
        }
        else low = mid + 1;
    }

    return answer;
}

문제

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

풀이

N이 최대 10이므로 모든 도시를 가보는 경우의 수는 N을 일렬로 세우는 방법의 수와 같으므로 최대 10! 이다. 즉, 모든 경우를 다 가보고 최소 비용을 출력하면 됨 -> 완탐 -> dfs

• 주의 : 시작점으로 돌아가야 하기 때문에 시작점으로 돌아가는 비용도 더해줘야 한다.

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

using namespace std;

int N;
int W[11][11];
bool visited[11];
int ans=2e9; // 비용
int start_city; // 출발 도시

void dfs(int node, int cnt_visited, int cnt){
    if(cnt_visited == N) { // 모든 도시 방문했을 경우
        if(W[node][start_city] > 0) ans = min(ans, cnt+W[node][start_city]); // 시작점으로 돌아갈 수 있다면 비용 추가
        return;
    }

    for(int i=1;i<=N;i++){
        if(W[node][i] == 0) continue;
        if(visited[i]) continue;

        visited[i] = true;
        dfs(i, cnt_visited+1, cnt + W[node][i]);
        visited[i] = false;
    }
}

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

    cin >> N;

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

    for(int i=1;i<=N;i++){ // 시작도시
        start_city = i;

        visited[i] = true;
        dfs(i, 1, 0);
        visited[i] = false;
    }

    cout << ans << "\n";

    return 0;
}

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

풀이

K <= N <= 1,000,000 K는 10,000 이하이기 때문에 모든 K개의 랜선을 잘라가며 총 N개를 만들 수 있는 길이를 찾으려면 1,000,000 x 10,000 = 10,000,000,000 -> 시간초과 👉 따라서 _이분탐색_으로 찾아보자.

랜선의 길이는 231-1보다 작거나 같은 자연수이기 때문에 랜선의 길이를 갖는 변수는 long long형을 사용해야 한다.

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

using namespace std;

int K, N;
long long cable[10001];
long long low = 1, high = 0, ans;

int Cnt_cable(long long size){
    int sum = 0;
    for(int i=0;i<K;i++){
        sum += cable[i]/size;
    }

    return sum;
}

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

    cin >> K >> N;

    for(int i=0;i<K;i++){
        cin >> cable[i];
        high = max(high, cable[i]);
    }

    while(low <= high){
        long long mid = (low + high)/2;

        if(Cnt_cable(mid) >= N) {
            low = mid + 1;
            ans = mid;
        }
        else high = mid - 1;
    }

    cout << ans << "\n";

    return 0;
}

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

풀이

1 ≤ X ≤ 1,000,000,000 이므로 승률(Z)이 변하는 값을 선형탐색하여 찾으려면 시간초과가 남 따라서 이진탐색 이용

• long long 형 사용
• 주의 : 99%는 아무리 해도 100%가 되지 못한다.

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

using namespace std;

long long X, Y, Z;

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

    cin >> X >> Y;

    Z = Y*100/X;

    if(Z >= 99){ // 99%는 아무리 해도 100%가 되지 못한다.
        cout << -1 << "\n";
        return 0;
    }

    long long left=0, right=1000000000, ans;
    while(left <= right){
        long long mid = (left + right)/2;

        long long win_per = (Y+mid)*100/(X+mid);
        if(win_per <= Z) left = mid + 1;
        else {
            ans = mid;
            right = mid - 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

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

풀이

• 배정된 예산들 중 최댓값은 상한액일 수도, 요청한 예산을 모두 줄 수 있어 그중 최댓값일 수도 있다.
• 따라서 요청한 예산의 최솟값 ~ 최댓값 안에 구하고자 하는 값이 있는데, 구하고자 하는 값이 요청한 예산들을 모두 만족하는지 확인해야 한다.
• 완전탐색으로 풀게되면 요청 예산의 수 (지방의 수) N은 3 이상 10,000 이하이므로 최악의 경우 10,000 x 10,000 = 1억이므로 시간초과가 날 수 있다.

따라서 _이분 탐색_을 통해 범위를 반씩 줄여가며 탐색한다.

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

using namespace std;

int N, M;
int arr[100001];
int high, low = 0, ans;

bool isPossible(int mid){
    int sum = 0;

    for(int i=0;i<N;i++){
        if(arr[i] < mid) sum += arr[i];
        else sum += mid;
    }

    if(sum <= M) return true;

    return false;
}

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

    cin >> N;
    for(int i=0;i<N;i++){
        cin >> arr[i];
        high = max(high, arr[i]);
    }
    cin >> M;

    while(low <= high){
        int mid = (low + high)/2;

        if(isPossible(mid)) {
            ans = mid;
            low = mid + 1;
        }
        else high = mid - 1;
    }

    cout << ans << "\n";

    return 0;
}

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

풀이

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

using namespace std;

int N, K;
int arr[100002];
int pSum[100002];
vector<int> temp;

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

    cin >> N >> K;

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

        pSum[i] = pSum[i-1] + arr[i];
    }

    for(int i=1;i<=N-(K-1);i++){
        temp.push_back(pSum[i+K-1]-pSum[i-1]);
    }

    cout << *max_element(temp.begin(), temp.end()) << "\n";


    return 0;
}

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

풀이

시간초과 때문에 누적합과 맵을 같이 사용해야 하는 문제였다. (+ long long 사용)

부분합이 K가 되는 경우를 세야 하는데 누적합을 이용하여 부분합을 구하기 때문에 누적합 차가 K가 되는 경우를 세야 한다. 하지만 누적합 배열을 돌면서 모든 경우를 세면 시간초과가 난다.

따라서 누적합의 원소들을 맵에 저장하면서 이전에 저장한 누적합 중에 차가 K가 되는 경우가 있었다면 ans에 더해준다.

처음에는 map에 누적합 원소들을 모두 저장해두고 차가 K가 되는 경우를 구하려고 했는데 이 경우에는 map 크기의 제곱 만큼 돌아야 하기 때문에 시간초과가 난다. (O(n^2))

따라서 map에 누적합 원소들을 저장하면서 동시에 이전에 저장한 차가 K가 되는 원소가 있었다면 ans에 더해주어야 한다. (O(n))

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

using namespace std;

int arr[200002];
int pSum[200002];
long long ans;

map<int, int> pSum_cnt;

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

    int N, K;
    cin >> N >> K;

    for(int i=1;i<=N;i++){
        cin >> arr[i];
        pSum[i] = pSum[i-1] + arr[i];
    }

    for(int i=1;i<=N;i++){
        if(pSum[i] == K) ans++;
        if(pSum_cnt[pSum[i]-K]) ans+=pSum_cnt[pSum[i]-K];
        pSum_cnt[pSum[i]]++;
    }

    cout << ans << "\n";

    return 0;
}

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

풀이

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

using namespace std;

int N,K,Q,M;
int check[5004];
int pSum[5004];

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

    cin >> N >> K >> Q >> M;

    for(int i=0;i<K;i++){
        int n;
        cin >> n;
        check[n] = -1;
    }

    for(int i=0;i<Q;i++){
        int n;
        cin >> n;

        if(check[n] == 0){
            for(int j=n;j<=N+2;j+=n){
                if(check[j] != -1) check[j] = 1;
            }
        }
    }

    for(int i=3;i<=N+2;i++){
        if(check[i] != 1) pSum[i] = pSum[i-1] + 1;
        else pSum[i] = pSum[i-1];
    }

    for(int i=0;i<M;i++){
        int s,e;
        cin >> s >> e;
        cout << pSum[e] - pSum[s-1] << "\n";
    }

    return 0;
}

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

풀이

표의 최대 크기가 1024 x 1024 이므로 매번 표 전체를 탐색하며 최대 100,000번 연산을 하면 1024 x 1024 x 100,000 번이므로 시간초과 날듯 -> 누적합을 이용해 (1,1)에서 (x,y)까지의 합을 미리 구해 저장해두자 -> (x1, y1)부터 (x2, y2)의 합을 구할 때는 중복 되는 부분 유의

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

using namespace std;

int N, M;
int map[1026][1026];
int pSum_map[1026][1026]; // 누적합

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

    cin >> N >> M;

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin >> map[i][j];
            pSum_map[i][j] = pSum_map[i-1][j] + pSum_map[i][j-1] - pSum_map[i-1][j-1] + map[i][j];
        }
    }

    for(int i=0;i<M;i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << pSum_map[x2][y2] - pSum_map[x1-1][y2] - pSum_map[x2][y1-1] + pSum_map[x1-1][y1-1] << "\n";
    }

    return 0;
}

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

풀이

문자열의 길이가 최대 20만이고 문제의 수도 최대 20만개이다. 따라서 단순 반복문으로 특정 문자의 개수를 매번 구하면 20만 x 20만 이므로 시간초과가 날 수 있다. 👉 _누적합_을 이용하여 문자열 각 문자 갯수의 누적합을 미리 구해놓자.

누적합을 구하기 위해 문자열을 한번 돌면서 알파벳이 나올때 이차배열(누적합 배열)을 1로 미리 저장해놓고 그 다음, 누적합을 구해 이차배열(누적합 배열)을 완성해야 한다.

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

using namespace std;

string s;
int q;
int sum_s[26][200001]; // 문자열 s의 알파벳 별 누적합

void CountAlp(){
    // 알파벳 나올 때 1로 저장
    for(int i=0;i<s.size();i++){
        sum_s[s[i]-'a'][i] = 1; 
    }

    // 누적합 만듦
    for(int i=1;i<s.size();i++){
        for(int j=0;j<26;j++){
            if(sum_s[j][i] == 1) sum_s[j][i] = sum_s[j][i-1] + 1;
            else sum_s[j][i] = sum_s[j][i-1];
        }
    }
}

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

    cin >> s;
    CountAlp();

    cin >> q;
    for(int i=0;i<q;i++){
        char ch;
        int l, r;
        cin >> ch >> l >> r;

        if(l == 0){
            cout << sum_s[ch-'a'][r] << "\n";
        }
        else{
            cout << sum_s[ch-'a'][r] - sum_s[ch-'a'][l-1] << "\n";
        }
    }

    return 0;
}

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

풀이

수의 개수 N과 합을 구해야 하는 횟수 M이 최대 100,000 이므로 단순 반복문으로 풀면 100,000 * 100,000으로 시간초과 👉 구간합 이용

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

using namespace std;

int N, M;
vector<int> arr;
vector<int> s; // 구간합

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


    cin >> N >> M;
    for(int i=0;i<N;i++){
        int num;
        cin >> num;
        arr.push_back(num);

        if(i==0)s.push_back(num);
        if(i>=1)s.push_back(num + s[i-1]);
    }

    for(int i=0;i<M;i++){
        int x,y;
        cin >> x >> y;
        cout << s[y-1] - s[x-2] << "\n";
    }

    return 0;
}