나만의 문제집 ( 쉽게, 깔끔하게, 시간복잡도가 좋게 )

Chapter 01 자료구조 ( 중요도 상 )

01-1 전화번호 목록 ( 프로그래머스 고득점 Kit, 해시 )

• 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요 (참고)

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

bool solution(vector<string> phone_book)
{
	bool answer = true;
	// 전화번호별 출현 횟수를 저장하는 해시맵
	unordered_map<string, int> num_count;
	// 각 전화번호가 출현한 횟수를 계산
	for (auto num : phone_book)
		num_count[num]++;

	// 각 전화번호의 접두사가 다른 전화번호에 포함되는지 검사
	for (int i = 0; i < phone_book.size(); i++)
	{
		// 현재 전화번호의 접두사
		string prefix = "";
		for (int j = 0; j < phone_book[i].size(); j++)
		{
			prefix += phone_book[i][j];
			// 접두사가 다른 전화번호의 전체번호라면 false 반환
			if (num_count[prefix] && prefix != phone_book[i])
				return false;
		}
	}

	return answer;
}

01-2 의상 ( 프로그래머스 고득점 Kit, 해시 )

• 코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요 (참고)

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<vector<string>> clothes)
{
    int answer = 1;
    unordered_map<string, int> mClothes;
    
    // 모든 종류를 체크한다
    for(auto cloth : clothes)
    {
        mClothes[cloth[1]] = mClothes[cloth[1]] + 1;
    }
    
    // 만약, 상의 3개, 하의 2개, 장신구 2개가 있었다고 가정하면, 총 가능한 경우의 수는 (3+1) * (2+1) * (2+1) = 36가지 이다
    // 참고로 (3+1) * (2+1) * (2+1) = 36가지 에서 +1은 선택 안함에 해당하는 경우의 수이다 ( 트리 구조로 그림을 그려보자 )
    for(auto it = mClothes.begin(); it != mClothes.end(); it++)
    {
        answer = answer * (it->second + 1);
    }
    
    // 그런데, 이 경우에는 (상의 선택 안 함, 하의 선택 안 함, 장신구 선택 안 함)이 포함되어 있으므로 그 경우를 빼주는 것이다
    // 덧 붙이자면, 문제의 제한사항에 스파이는 하루에 최소 한 개의 의상은 입습니다 라고 했다
    return answer - 1;
}

01-3 올바른 괄호 ( 프로그래머스 고득점 Kit, 스택/큐 )

• 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요 (참고)

#include <string>
#include <iostream>
#include <stack>

using namespace std;

bool solution(string s)
{
    stack<char> stk;
    
    for(int i = 0; i < s.size(); ++i)
    {
        // 첫번째 문자가 '(' 이면 그냥 넣는다
        if(s[i] == '(')
            stk.push('(');
        // 첫번째 문자가 '(' 가 아닌데 스택이 비어 있다면 false를 리턴한다
        else if(stk.empty())
            return false;
        // 첫번째 문자가 '(' 가 아닌데 스택이 비어 있지 않다면 pop 한다
        else
            stk.pop();
    }
    
    return stk.size() == 0;
}

01-4 기능개발 ( 프로그래머스 고득점 Kit, 스택/큐 )

• 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요 (참고)

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

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds)
{
    // 정답을 담을 곳
    vector<int> answer;
    // 배포될 작업을 임시로 담을 곳
    queue<int> q;
    // 작업 개수라고 보면 되는 사이즈
    int size = progresses.size();
    
    // 작업에 해당하는 인덱스를 담는다
    for (int i = 0; i < size; ++i)
    {
        q.push(i);
    }
    
    // 큐에 인덱스 값이 남아 있으면 없을때 까지 돈다
    while(!q.empty())
    {
        int cnt = 0;
        
        // 작업 진척도 퍼센테이지를 담아놓은 벡터의 값을 증가시킨다
        for(int j = 0; j < size; ++j)
        {
            progresses[j] += speeds[j];
        }
        
        // 여기서 각 배포마다 몇 개의 기능이 배포되는지를 카운트 한다
        while(!q.empty() && 100 <= progresses[q.front()])
        { 
            ++cnt;
            q.pop();
        }
        
        // 각 배포마다 몇 개의 기능이 배포되는지 정답지에 담는다
        if(cnt != 0)
            answer.push_back(cnt);  
    }
    
    return answer;
}

01-5 프로세스 ( 프로그래머스 고득점 Kit, 스택/큐 )

• 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요 (참고)

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

using namespace std;

int solution(vector<int> priorities, int location)
{
    int answer = 0, count = 0;
    //일반큐
    queue<pair<int, int>> que;
    //우선순위 큐
    priority_queue<int> prio_que;
    //우선순위 큐 정렬 반대로
    //priority_queue<int, vector<int>, greater<int>> prio_que;
 
    for (int i = 0; i < priorities.size(); ++i)
    {
        //큐에 들어온 순서와 중요도를 넣음
        que.push(make_pair(i, priorities[i]));
        //우선순위 큐에 중요도를 넣음
        prio_que.push(priorities[i]);
    }

    //큐가 빌때까지 반복
    while (!que.empty())
    {
        int index = que.front().first;
        int value = que.front().second;
        que.pop();
        //우선순위 1순위와 현재값이 같다면
        if (prio_que.top() == value)
        {
            //우선순위큐 pop
            prio_que.pop();
            //하나가 나갔으므로 count
            count++;
            //현재 나간것이 원하는것과 같다면
            if (index == location)
            {
                //현재 카운터를 리턴
                answer = count;
                break;
            }
        }
        //우선순위 1순위와 현재값이 같지않다면 큐 뒤에 넣기
        else
            que.push(make_pair(index, value));
    }

    return answer;
}

01-6 다리를 지나는 트럭 ( 프로그래머스 고득점 Kit, 스택/큐 )

• 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요 (참고)

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights)
{
    queue<int> que;
    int time = 0;
    int sum = 0;
    int truckIdx = 0;
    
    while(true)
    {
        // 1초인 시점부터 트럭이 진입하기 시작하자나 그러니까 시작하자 마자 ++ 시켜준거다
         time++;
        // 트럭의 무게가 다리의 무게보다 작으면, 트럭을 삽입
        if(sum + truck_weights[truckIdx] <= weight)
        {
            // 마지막 트럭이 삽입되면 종료
            if(truckIdx == truck_weights.size()-1)
            {
                // 마지막 트럭 도착시간 추가
                time += bridge_length;
                break;
            }
            
            que.push(truck_weights[truckIdx]);
            sum += truck_weights[truckIdx];
            truckIdx++;
        }
        // 트럭의 무게가 다리의 무게보다 크면, 0을 삽입해서 트럭을 도착점으로 민다
        else
        {
            que.push(0);
        }

        // 큐 사이즈 = 다리길이 -> 트럭 도착
        // ( 이 상황에서 트럭이 도착했다는 처리를 해줘야 다음 time++ 에서 새로운 트럭이 들어올 수 있다 )
        if(que.size() == bridge_length)
        {
            sum -= que.front();
            que.pop();
        }
    }
    return time;
}

01-7 주식가격 ( 프로그래머스 고득점 Kit, 스택/큐 )

• 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요 (참고)

#include <string>
#include <vector>
#include <stack>
 
using namespace std;
 
vector<int> solution(vector<int> prices)
{
    // 7 8 9 7 8 9 7 8 9 이 숫자 세트가 예시로서 적당하다
    vector<int> answer(prices.size());
    stack<int> st;

    int size = prices.size();
    for (int i = 0; i < size; i++)
    {
        // 스택이 비어있지않고
        // 스택의 마지막 인덱스가 가리키는 가격이 현재 가격보다 크다면 ( 가격이 떨어 졌다면 )
        while (!st.empty() && prices[i] < prices[st.top()])
        {
            // 지금까지 쌓인 모든 스택 인덱스를 검사하여 얼마만에 가격이 떨어졌는지 죄다 기록한다
            answer[st.top()] = i - st.top();
            // 가격이 떨어진 인덱스는 제거하자
            st.pop();
        }
        // 현재 인덱스를 스택에 넣기
        st.push(i);
    }

    // 스택이 빌때까지 반복
    while (!st.empty())
    {
        // 가격을 버텨낸 인덱스들이 얼마나 버텼는지 기록해준다
        // 유의사항1. 위에서 특정위치에 이미값을 넣었으므로 pushback이나 insert로하면 안된다.
        // 유의사항2. 뒤에서부터 넣어야하므로 size-1 에서 버텨낸 인덱스값을 빼준다.
        answer[st.top()] = (size - 1) - st.top();
        st.pop();
    }

    return answer;
}

01-8 더 맵게 ( 프로그래머스 고득점 Kit, 힙 )

• Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요 (참고)

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

using namespace std;

int solution(vector<int> scoville, int K)
{
	int answer = 0;
	priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());
	while (pq.size() > 1 && pq.top() < K)
	{
		// 스코빌 지수가 가장 낮은 음식과 두번째로 낮은 음식의 스코빌 지수를 섞는다
		int first = pq.top();
		pq.pop();
		int second = pq.top();
		pq.pop();
		pq.push(first + (second * 2));

		// 섞은 횟수를 ++ 한다
		answer++;
	}

	// 스코빌 지수를 K 이상으로 만들 수 없을 경우 -1로 answer를 갱신한다
	if (pq.top() < K) answer = -1;

	return answer;
}

01-9 입국심사 ( 프로그래머스 고득점 Kit, 이분탐색 )

• 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요 (참고)

#include<bits/stdc++.h> // 필요한 헤더 파일들을 한번에 include하기 위한 코드

using namespace std;

long long solution(int n, vector<int> times)
{
	long long answer = 0; // 최종적으로 반환될 정답

	// times 배열을 오름차순으로 정렬하여 가장 큰 값이 times.back()에 위치하도록 함
	sort(times.begin(), times.end());

	long long left = 1; // 이진 탐색을 위한 왼쪽 끝 값
	long long right = (long long)times.back() * n; // 이진 탐색을 위한 오른쪽 끝 값

	while (left <= right) // 이진 탐색
	{
		long long mid = (left + right) / 2; // 중앙 값

		long long cnt = 0; // mid 시간 동안 심사 가능한 인원 수
		for (long long i = 0; i < times.size(); i++) // 모든 심사관이 mid 시간 동안 처리할 수 있는 인원 수를 합산
		{
			cnt = cnt + (mid / times[i]);
		}

		if (cnt < n) // 처리 가능한 인원 수가 n보다 작은 경우
		{
			left = mid + 1; // 이진 탐색의 왼쪽 끝 값을 mid+1로 조정하여 다시 탐색
		}
		else // 처리 가능한 인원 수가 n 이상인 경우
		{
			answer = mid; // 현재 시간을 정답에 저장
			right = mid - 1; // 이진 탐색의 오른쪽 끝 값을 mid-1로 조정하여 다시 탐색
		}
	}

	return answer; // 정답 반환
}

Chapter 02 시뮬레이션 ( 중요도 상 )

02-1 뱀 ( 3190 )

• 첫째 줄에 게임이 몇 초에 끝나는지 출력한다 (참고)

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

int board_size; // 게임판의 크기
int num_of_apple; // 먹이의 개수
int num_of_order; // 뱀의 이동 방향 변경 횟수

deque<pair<int, int>> snake_body; // 뱀의 몸통 좌표
vector<int> order_time; // 뱀의 이동 방향 변경 시간
vector<char> order_direction; // 뱀의 이동 방향 변경 방향

int game_board[100][100]; // 게임판 상태
int dx[] = { 1, 0, -1, 0 }; // x좌표 이동 방향
int dy[] = { 0, 1, 0, -1 }; // y좌표 이동 방향

// 뱀 게임 실행 함수
int run_game(int start_x, int start_y)
{
	int direction = 0; // 초기 방향은 오른쪽
	int cnt = 0; // 게임 진행 시간
	int x, y; // 뱀 머리 좌표
	int order_idx = 0; // 뱀의 이동 방향 변경 명령 인덱스

	snake_body.push_front(make_pair(start_x, start_y)); // 뱀 머리 좌표 큐에 추가
	game_board[start_y][start_x] = 2; // 뱀이 있는 위치 표시

	while (1)
	{
		x = snake_body.front().first;
		y = snake_body.front().second;

		cnt++;

		int next_x = x + dx[direction];
		int next_y = y + dy[direction];

		// 게임 종료 조건
		if (next_x < 0 || next_y < 0 || board_size <= next_x || board_size <= next_y || game_board[next_y][next_x] == 2)
			return cnt;

		snake_body.push_front(make_pair(next_x, next_y)); // 뱀 머리를 다음 위치로 이동

		// 먹이를 먹지 않은 경우
		if (game_board[next_y][next_x] != 1)
		{
			int tail_x = snake_body.back().first;
			int tail_y = snake_body.back().second;
			game_board[tail_y][tail_x] = 0; // 꼬리 제거
			snake_body.pop_back(); // 뱀 꼬리 제거
		}

		// 먹이를 먹지 않는 경우를 먼저 처리 해주지 않으면 아래의 코드에서 표시해준게 없어질 수 있다
		game_board[next_y][next_x] = 2; // 뱀이 있는 위치 표시

		// 뱀의 이동 방향 변경
		if (cnt == order_time[order_idx])
		{
			if (order_direction[order_idx] == 'L')
			{ // 왼쪽으로 회전
				direction += 3;
				direction %= 4;
			}
			else
			{ // 오른쪽으로 회전
				direction += 1;
				direction %= 4;
			}

			if (order_idx < order_time.size() - 1) order_idx++;
		}
	}
}

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

	cin >> board_size;

	// 사과
	cin >> num_of_apple;
	for (int i = 0; i < num_of_apple; i++)
	{
		int applex, appley;
		cin >> applex >> appley;
		game_board[applex - 1][appley - 1] = 1;
	}

	// 명령
	cin >> num_of_order;
	for (int i = 0; i < num_of_order; i++)
	{
		int t;
		char d;
		cin >> t >> d;
		order_time.push_back(t);
		order_direction.push_back(d);
	}

	cout << run_game(0, 0);
	return 0;
}

02-2 주사위 굴리기 ( 14499 )

• 이동할 때마다 주사위의 윗 면에 쓰여 있는 수를 출력한다 만약 바깥으로 이동시키려고 하는 경우에는 해당 명령을 무시해야 하며, 출력도 하면 안 된다 (참고)

// https://excited-hyun.tistory.com/215 참고

#include<bits/stdc++.h>
using namespace std;

int mymap[20][20];
int X[5] = { 0, 1, -1, 0, 0 };
int Y[5] = { 0, 0, 0, -1, 1 };
vector<int> dice(6, 0);

int main()
{
	int n, m, x, y, k;

	scanf("%d %d %d %d %d", &n, &m, &y, &x, &k);
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
			scanf("%d", &mymap[i][j]);
	}

	int move;
	for (int i = 0; i < k; ++i)
	{
		scanf("%d", &move);
		int newX = x + X[move];
		int newY = y + Y[move];

		if (newX < 0 || newY < 0 || m <= newX || n <= newY)
			continue;

		if (move == 1)
			dice = { dice[3], dice[1], dice[0], dice[5], dice[4], dice[2] };
		else if (move == 2)
			dice = { dice[2], dice[1], dice[5], dice[0], dice[4], dice[3] };
		else if (move == 3)
			dice = { dice[4], dice[0], dice[2], dice[3], dice[5], dice[1] };
		else if (move == 4)
			dice = { dice[1], dice[5], dice[2], dice[3], dice[0], dice[4] };

		if (mymap[newY][newX] == 0)
			mymap[newY][newX] = dice[5];
		else
		{
			dice[5] = mymap[newY][newX];
			mymap[newY][newX] = 0;
		}

		cout << dice[0] << endl;

		x = newX;
		y = newY;
	}

	return 0;
}

02-3 로봇 청소기 ( 14503 )

• 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오 (참고)

// https://blog.naver.com/PostView.naver?blogId=fbfbf1&logNo=222472445249&categoryNo=34&parentCategoryNo=37&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView 참고

#include<bits/stdc++.h>
using namespace std;

int board[52][52];
bool check[52][52];

int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
int sum = 0;

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

	int N, M, r, c, d;
	cin >> N >> M >> r >> c >> d;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> board[i][j];
		}
	}

	while (true)
	{
		if (check[r][c] == false)
		{
			check[r][c] = true;
			sum++;
		}

		bool move = false;
		for (int i = 0; i < 4; ++i)
		{
			d = (d + 3) % 4;
			int nx = c + dx[d];
			int ny = r + dy[d];

			if (nx < 0 || ny < 0 || M <= nx || N <= ny) continue;

			if (board[ny][nx] == 0 && check[ny][nx] == false)
			{
				c = nx;
				r = ny;
				move = true;
				break;
			}
		}

		if (!move)
		{
			int back = (d + 2) % 4;
			int nx = c + dx[back];
			int ny = r + dy[back];

			if (nx < 0 || ny < 0 || M <= nx || N <= ny) break;
			if (board[ny][nx] == 1) break;

			c = nx;
			r = ny;
		}
	}

	cout << sum << "\n";
}

02-4 톱니바퀴 (2) ( 15662 )

• 톱니바퀴 T개의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오 (참고)

// https://intaehwang.tistory.com/108 참고

#include<bits/stdc++.h>
using namespace std;

int gear[1001][8];
int check[1001];
 
int main()
{
    int t;
    cin >> t;
 
    for (int i = 1; i <= t; i++)
    {
        for (int j = 0; j < 8; j++)
            scanf("%1d", &gear[i][j]);
    }
 
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        memset(check, 0, sizeof(check));
        int x, y;
        cin >> x >> y;
        check[x] = y;
        
        for (int j = x; j < t; j++)
        {
            if (gear[j][2] != gear[j+1][6]) check[j+1] = -check[j];
            else break;
        }
        for (int j = x; 1 < j; j--)
        {
            if (gear[j-1][2] != gear[j][6]) check[j-1] = -check[j];
            else break;
        }
        for (int j = 1; j <= t; j++)
        {
            if (check[j] == 0) continue;
            else if (check[j] == 1)
            {
                int tmp = gear[j][7];
                for(int cur = 7; 0 < cur; --cur) gear[j][cur] = gear[j][cur-1];
                gear[j][0] = tmp;
            }
            else if (check[j] == -1)
            {
                int tmp = gear[j][0];
                for(int cur = 0; cur < 7; ++cur) gear[j][cur] = gear[j][cur+1];
                gear[j][7] = tmp;
            }
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= t; i++)
        if (gear[i][0] == 1) ans += 1;
    
    cout << ans << endl;
}

02-5 드래곤 커브 ( 15685 )

• 크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오 (참고)

// https://velog.io/@sj-lee33/%EB%B0%B1%EC%A4%80-15685-%EB%93%9C%EB%9E%98%EA%B3%A4-%EC%BB%A4%EB%B8%8C-c-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%92%80%EC%9D%B4 참고

#include<bits/stdc++.h>
using namespace std;
#define MAX 101

int N;
int x, y, d, g, cnt;
int mymap[MAX][MAX];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };
vector<int> direction;

void Make_Dragon_Curve()
{
	int size = direction.size();
	for (int i = size - 1; 0 <= i; i--)
	{
		int temp = (direction[i] + 1) % 4;
		x += dx[temp];
		y += dy[temp];
		mymap[y][x] = 1;
		direction.push_back(temp);
	}
}

void Count_Square()
{
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			if (mymap[i][j] == 1 && mymap[i][j + 1] == 1 && mymap[i + 1][j + 1] == 1 && mymap[i + 1][j] == 1)
				cnt++;
		}
	}
}

void Solution()
{
	cin >> N;

	while (N--)
	{
		direction.clear();
		cin >> x >> y >> d >> g;

		// initialize
		mymap[y][x] = 1;

		// generation 0
		x += dx[d];
		y += dy[d];
		mymap[y][x] = 1;
		direction.push_back(d);

		// next 'g' generations
		while (g--)
		{
			Make_Dragon_Curve();
		}
	}

	Count_Square();
	cout << cnt << endl;
}

int main()
{
	Solution();
}

02-6 인구 이동 ( 16234 )

• 각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오 (참고)

#include<bits/stdc++.h>
using namespace std;

int arr[55][55];
bool visited[55][55];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int n, l, r, uni, sum;
queue<pair<int, int>> que;

// y, x 좌표를 시작으로 DFS 탐색을 하면서 인구 이동이 가능한 국가들을 모두 찾아줌
void dfs(int y, int x)
{
	// 시작 좌표를 큐에 추가하고 방문 체크를 함
	que.push({ y, x });
	visited[y][x] = true;
	sum = sum + arr[y][x];
	uni++;

	// 현재 위치에서 4방향으로 이동하면서 인구 이동이 가능한 국가들을 찾음
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i], nx = x + dx[i];
		if (nx < 0 || ny < 0 || n <= nx || n <= ny || visited[ny][nx]) continue;

		if (l <= abs(arr[y][x] - arr[ny][nx]) && abs(arr[y][x] - arr[ny][nx]) <= r)
			dfs(ny, nx);
	}
}

int main()
{
	scanf("%d %d %d", &n, &l, &r);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) scanf("%d", &arr[i][j]);

	int ret = 0; bool move = false;
	do
	{
		move = false;
		memset(visited, 0, sizeof(visited));

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				// 아직 방문하지 않은 국가를 시작으로 DFS 탐색을 시작함
				uni = 0;
				if (!visited[i][j])
				{
					sum = 0;
					dfs(i, j);

					// 큐에 저장된 모든 국가들의 인구수를 현재 연합의 인구수 평균값으로 업데이트함
					while (!que.empty())
					{
						auto pos = que.front();
						que.pop();
						arr[pos.first][pos.second] = sum / uni;
					}

					// 인구 이동이 발생한 경우 move를 true로 세팅
					if (sum != arr[i][j]) move = true;
				}
			}
		}
		// 인구 이동이 발생한 경우 날짜를 증가시킨다
		if (move) ret++;

	} while (move);

	printf("%d", ret);
}

// 이 코드는 도대체 어떻게 돌아가는지 연구가 필요하다
// for (int i = 0; i < 4; i++) 여기 부분에서
// sum = arr[ny][nx] + dfs(ny, nx); 이 코드가 말이 안된다
#include<bits/stdc++.h>
using namespace std;

int arr[55][55];
bool visited[55][55];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int n, l, r, uni, sum;
queue<pair<int, int>> que;

// y, x 좌표를 시작으로 DFS 탐색을 하면서 인구 이동이 가능한 국가들을 모두 찾아줌
int dfs(int y, int x)
{
	// 시작 좌표를 스택에 추가하고 방문 체크를 함
	que.push({ y, x });
	visited[y][x] = true;
	uni++;

	// 현재 위치에서 4방향으로 이동하면서 인구 이동이 가능한 국가들을 찾음
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i], nx = x + dx[i];
		if (nx < 0 || ny < 0 || n <= nx || n <= ny || visited[ny][nx]) continue;
		if (abs(arr[y][x] - arr[ny][nx]) <= r && l <= abs(arr[y][x] - arr[ny][nx])) sum = arr[ny][nx] + dfs(ny, nx);
	}

	return sum;
}

int main()
{
	scanf("%d %d %d", &n, &l, &r);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) scanf("%d", &arr[i][j]);

	int ret = 0; bool move = false;
	do
	{
		move = false;
		memset(visited, 0, sizeof(visited));

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				// 아직 방문하지 않은 국가를 시작으로 DFS 탐색을 시작함
				uni = 0;
				if (!visited[i][j])
				{
					sum = 0;
					sum = arr[i][j] + dfs(i, j);

					// 큐에 저장된 모든 국가들의 인구수를 현재 연합의 인구수 평균값으로 업데이트함
					while (!que.empty())
					{
						auto pos = que.front();
						que.pop();
						arr[pos.first][pos.second] = sum / uni;
					}

					// 인구 이동이 발생한 경우 카운트를 증가시킴
					if (sum != arr[i][j]) move = true;
				}
			}
		}
		// 인구 이동이 발생한 경우 날짜를 증가시킨다
		if (move) ret++;

	} while (move);

	printf("%d", ret);
}

02-7 미세먼지 안녕! ( 17144 )

• 첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다 (참고)

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

int R, C, T;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int board[51][51];
vector<int> cleaner; // 공기청정기 위치

// 미세먼지 확산 함수
void CalDiffusion()
{
	vector<vector<int>> temp(51, vector<int>(51, 0)); // 확산될 미세먼지 임시 보관

	// 미세먼지 있는 칸 별로 확산되는 미세먼지 양 계산
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			if (0 < board[i][j]) // 미세먼지 있는 칸
			{
				int dust = board[i][j] / 5; // 확산되는 미세먼지 양 계산
				if (dust == 0) continue; // 예시 그림을 보면 나누기 5를 했을때 1 이상 나오지 않으면 확산되지 않음

				int cnt = 0; // 확산된 칸 갯수
				for (int dir = 0; dir < 4; dir++) // 사방 탐색
				{
					int ny = i + dy[dir];
					int nx = j + dx[dir];

					if (nx < 0 || ny < 0 || C <= nx || R <= ny) continue; // 범위 체크
					if (board[ny][nx] == -1) continue; // 공기청정기 체크

					temp[ny][nx] = temp[ny][nx] + dust; // 미세먼지 확산
					cnt++;
				}

				// 확산 이후 미세먼지 감소
				board[i][j] = board[i][j] - (dust * cnt);
			}
		}
	}

	// 확산된 미세먼지와 칸 별로 줄어든 미세먼지 합산
	// 확산된 먼지가 다른 칸의 먼지양을 나누는 계산을
	// 할때 영향을 끼치면 안되서 이렇게 하는것으로 추정
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			board[i][j] = board[i][j] + temp[i][j];
		}
	}
}

void CleanDust()
{
	// upward
	int cr = cleaner[0];
	for (int i = cr - 1; 0 < i; i--) board[i][0] = board[i - 1][0];
	for (int j = 0; j < C - 1; j++) board[0][j] = board[0][j + 1];
	for (int i = 0; i < cr; i++) board[i][C - 1] = board[i + 1][C - 1];
	for (int j = C - 1; 1 < j; j--) board[cr][j] = board[cr][j - 1];
	board[cr][1] = 0;

	// downward
	cr = cleaner[1];
	for (int i = cr + 1; i < R - 1; i++) board[i][0] = board[i + 1][0];
	for (int j = 0; j < C - 1; j++) board[R - 1][j] = board[R - 1][j + 1];
	for (int i = R - 1; cr < i; i--) board[i][C - 1] = board[i - 1][C - 1];
	for (int j = C - 1; 1 < j; j--) board[cr][j] = board[cr][j - 1];
	board[cr][1] = 0;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> R >> C >> T;
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == -1) cleaner.push_back(i);
		}
	}

	while (T--)
	{
		CalDiffusion();
		CleanDust();
	}

	int answer = 0;
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			if (board[i][j] > 0) answer += board[i][j];
		}
	}
	cout << answer;
}

02-8 이차원 배열과 연산 ( 17140 )

• A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다 (참고)

#include<bits/stdc++.h>
using namespace std;

int grid[101][101]; // 101x101 크기의 2차원 배열 선언
int rows, cols, target; // 행, 열, 타겟값
int rowCount = 3; // 현재 행의 개수
int colCount = 3; // 현재 열의 개수

void sortRows() // 각 행에 대해 정렬하는 함수
{
	int cnt = 0;
	for (int i = 0; i < rowCount; i++) // 모든 행에 대해 반복
	{
		int freq[101] = { 0 }; // 각 숫자의 등장 횟수를 저장하는 배열
		for (int j = 0; j < colCount; j++) // 현재 행의 모든 열에 대해 반복
		{
			freq[grid[i][j]]++; // 해당 숫자의 등장 횟수 증가
		}

		vector<pair<int, int>> freqPairs; // 등장 횟수와 해당 숫자를 저장하는 벡터
		for (int j = 1; j < 101; j++) // 1부터 100까지 모든 숫자에 대해 반복
		{
			if (0 < freq[j]) // 해당 숫자가 등장한 경우
			{
				freqPairs.push_back({ freq[j], j }); // 등장 횟수와 해당 숫자를 벡터에 추가
			}
		}

		sort(freqPairs.begin(), freqPairs.end()); // 등장 횟수를 기준으로 오름차순 정렬

		int idx = 0; // 현재 열 인덱스를 저장하는 변수
		int size = freqPairs.size(); // 등장한 숫자의 개수
		for (int j = 0; j < size; j++) // 등장한 숫자에 대해 반복
		{
			grid[i][idx] = freqPairs[j].second; // 해당 숫자를 현재 열에 저장
			grid[i][idx + 1] = freqPairs[j].first; // 해당 숫자의 등장 횟수를 다음 열에 저장
			idx += 2; // 열 인덱스를 2 증가
		}
		cnt = max(cnt, size * 2); // 열 개수를 갱신

		for (int j = idx; j < 101; j++) grid[i][j] = 0; // 남은 열을 0으로 초기화
	}

	colCount = cnt; // 열 개수를 업데이트
}

void sortCols()
{
	int cnt = 0;
	for (int i = 0; i < colCount; i++)
	{
		// freq: 열에서 각 숫자의 등장 횟수를 저장하는 배열
		int freq[101] = { 0 };
		for (int j = 0; j < rowCount; j++)
		{
			freq[grid[j][i]]++;
		}

		// freqPairs: 등장 횟수가 1 이상인 숫자와 그 횟수를 저장하는 벡터
		vector<pair<int, int>> freqPairs;
		for (int j = 1; j < 101; j++)
		{
			if (0 < freq[j])
			{
				freqPairs.push_back({ freq[j], j });
			}
		}

		// 등장 횟수가 적은 숫자부터 정렬
		sort(freqPairs.begin(), freqPairs.end());

		// idx: 현재 열의 어디까지 값을 넣었는지를 저장하는 인덱스
		int idx = 0;
		int size = freqPairs.size();
		for (int j = 0; j < size; j++)
		{
			grid[idx][i] = freqPairs[j].second;  // 숫자를 넣음
			grid[idx + 1][i] = freqPairs[j].first;  // 등장 횟수를 넣음
			idx += 2;
		}
		cnt = max(cnt, size * 2);  // 현재 가장 긴 열의 길이 업데이트

		// 나머지 빈 공간에는 0을 채움
		for (int j = idx; j < 101; j++) grid[j][i] = 0;
	}

	rowCount = cnt;  // 새로운 행의 개수를 업데이트
}

int main()
{
	int time = 0;

	// 입력 받기
	cin >> rows >> cols >> target;
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> grid[i][j];
		}
	}

	// 목표값이 나올 때까지 정렬을 반복
	while (time <= 100)
	{
		if (grid[rows - 1][cols - 1] == target) break; // 목표값이 나오면 종료
		if (colCount <= rowCount) sortRows(); // 행 기준으로 정렬
		else sortCols(); // 열 기준으로 정렬
		time++;
	}

	// 목표값을 찾지 못한 경우 -1 출력, 찾은 경우에는 시간 출력
	if (100 < time) cout << "-1";
	else cout << time;
}

02-9 컨베이어 벨트 위의 로봇 ( 20055 )

• 몇 번째 단계가 진행 중일때 종료되었는지 출력한다 (참고)

// 이 문제에서 사용된 로직은 DP스러운 문제에서 필요한 경우가 있다

#include<bits/stdc++.h>
using namespace std;

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

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

	vector<bool> occupied(2 * N, false);
	vector<int> A(2 * N);
	for (auto& item : A)
		cin >> item;

	int counter = 0;
	while (true)
	{
		++counter;

		// 1.
		rotate(occupied.rbegin(), occupied.rbegin() + 1, occupied.rend());
		rotate(A.rbegin(), A.rbegin() + 1, A.rend());
		occupied[N - 1] = false;

		// 2.
		for (int i = N - 1; 0 < i; --i)
		{
			if (occupied[i - 1] && !occupied[i] && A[i])
			{
				swap(occupied[i - 1], occupied[i]);
				--A[i];
			}
		}
		occupied[N - 1] = false;

		// 3.
		if (A[0])
		{
			occupied[0] = true;
			--A[0];
		}

		// 4.
		if (K <= count_if(A.begin(), A.end(), [](int item) { return item == 0; }))
		{
			break;
		}
	}

	cout << counter;

	return 0;
}

02-10 마법사 상어와 파이어볼 ( 20056 )

• 마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다 (참고)

// https://www.youtube.com/watch?v=g2B-rKwaVUQ 14 : 57 참고

#include<bits/stdc++.h>
using namespace std;

int N, M, K;

// 볼을 나타내는 구조체 선언
struct Ball
{
	int y, x;   // 좌표
	int m, s, d; // 질량, 속도, 방향
};

// 각 좌표에 위치한 Ball을 저장할 벡터 배열 선언
vector<Ball> balls;
vector<Ball> mat[53][53];

// 각 방향을 나타내는 배열 선언 ( 12시 방향부터 시계 방향으로  )
int dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

void solution()
{
	while (K--)
	{
		// Ball 움직이기  
		for (int i = 0; i < balls.size(); i++)
		{
			int y = balls[i].y;
			int x = balls[i].x;
			int m = balls[i].m;
			int s = balls[i].s;
			int d = balls[i].d;

			// 현재 속력으로 이동한 거리 계산
			int move = s % N;
			int ny = y + dy[d] * move; // 새로운 y 좌표
			int nx = x + dx[d] * move; // 새로운 x 좌표

			// 경계를 넘어갈 경우 위치 수정
			if (ny < 0) ny = ny + N;
			if (nx < 0) nx = nx + N;
			if (N <= ny) ny = ny - N;
			if (N <= nx) nx = nx - N;

			// 새로운 위치에 Ball 추가
			mat[ny][nx].push_back({ ny, nx, m, s, d });
		}


		// 움직임이 완료된 Ball들 합치기  
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (2 <= mat[i][j].size())
				{
					int sum_m = 0, sum_s = 0;
					int odd = 0, even = 0;
					int size = mat[i][j].size();

					// Ball의 속력, 방향, 질량의 합 구하기
					for (int t = 0; t < size; t++)
					{
						sum_m = sum_m + mat[i][j][t].m;
						sum_s = sum_s + mat[i][j][t].s;

						if (mat[i][j][t].d % 2 == 0) even++;
						else odd++;
					}

					mat[i][j].clear(); // 합쳐진 Ball 제거

					// 소멸될 예정인 파이어볼은 미리 거르자
					if (sum_m / 5 == 0) continue;

					// 방향 결정
					if (odd == 0 || even == 0)
					{
						for (int nd = 0; nd < 7; nd = nd + 2)
						{
							mat[i][j].push_back({ i, j, sum_m / 5, sum_s / size, nd });
						}
					}
					else
					{
						for (int nd = 1; nd < 8; nd = nd + 2)
						{
							mat[i][j].push_back({ i, j, sum_m / 5, sum_s / size, nd });
						}
					}
				}
			}
		}

		// 합치기가 완료된 Ball을 저장하기  
		balls.clear();
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				for (int t = 0; t < mat[i][j].size(); t++)
				{
					balls.push_back(mat[i][j][t]);
				}
				mat[i][j].clear();
			}
		}
	}

	// 남은 질량의 합 구하기  
	int ans = 0;
	for (int i = 0; i < balls.size(); i++)
		ans = ans + balls[i].m;

	cout << ans << endl;
}

int main(void)
{
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++)
	{
		int y, x, m, s, d;
		cin >> y >> x >> m >> s >> d;
		balls.push_back({ y, x, m, s, d });
	}

	solution();
}

// 킵 해두자
// https://kibbomi.tistory.com/193

02-11 상어 초등학교 ( 21608 )

• 첫째 줄에 학생의 만족도의 총 합을 출력한다 (참고)

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

int main()
{
	//위,아래,왼,우 방향 배열
	int x_direction[] = { 1, -1, 0, 0 };
	int y_direction[] = { 0, 0, 1, -1 };
	int answer = 0;
	int n;

	// n 입력 받기
	cin >> n;

	// n x n 크기의 2차원 벡터 seats를 만들고 0으로 초기화
	vector<vector<int>> seats(n, vector<int>(n, 0));

	// n x n + 1 크기의 2차원 벡터 like와 1차원 벡터 students를 만들기
	vector<vector<int>> like(n * n + 1, vector<int>(4, 0));
	vector<int> students(n * n + 1);

	// 학생들의 좋아하는 학생 번호 입력받기
	for (int i = 0; i < n * n; i++)
	{
		cin >> students[i];
		for (int j = 0; j < 4; j++)
			cin >> like[students[i]][j];
	}

	// 배치 시작
	for (int s = 0; s < n * n; s++)
	{
		int student = students[s];
		int most_like = -1, most_empty = -1, selected_y = -1, selected_x = -1;

		// 각 자리마다 좋아하는 학생과 인접한 빈 자리 수 계산하기
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
			{
				// 이미 학생이 있는 자리는 건너뛰기
				if (seats[i][j] != 0) continue;

				int cur_like = 0, cur_empty = 0;
				for (int dir = 0; dir < 4; dir++)
				{
					int ny = i + y_direction[dir], nx = j + x_direction[dir];
					// 범위를 벗어나는 경우 건너뛰기
					if (nx < 0 || ny < 0 || n <= nx || n <= ny) continue;

					if (seats[ny][nx] == 0)
					{
						cur_empty++;
						continue;
					}

					// 좋아하는 학생인 경우 인접한 학생 수 1 증가
					for (int k = 0; k < 4; k++)
					{
						if (seats[ny][nx] == like[student][k])
						{
							cur_like++;
							break;
						}
					}
				}

				// 조건에 맞는 자리 선택하기
				if (most_like < cur_like)
				{
					most_like = cur_like, most_empty = cur_empty;
					selected_y = i, selected_x = j;
				}
				else if (most_like == cur_like)
				{
					if (most_empty < cur_empty)
					{
						most_empty = cur_empty;
						selected_y = i, selected_x = j;
					}
				}
			}

		// 선택된 자리에 학생 배치하기
		seats[selected_y][selected_x] = student;
	}

	// 만족도 계산
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			int student = seats[i][j];
			int satisfaction = 0;

			// 상하좌우 인접한 자리에 좋아하는 학생이 있으면 만족도 증가
			for (int dir = 0; dir < 4; dir++)
			{
				int ny = i + y_direction[dir], nx = j + x_direction[dir];
				if (nx < 0 || ny < 0 || n <= nx || n <= ny) continue;

				for (int k = 0; k < 4; k++)
				{
					if (seats[ny][nx] == like[student][k])
					{
						satisfaction++;
						break;
					}
				}
			}

			// 만족도가 1 이상이면 answer에 추가
			if (satisfaction)
			{
				int ans = 1;
				for (int score = 0; score < satisfaction - 1; score++) ans = ans * 10;
				answer = answer + ans;
			}
		}

	cout << answer << endl;
	return 0;
}

// https://gusdnr69.tistory.com/296 킵 해두자

02-12 마법사 상어와 비바라기 ( 21610 )

• 첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다 (참고)

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

using namespace std;

int main()
{
	int gridSize, numMoves;
	int answer = 0;
	queue<pair<int, int>> cloudQueue;
	vector<vector<int>> grid(51, vector<int>(51, 0));
	int directionY[9] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
	int directionX[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };

	// 그리드 사이즈와 이동 횟수 입력받기
	cin >> gridSize >> numMoves;

	// 그리드 초기화
	for (int i = 1; i <= gridSize; i++)
		for (int j = 1; j <= gridSize; j++)
			cin >> grid[i][j];

	// 초기 구름 위치 설정
	cloudQueue.push(make_pair(gridSize, 1));
	cloudQueue.push(make_pair(gridSize, 2));
	cloudQueue.push(make_pair(gridSize - 1, 1));
	cloudQueue.push(make_pair(gridSize - 1, 2));

	// 이동 횟수만큼 반복
	while (numMoves--)
	{
		int moveDirection, moveDistance, queueSize;
		vector<vector<bool>> visited(51, vector<bool>(51, false));
		vector<pair<int, int>> cloudPositions;

		// 이동 방향과 거리 입력받기
		cin >> moveDirection >> moveDistance;

		// 현재 구름 위치에서 이동 방향과 거리에 따라 이동하기
		queueSize = cloudQueue.size();
		for (int i = 0; i < queueSize; i++)
		{
			int y = cloudQueue.front().first;
			int x = cloudQueue.front().second;
			cloudQueue.pop();

			for (int j = 0; j < moveDistance; j++)
			{
				x += directionX[moveDirection];
				y += directionY[moveDirection];

				// 그리드를 벗어나는 경우 위치 조정
				if (x == 0)
					x = gridSize;
				else if (gridSize < x)
					x = 1;

				if (y == 0)
					y = gridSize;
				else if (gridSize < y)
					y = 1;
			}

			grid[y][x]++;
			cloudPositions.push_back(make_pair(y, x));
			visited[y][x] = true;
		}

		// 현재 구름 위치에서 대각선 방향으로 인접한 칸의 물의 양 증가시키기
		for (int i = 0; i < cloudPositions.size(); i++)
		{
			int y = cloudPositions[i].first;
			int x = cloudPositions[i].second;

			for (int j = 2; j <= 8; j += 2)
			{
				int nx = x + directionX[j];
				int ny = y + directionY[j];

				if (1 <= nx && 1 <= ny && nx <= gridSize && ny <= gridSize && 1 <= grid[ny][nx])
					grid[y][x]++;
			}
		}

		// 구름을 이동시킨 후 물의 양이 2 이상이 되는 칸에 새로운 구름 생성
		for (int i = 1; i <= gridSize; i++)
			for (int j = 1; j <= gridSize; j++)
				if (2 <= grid[i][j] && !visited[i][j])
				{
					cloudQueue.push(make_pair(i, j));
					grid[i][j] -= 2;
				}
	}

	// 최종적으로 남아있는 물의 양 계산
	for (int i = 1; i <= gridSize; i++)
		for (int j = 1; j <= gridSize; j++)
			if (0 < grid[i][j])
				answer += grid[i][j];

	// 결과 출력
	cout << answer;

	return 0;
}

// https://eunchanee.tistory.com/398 킵 해두자
// https://imnotabear.tistory.com/562 // 킵 해두자

Chapter 03 그래프 ( 중요도 중 )

03-1 전력망을 둘로 나누기 ( 프로그래머스 고득점 Kit, 완전탐색 )

• 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요 (참고)

// 기본 그래프 문제 5개

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAX = 101;

// 각 노드는 중복이 존재할 수 없다
set<int> graph[MAX];

int getLength(int nodecount, int node)
{
    int length = 0;
    queue<int> que;
    
    // 현재 노드 세팅
    que.push(node);
    
    // 메모이제이션 기법으로 중복 계산 방지
    vector<bool> visited(nodecount);
    visited[node] = true;
    
    while (!que.empty())
    {
        // 다음 노드 세팅
        int cur = que.front();
        que.pop();
        length++;
        
        // 현재 노드와 연결된 노드를 모두 큐에 등록한다
        for (auto next : graph[cur])
        {
            if (visited[next])
                continue;
            
            que.push(next);
            visited[next] = true;
        }
    }

    return length;
}

int solution(int n, vector<vector<int>> wires)
{
    // 엣지들을 서로 연결
    for (auto wire : wires)
    {
        graph[wire[0]].insert(wire[1]);
        graph[wire[1]].insert(wire[0]);
    }
    
    int answer = INF;
    
    // 모든 간선을 한번씩 끊어가면서, 노드 개수의 차이가 최소가 되는 값을 구하자
    for (auto wire : wires)
    {
        graph[wire[0]].erase(wire[1]);
        graph[wire[1]].erase(wire[0]);
        
        answer = min(answer, abs(getLength(n, wire[0]) - getLength(n, wire[1])));
        
        graph[wire[0]].insert(wire[1]);
        graph[wire[1]].insert(wire[0]);
    }
    
    return answer;
}

03-2 가장 먼 노드 ( 프로그래머스 고득점 Kit, 그래프 )

• 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요 (참고)

#include <bits/stdc++.h>
using namespace std;

int maxLevel = 1;

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

	vector<vector<int>> graph(n + 1);
	vector<bool> visited(n + 1, false);

	for (int i = 0; i < edges.size(); i++)
	{
		graph[edges[i][0]].push_back(edges[i][1]);
		graph[edges[i][1]].push_back(edges[i][0]);
	}

	queue<pair<int, int>> que;
	que.push({ 1, 1 });
	visited[1] = true;

	while (!que.empty())
	{
		int node = que.front().first;
		int currentLevel = que.front().second;
		que.pop();

		if (maxLevel < currentLevel)
		{
			maxLevel = currentLevel;
			answer = 1;
		}
		else answer++;

		for (int i = 0; i < graph[node].size(); i++)
		{
			if (!visited[graph[node][i]])
			{
				visited[graph[node][i]] = true;
				que.push({ graph[node][i], currentLevel + 1 });
			}
		}
	}

	return answer;
}

03-3 ABCDE ( 13023 )

• 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오 (참고)

#include<bits/stdc++.h>
using namespace std;

vector<int> people[2000];
bool visited[2000];
bool ispossible;

void dfs(int node, int depth)
{
	if (depth == 4)
	{
		ispossible = true;
		return;
	}

	visited[node] = true;
	for (int i = 0; i < people[node].size(); ++i)
	{
		int next = people[node][i];

		// if(!visited[next] && ispossible == false) 이렇게 하면 좀더 최적화 된다
		if (!visited[next]) dfs(next, depth + 1);
	}
	visited[node] = false;
}

int N, M;
int main()
{
	cin >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int a, b;
		cin >> a >> b;
		people[a].push_back(b);
		people[b].push_back(a);
	}

	for (int i = 0; i < N; ++i)
	{
		dfs(i, 0);
		if (ispossible) break;
	}

	cout << ispossible << '\n';
}

03-4 연결 요소의 개수 ( 11724 )

• 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오 (참고)

#include<bits/stdc++.h>
using namespace std;

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

/* DFS : 방문기록 남기는 용도 */
void DFS(int vertex)
{
    visited[vertex] = true;
    for (int i = 0; i < vect[vertex].size(); i++) // 최댓값 주의 : 벡터 그 원소에 해당하는 크기만큼 돌아야함
    {
        int idx = vect[vertex][i];
        if (!visited[idx])
        {
            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])
        {
            cnt++;
            DFS(i);
        }
    }
    cout << cnt << "\n";
}

03-5 이분 그래프 ( 1707 )

• 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오 (참고)

// https://hongjw1938.tistory.com/117 이분 그래프 설명

#include<bits/stdc++.h>
using namespace std;

#define RED 1
#define BLUE 2

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

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

	while (!q.empty()) // 큐가 빌 때 까지 반복(전체)
	{
		int now = q.front();
		q.pop();

		for (int i = 0; i < vect[now].size(); i++)
		{
			int next = vect[now][i];

			if (visited[next] == 0)
			{
				q.push(next);

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

bool check()
{
	for (int i = 1; i <= V; i++)
	{
		for (int j = 0; j < vect[i].size(); j++)
		{
			int next = vect[i][j];

			if (visited[i] == visited[next]) 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));
	}
}

03-6 순위 ( 프로그래머스 고득점 Kit, 그래프 )

• 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요 (참고)

#include<bits/stdc++.h>
using namespace std;

int solution(int n, vector<vector<int>> results)
{
	int answer = 0;
	// (n+1) x (n+1) 크기의 2차원 boolean 그래프를 생성합니다
	vector<vector<bool>> graph(n + 1, vector<bool>(n + 1, false));

	// 결과에 따라 그래프를 갱신합니다.
	for (auto r : results)
		graph[r[0]][r[1]] = true; // 선수 r[0]가 선수 r[1]을 이겼다면 true로 표시합니다

	// Floyd-Warshall 알고리즘을 사용하여 그래프를 갱신합니다
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++)
				if (graph[j][i] && graph[i][k])
					graph[j][k] = true;

	// 각 선수에 대해 결과를 계산합니다
	for (int i = 1; i <= n; i++)
	{
		int count = 0;
		for (int j = 1; j <= n; j++)
			if (graph[i][j] || graph[j][i]) count++;

		if (count == n - 1) answer++; // 선수 i의 결과가 n-1개와 일치한다면 answer를 증가시킵니다
	}

	return answer;
}

03-7 네트워크 연결 ( 1922 )

• 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라 모든 컴퓨터를 연결할 수 없는 경우는 없다 (참고)

// https://codekodo.tistory.com/68
// 유니온 파인드를 활용해 MST 문제를 해결한다

#include<bits/stdc++.h>
using namespace std;

int N, M, res = 0;
int parent[1001];
vector<pair<int, pair<int, int>>> v;

int findParent(int a)
{
	if (parent[a] == a) return a;
	else return parent[a] = findParent(parent[a]);
}

void unionParent(int a, int b)
{
	a = findParent(a);
	b = findParent(b);

	if (a < b) parent[b] = a;
	else parent[a] = b;
}

bool sameParent(int a, int b)
{
	a = findParent(a);
	b = findParent(b);

	if (a == b) return true;
	else return false;
}

void solution()
{
	sort(v.begin(), v.end());

	for (int i = 1; i <= N; i++)
		parent[i] = i;

	for (int i = 0; i < M; i++)
	{
		int a = v[i].second.first;
		int b = v[i].second.second;
		int cost = v[i].first;

		if (!sameParent(a, b))
		{
			unionParent(a, b);
			res += cost;
		}
	}

	cout << res;
}

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

	cin >> N;
	cin >> M;

	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		v.push_back({ c, {a, b} });
	}

	solution();

	return 0;
}

Chapter 04 DFS ( 중요도 하 )

04-1 문제

• 설명

Chapter 05 백트래킹 ( 중요도 하 )

05-1 문제

• 설명

Chapter 06 BFS ( 중요도 상 )

06-1 뱀과 사다리 게임 ( 16928 )

• 게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해보자 (참고)

#include<bits/stdc++.h>
using namespace std;

const int MAX = 102;

void game(vector<int>& warp, vector<bool>& visited, int location, int c)
{
	queue<pair<int, int>> que;
	que.push(make_pair(location, c));
	visited[location] = true;

	while (!que.empty())
	{
		// 다음 위치 세팅
		int x = que.front().first;
		int cnt = que.front().second;
		que.pop();

		for (int i = 1; i <= 6; i++)
		{
			// 주사위 숫자만큼 이동
			int nx = x + i;
			int ncnt = cnt + 1;

			// 도착 했다면 정답을 출력
			if (nx == 100)
			{
				cout << ncnt << endl;
				return;
			}
			// 이 조건문이 없어도 정상 실행되는것 확인
			else if (nx < 100)
			{
				// 워프를 태울수 있을때 까지 태운다
				while (warp[nx] != 0)
				{
					nx = warp[nx];
				}

				// 아직 방문한적 없는 노드라면 큐에 넣는다
				if (!visited[nx])
				{
					que.push(make_pair(nx, ncnt));
					visited[nx] = true;
				}
			}
		}
	}
}

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

	vector<int> warp(MAX, 0);
	vector<bool> visited(MAX, false);

	int sadari, snake;
	cin >> sadari >> snake;

	for (int i = 0; i < sadari; i++)
	{
		int from = 0, to = 0;
		cin >> from >> to;
		warp[from] = to;
	}
	for (int i = 0; i < snake; i++)
	{
		int from = 0, to = 0;
		cin >> from >> to;
		warp[from] = to;
	}

	game(warp, visited, 1, 0);

	return 0;
}

06-2 연구소 ( 14502 )

• 연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오 (참고)

#include<bits/stdc++.h>
using namespace std;

int answer = 0;

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

// 여기서는 참조자를 사용해도 된다
void BFS(vector<vector<int>>& mymap)
{
	queue<pair<int, int>> que;

	// 바이러스 최초 위치들을 모두 큐에 담는다
	for (int y = 0; y < mymap.size(); y++)
	{
		for (int x = 0; x < mymap[0].size(); x++)
		{
			if (mymap[y][x] == 2)
				que.push({ x, y });
		}
	}

	// 바이러스를 최대한 퍼뜨린다
	while (!que.empty())
	{
		int x = que.front().first;
		int y = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || mymap[0].size() <= nx || mymap.size() <= ny || mymap[ny][nx] != 0)
				continue;

			que.push({ nx, ny });
			mymap[ny][nx] = 2;
		}
	}

	// 바이러스가 모두 퍼진 상태에서 안전 영역 크기를 계산한다
	int cnt = 0;
	for (int y = 0; y < mymap.size(); y++)
	{
		for (int x = 0; x < mymap[0].size(); x++)
		{
			if (mymap[y][x] == 0)
				cnt++;
		}
	}

	answer = max(answer, cnt);
}

// 여기서는 참조자를 사용하면 안된다
void DFS(vector<vector<int>> mymap, int x, int y, int cnt)
{
	mymap[y][x] = 1;
	cnt = cnt - 1;

	// 벽을 더이상 세울수 없다면 바이러스를 퍼뜨린다
	if (cnt == 0)
	{
		BFS(mymap);

		return;
	}

	// 벽 2개를 세울수 있는 모든 경우의 수를 체크한다
	for (int y = 0; y < mymap.size(); y++)
	{
		for (int x = 0; x < mymap[0].size(); x++)
		{
			if (mymap[y][x] == 0)
				DFS(mymap, x, y, cnt);
		}
	}
}

int main()
{
	int N, M;
	cin >> N >> M;

	vector<vector<int>> mymap(N, vector<int>(M, 0));

	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
			cin >> mymap[y][x];
	}

	// 벽 3개를 세울수 있는 모든 경우의 수를 체크한다
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
		{
			if (mymap[y][x] == 0)
				DFS(mymap, x, y, 3);
		}
	}

	cout << answer << endl;

	return 0;
}

06-3 점프 게임 ( 15558 )

• 각 칸의 정보가 주어졌을 때, 게임을 클리어 할 수 있는지, 없는지 구하는 프로그램을 작성하시오 (참고)

#include<bits/stdc++.h>
using namespace std;

typedef struct
{
	int x, y, x_limit;
}node;

int main()
{
	vector<vector<bool>> visited(2, vector<bool>(200001, false));

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

	for (int y = 0; y < 2; y++)
	{
		for (int x = 0; x < N; x++)
		{
			char value;
			cin >> value;

			if (value == '0')
			{
				visited[y][x] = true;
			}
			else
			{
				visited[y][x] = false;
			}
		}
	}

	// 필요한 변수 초기화
	bool flag = false;
	queue<node> que;
	que.push({ 0, 0, 0 });
	visited[0][0] = true;

	while (!que.empty())
	{
		// 다음 위치 세팅
		node cur = que.front();
		int x = cur.x, y = cur.y, x_limit = cur.x_limit;
		que.pop();

		// 목적지를 넘어서면 플래그를 true로 세팅한다
		if (N <= x)
		{
			flag = true;
			break;
		}

		//전진
		if (visited[y][x + 1] == false)
		{
			visited[y][x + 1] = true;
			que.push({ x + 1, y, x_limit + 1 });
		}

		//후진 
		if (visited[y][x - 1] == false && x_limit < x - 1)
		{
			visited[y][x - 1] = true;
			que.push({ x - 1, y, x_limit + 1 });
		}

		//점프
		if (visited[1 - y][x + K] == false)
		{
			visited[1 - y][x + K] = true;
			que.push({ x + K, 1 - y, x_limit + 1 });
		}

	}

	// 플래그에 따라 결과 출력
	if (flag == false)
		cout << 0;
	else
		cout << 1;
}

06-4 4연산 ( 14395 )

• 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오 (참고)

#include<bits/stdc++.h>
using namespace std;

const long long MAX = 1e9;

set<long long> visited;

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

    int start, target;
    cin >> start >> target;

    if(start == target)
    {
        cout << 0 << "\n";
        return 0;
    }
    
    // 필요한 변수 초기화
    queue<pair<long long, string>> que;
    que.push({start, ""});
    
    while (!que.empty())
    {
        // 다음 숫자 세팅
        long long n = que.front().first;
        string temp = que.front().second;
        que.pop();

        // 원하는 숫자라면 연산자 출력후 리턴
        if (n == target)
        {
            cout << temp << "\n";
            return 0;
        }

        // 현재 노드에서 방문할 수 있는 노드를 모두 큐에 담는다 ( https://twpower.github.io/92-how-to-use-set-in-cpp // count 함수에 대한 정보 )
        if (0 <= n * n && n * n <= MAX && visited.count(n*n) == 0 )
        {
            que.push({ n * n, temp + "*" });
            visited.insert(n*n);
        }
        if (0 <= n + n && n + n <= MAX && visited.count(n+n) == 0)
        {
            que.push({ n + n, temp + "+" });
            visited.insert(n + n);
        }
        if (0 <= n - n && n - n <= MAX && visited.count(n-n) == 0)
        {
            que.push({ n - n, temp + "-" });
            visited.insert(n - n);
        }
        if (n != 0 && 0 <= n / n && n / n <= MAX && visited.count(n/n) == 0)
        {
            que.push({ n / n, temp + "/" });
            visited.insert(n / n);
        }

    }
    
    // 변환이 불가능한 경우 -1을 출력한다
    cout << -1 << "\n";
    return 0;
}

06-5 물통 ( 2251 )

• 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오 (참고)

// https://j2wooooo.tistory.com/130 이분은 push 이후 바로 방문처리 하게함

#include<bits/stdc++.h>
using namespace std;

typedef struct
{
	int a, b, c;
}node;

const int MAX = 201;

int CapacityA, CapacityB, CapacityC;
bool visited[MAX][MAX][MAX];

vector<int> answer;

void Input()
{
	cin >> CapacityA >> CapacityB >> CapacityC;
}

void Solution()
{
	// 필요한 변수 초기화
	queue<node> que;
	que.push({ 0, 0, CapacityC });

	while (!que.empty())
	{
		// 다음 물높이 세팅
		node cur = que.front();
		int a = cur.a;
		int b = cur.b;
		int c = cur.c;
		que.pop();

		// 해당 물높이 방문 처리
		if (visited[a][b][c] == true) continue;
		visited[a][b][c] = true;

		// 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있는 물의 양을 정답지에 넣는다
		if (a == 0) answer.push_back(c);

		// A물통에서 B물통으로 줄 때
		if (CapacityB < a + b) que.push({ a + b - CapacityB, CapacityB, c });
		else que.push({ 0, a + b, c });

		// A물통에서 C물통으로 줄 때
		if (CapacityC < a + c) que.push({ a + c - CapacityC, b, CapacityC });
		else que.push({ 0, b, a + c });

		// B물통에서 A물통으로 줄 때
		if (CapacityA < b + a) que.push({ CapacityA, b + a - CapacityA, c });
		else que.push({ b + a, 0, c });

		// B물통에서 C물통으로 줄 때
		if (CapacityC < b + c) que.push({ a, b + c - CapacityC, CapacityC });
		else que.push({ a, 0, b + c });

		// C물통에서 A물통으로 줄 때
		if (CapacityA < c + a) que.push({ CapacityA, b, c + a - CapacityA });
		else que.push({ c + a, b, 0 });

		// C물통에서 B물통으로 줄 때
		if (CapacityB < c + b) que.push({ a, CapacityB, c + b - CapacityB });
		else que.push({ a, c + b, 0 });
	}

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

	for (int i = 0; i < answer.size(); i++)
	{
		cout << answer[i] << " ";
	}
}

void Solve()
{
	Input();
	Solution();
}

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

	Solve();

	return 0;
}

06-6 토마토 ( 7576 )

• 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라 (참고)

#include <bits/stdc++.h>
using namespace std;

// 그래프 관련 변수
int n, m;
int graph[1001][1001];
queue<pair<int, int>> q;

// 상, 하, 좌, 우 이동
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void bfs(void)
{
	while (!q.empty())
	{
		// main에서 분명히 y 좌표를 first에 입력해놨다
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || m <= nx || n <= ny) continue;
			if (graph[ny][nx] == -1) continue;

			if (graph[ny][nx] == 0)
			{
				q.push({ ny, nx });
				graph[ny][nx] = graph[y][x] + 1;
			}
		}
	}
}

int main()
{
	// 입력받기
	cin >> m >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%d", &graph[i][j]);
			if (graph[i][j] == 1)
			{
				// 분명히 y 좌표를 first에 입력해놨다
				q.push({ i, j });
			}
		}
	}

	// BFS를 통해 탐색
	bfs();

	// 안 익은 토마토 없나 확인
	int result = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			result = max(result, graph[i][j] - 1);

			if (graph[i][j] == 0)
			{
				cout << -1 << endl;
				return 0;
			}
		}
	}

	// 결과 출력
	printf("%d\n", result);
	return 0;
}

06-7 경쟁적 전염 ( 18405 )

• 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오 (참고)

#include<bits/stdc++.h>
using namespace std;

const int MAX = 202;

int arr[MAX][MAX];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

struct Virus
{
	int virus;
	int x;
	int y;
};

bool cmp(const Virus& v1, const Virus& v2)
{
	return v1.virus < v2.virus;
}

int main()
{
	vector<Virus> vec;

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

	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			cin >> arr[y][x];
			vec.push_back({ arr[y][x], x, y });
		}
	}

	int S, X, Y;
	cin >> S >> Y >> X;

	int s = 0;
	sort(vec.begin(), vec.end(), cmp);

	while (s < S)
	{
		int len = vec.size();
		for (int j = 0; j < len; j++)
		{
			Virus v = vec[j];
			for (int i = 0; i < 4; i++)
			{
				int nx = v.x + dx[i];
				int ny = v.y + dy[i];

				if (nx < 0 || ny < 0 || N <= nx || N <= ny) continue;

				if (arr[ny][nx] == 0)
				{
					arr[ny][nx] = v.virus;
					vec.push_back({ arr[ny][nx], nx, ny });
				}
			}
		}

		if (0 < arr[Y - 1][X - 1]) break;
		s++;
	}

	cout << arr[Y - 1][X - 1];

	return 0;
}

06-8 숨바꼭질 4 ( 13913 )

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

#include<bits/stdc++.h>
using namespace std;
#define max 1000001

int N, K;
int parent[max];
bool visited[max];

// 현재 위치와 걸린 시간
struct node
{
	int cur;
	int time;
};

void bfs(int start)
{
	queue<node> q;
	q.push({ start, 0 });
	visited[start] = true;

	while (!q.empty())
	{
		int cur = q.front().cur;
		int time = q.front().time;
		q.pop();

		// 목적지 도착 하면 종료
		if (cur == K)
		{
			cout << time << endl;
			return;
		}

		// 해당 지점을 처음 방문하는 경우 부모 설정 및 방문 처리
		if (0 <= cur - 1)
		{
			if (!visited[cur - 1])
			{
				q.push({ cur - 1, time + 1 });
				visited[cur - 1] = true;
				parent[cur - 1] = cur;
			}
		}
		if (cur + 1 < max)
		{
			if (!visited[cur + 1])
			{
				q.push({ cur + 1, time + 1 });
				visited[cur + 1] = true;
				parent[cur + 1] = cur;
			}
		}
		if (cur * 2 < max)
		{
			if (!visited[cur * 2])
			{
				q.push({ cur * 2, time + 1 });
				visited[cur * 2] = true;
				parent[cur * 2] = cur;
			}
		}
	}
}

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

	cin >> N >> K;
	bfs(N);

	stack<int> stk;

	stk.push(K);
	int cur = K;
	while (cur != N)
	{
		stk.push(parent[cur]);
		cur = stk.top();
	}

	while (!stk.empty())
	{
		cout << stk.top() << ' ';
		stk.pop();
	}

	return 0;
}

06-9 이모티콘 ( 14226 )

• 영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오 (참고)

// https://junbastick.tistory.com/17 참고
#include<iostream>
#include<vector>
#include<queue>

#define endl "\n"
using namespace std;

#define MAX 1001
bool visit[MAX][MAX];

int BFS(int S)
{
	queue<pair<pair<int, int>, int>> q;
	q.push(make_pair(make_pair(1, 0), 0));
	visit[1][0] = true;

	while (!q.empty())
	{
		int screen = q.front().first.first;
		int clip = q.front().first.second;
		int time = q.front().second;
		q.pop();

		// 각 시간대 별로 현재 상황을 사진 찍어놓는다는 느낌
		if (screen == S)
			return time;
		if (!visit[screen][screen])
		{
			q.push(make_pair(make_pair(screen, screen), time + 1));
			visit[screen][screen] = true;
		}
		if (screen + clip <= S && !visit[screen + clip][clip])
		{
			q.push(make_pair(make_pair(screen + clip, clip), time + 1));
			visit[screen + clip][clip] = true;
		}
		if (2 <= screen - 1 && !visit[screen - 1][clip])
		{
			q.push(make_pair(make_pair(screen - 1, clip), time + 1));
			visit[screen - 1][clip] = true;
		}
	}
}

void Answer()
{
	int S;
	cin >> S;
	cout << BFS(S) << endl;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	Answer();
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

//1개는 이미 입력
int S;

int visited[3000][3000];
int main()
{
	cin >> S;
	//현재 상태, 클립보드에 저장된 개수

	queue<pair<int, int>> q;
	q.push({ 1,0 });
	visited[1][0] = 1;

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();
		int now = cur.first;
		int clip = cur.second;

		//체크
		if (now == S)
		{
			cout << visited[now][clip] - 1 << '\n';
			break;
		}

		//1.복사
		int nextClip = now;
		if (visited[now][nextClip] == 0)
		{
			q.push({ now, nextClip });
			visited[now][nextClip] = visited[now][clip] + 1;
		}

		//2.붙여넣기
		if (now + clip <= S)
		{
			if (visited[now + clip][clip] == 0)
			{
				q.push({ now + clip, clip });
				visited[now + clip][clip] = visited[now][clip] + 1;
			}
		}

		//3.삭제
		if (now > 0)
		{
			if (visited[now - 1][clip] == 0)
			{
				q.push({ now - 1, clip });
				visited[now - 1][clip] = visited[now][clip] + 1;
			}
		}
	}

	return 0;
}

06-10 알고스팟 ( 1261 )

• 현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오 (참고)

#include<bits/stdc++.h>
using namespace std;

#define MAX 1e9

int N, M;
int board[101][101];
int dist[101][101];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void bfs()
{
	queue<pair<int, int>> q;
	q.push({ 0,0 });
	dist[0][0] = 0;

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || M <= nx || N <= ny) continue;

			if (board[ny][nx] == 0)
			{
				// 이 경우가 성립한다면 벽을 부술 필요가
				// 없는데 부순애가 지나갔다는 의미
				if (dist[y][x] < dist[ny][nx])
				{
					dist[ny][nx] = dist[y][x];
					q.push({ nx,ny });
				}
			}
			else if (board[ny][nx] == 1)
			{
				// 이 경우가 성립하다면 벽을 더 적게
				// 부수고 지나갈수 있다는 의미
				if (dist[y][x] + 1 < dist[ny][nx])
				{
					dist[ny][nx] = dist[y][x] + 1;
					q.push({ nx,ny });
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> M >> N;
	string str;

	for (int i = 0; i < N; i++)
	{
		cin >> str;
		for (int j = 0; j < M; j++)
		{
			dist[i][j] = MAX;
			board[i][j] = str[j] - '0';
		}
	}

	bfs();
	cout << dist[N - 1][M - 1] << "\n";

	return 0;
}

Chapter 07 완전탐색 ( 중요도 상 )

07-1 테트로미노 ( 14500 )

• 첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다

// https://9967han.tistory.com/15 참고

#include<bits/stdc++.h>
using namespace std;

const int MAX = 501;

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int N, M, ans = 0;

void getMaxNum(vector<vector<int>>& mymap, vector<vector<bool>>& visited, int x, int y, int cnt, int curScore)
{
	// 블록이 4개라면 스코어 갱신이 가능한지 체크
	if (cnt == 4)
	{
		if (ans < curScore) ans = curScore;
		return;
	}

	// 현재 노드에서 만들수 있는 모든 도형을 만들자
	for (int i = 0; i < 4; ++i)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 0 || ny < 0 || M <= nx || N <= ny || visited[ny][nx]) continue;

		visited[ny][nx] = true;
		getMaxNum(mymap, visited, nx, ny, cnt + 1, curScore + mymap[ny][nx]);
		visited[ny][nx] = false;
	}
}

int main()
{
	vector<vector<int>> mymap(MAX, vector<int>(MAX, 0));
	vector<vector<bool>> visited(MAX, vector<bool>(MAX, false));

	cin >> N >> M;

	for (int y = 0; y < N; ++y)
	{
		for (int x = 0; x < M; ++x)
		{
			cin >> mymap[y][x];
		}
	}

	for (int y = 0; y < N; ++y)
	{
		for (int x = 0; x < M; ++x)
		{
			// 모든 노드를 방문한다
			visited[y][x] = true;
			getMaxNum(mymap, visited, x, y, 1, mymap[y][x]);
			visited[y][x] = false;

			// ㅏ ㅓ ㅗ ㅜ 를 만들자
			if (0 <= y - 1 && x + 1 < M && y + 1 < N) //ㅏ
			{
				ans = max(ans, (mymap[y - 1][x] + mymap[y][x] + mymap[y][x + 1] + mymap[y + 1][x]));
			}
			if (0 <= y - 1 && 0 <= x - 1 && y + 1 < N) //ㅓ
			{
				ans = max(ans, (mymap[y - 1][x] + mymap[y][x] + mymap[y][x - 1] + mymap[y + 1][x]));
			}
			if (0 <= y - 1 && 0 <= x - 1 && x + 1 < M) //ㅗ
			{
				ans = max(ans, (mymap[y - 1][x] + mymap[y][x - 1] + mymap[y][x] + mymap[y][x + 1]));
			}
			if (0 <= x - 1 && x + 1 < M && y + 1 < N) //ㅜ
			{
				ans = max(ans, (mymap[y][x - 1] + mymap[y][x] + mymap[y][x + 1] + mymap[y + 1][x]));
			}
		}
	}

	cout << ans;
}

07-2 감시 ( 15683 )

• 첫째 줄에 사각 지대의 최소 크기를 출력한다

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

using namespace std;

int N, M;
int arr[8][8];
vector<pair<int, int>> cctv; // CCTV의 위치를 저장할 벡터
int ans = 987654321; // 최소로 막아야 할 칸의 수

int dy[4] = { 0, -1, 0, 1 }; // 방향에 따른 y좌표 변화량
int dx[4] = { 1, 0, -1, 0 }; // 방향에 따른 x좌표 변화량

// CCTV가 볼 수 있는 영역을 체크하는 함수
void check(int x, int y, int dir)
{
	dir %= 4; // dir이 4보다 큰 경우를 위해 나머지 연산으로 방향을 구함
	while (1)
	{
		int nx = x + dx[dir]; // 현재 위치에서 방향에 따라 이동한 x좌표
		int ny = y + dy[dir]; // 현재 위치에서 방향에 따라 이동한 y좌표

		x = nx; // 다음 위치로 x좌표 갱신
		y = ny; // 다음 위치로 y좌표 갱신

		if (nx < 0 || ny < 0 || M <= nx || N <= ny) return; // 범위를 벗어난 경우 반환
		if (arr[ny][nx] == 6) return; // 벽인 경우 반환
		if (arr[ny][nx] != 0) continue; // 이미 CCTV가 있거나, 이미 감시되는 영역인 경우 넘어감

		arr[ny][nx] = -1; // CCTV로부터 감시되는 영역이므로 -1로 표시
	}
}

// 모든 CCTV를 처리하는 dfs 함수
void dfs(int idx)
{
	// 모든 CCTV를 처리한 경우
	if (idx == cctv.size())
	{
		int cnt = 0; // 막아야 할 칸의 수를 세기 위한 변수
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (!arr[i][j]) cnt++; // CCTV로부터 감시되지 않는 영역의 개수를 센다

		ans = min(ans, cnt); // 최소값 갱신
		return;
	}

	int y = cctv[idx].first;
	int x = cctv[idx].second;
	for (int dir = 0; dir < 4; dir++)
	{
		int tmp[8][8];
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				tmp[i][j] = arr[i][j];

		if (arr[y][x] == 1)
			check(x, y, dir);
		else if (arr[y][x] == 2)
		{
			check(x, y, dir);
			check(x, y, dir + 2);
		}
		else if (arr[y][x] == 3)
		{
			check(x, y, dir);
			check(x, y, dir + 1);
		}
		else if (arr[y][x] == 4)
		{
			check(x, y, dir);
			check(x, y, dir + 1);
			check(x, y, dir + 2);
		}
		else if (arr[y][x] == 5)
		{
			check(x, y, dir);
			check(x, y, dir + 1);
			check(x, y, dir + 2);
			check(x, y, dir + 3);
		}

		dfs(idx + 1);

		// case 종료이므로 초기화
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				arr[i][j] = tmp[i][j];
	}
}

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

	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] != 0 && arr[i][j] != 6)
				cctv.push_back({ i, j });
		}
	}

	dfs(0);
	cout << ans << '\n';

	return 0;
}

07-3 치킨 배달 ( 15686 )

• 첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다 (참고)

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

const int MAX = 50;
const int INF = 987654321;

int N, M;
int result = INF;
int graph[MAX][MAX]; // 치킨 거리를 계산하기 위한 그래프
vector<pair<int, int>> house, chicken; // 집과 치킨집 위치를 저장하는 벡터
bool live[13]; // 치킨집을 선택했는지 여부를 저장하는 배열

int distance(pair<int, int> a, pair<int, int> b) // 두 위치 사이의 거리를 계산하는 함수
{
	return abs(a.first - b.first) + abs(a.second - b.second);
}

void DFS(int idx, int selected) // 치킨집을 선택하는 모든 경우의 수를 탐색하는 함수
{
	if (selected == M) // 선택한 치킨집의 개수가 M개일 경우
	{
		int tempResult = 0;
		for (int i = 0; i < house.size(); i++) // 모든 집에 대해
		{
			int dist = INF;
			for (int j = 0; j < chicken.size(); j++) // 선택한 치킨집 중 가장 가까운 거리를 찾음
			{
				if (live[j])
					dist = min(dist, distance(house[i], chicken[j]));
			}
			tempResult = tempResult + dist; // 가장 가까운 거리를 더해줌
		}
		result = min(result, tempResult); // 최소값을 갱신

		return;
	}

	if (idx == chicken.size()) // 탐색이 끝났을 경우
		return;

	//프랜차이즈 선정
	live[idx] = true; // 현재 치킨집을 선택함
	DFS(idx + 1, selected + 1); // 다음 치킨집을 선택하기 위해 DFS 호출
	//프랜차이즈 선정 X
	live[idx] = false; // 현재 치킨집을 선택하지 않음
	DFS(idx + 1, selected); // 다음 치킨집을 선택하기 위해 DFS 호출
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;

	for (int i = 0; i < N; i++) // 입력받은 그래프를 저장하고, 집과 치킨집의 위치를 벡터에 저장
		for (int j = 0; j < N; j++)
		{
			cin >> graph[i][j];
			if (graph[i][j] == 1)
				house.push_back({ i, j });
			else if (graph[i][j] == 2)
				chicken.push_back({ i, j });
		}

	DFS(0, 0); // 치킨집 선택을 위한 DFS 호출

	cout << result << "\n"; // 최소 치킨 거리 출력

	return 0;
}

07-4 야구 ( 17281 )

• 아인타팀이 얻을 수 있는 최대 점수를 출력한다 (참고)

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

using namespace std;

int main(void)
{
	// 선수 번호는 0 ~ 8로 하여 배열 접근이 쉽게 한다.
	int N;
	vector<vector<int>> score(50, vector<int>(9)); // 각 이닝의 선수별 타격 결과를 저장하는 벡터
	int ans = 0; // 최대 점수를 저장할 변수

	vector<int> player = { 1, 2, 3, 4, 5, 6, 7, 8 }; // 타자 순서를 저장하는 벡터

	cin >> N; // 이닝의 수를 입력 받음

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> score[i][j]; // 각 이닝의 각 선수의 결과를 입력 받음
		}
	}

	do
	{
		int sum = 0; // 현재 순서로 게임을 진행했을 때의 총 점수
		int index = 0; // 현재 타자의 인덱스
		vector<int> tmp_player = player; // 현재 순서로 타자를 저장할 벡터

		// 아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다
		// player 선언한 부분을 보면 8명의 선수밖에 등록 안되어 있는것을 확인할 수 있다
		tmp_player.insert(tmp_player.begin() + 3, 0);

		for (int inning = 0; inning < N; inning++)
		{
			queue<int> base; // 베이스에 있는 주자를 관리하는 큐

			int out = 0; // 현재 이닝의 아웃 수
			while (out != 3) // 아웃 수가 3이 될 때까지 반복
			{
				// 각 이닝 당 타순에 맞게 결과를 저장.
				int state = score[inning][tmp_player[index++]];

				if (state == 0)
				{
					out++; // 아웃
				}
				else if (state == 1)
				{
					// 안타
					// 큐가 비어있으면 1루에 주자 1명을 두고, 2, 3루는 비어둔다.
					// 큐가 비어있지 않으면 큐의 사이즈가 3인지 검사.
					// 사이즈가 3인 경우 베이스를 1루씩 앞당기면서 베이스의 선수 여부에 따라 점수를 더해준다.
					// 사이즈가 3이 아닌 경우 1을 푸시하여 1루에 진루.
					if (base.empty())
					{
						base.push(0);
						base.push(0);
						base.push(1);
					}
					else
					{
						if (base.size() == 3)
						{
							sum += base.front();
							base.pop();
						}
						base.push(1);
					}
				}
				else if (state == 2)
				{
					// 2루타
					// 큐가 비어있으면 2루에 주자 1명을 두고, 1, 3루는 비어둔다.
					// 큐가 비어있지 않으면 큐의 사이즈가 3인지 검사.
					// 사이즈가 3인 경우 베이스를 2루씩 앞당기면서 베이스의 선수 여부에 따라 점수를 더해준다.
					// 사이즈가 3이 아닌 경우 1과 0을 푸시하여 2루에 선수 1명을 진루시키고, 1루에는 주자가 없다.
					if (base.empty())
					{
						base.push(0);
						base.push(1);
						base.push(0);
					}
					else
					{
						if (base.size() == 3)
						{
							for (int i = 0; i < 2; i++)
							{
								sum += base.front();
								base.pop();
							}
						}
						base.push(1);
						base.push(0);
					}
				}
				else if (state == 3)
				{
					// 3루타
					// 큐가 비어있으면 3루에 주자 1명을 두고, 1, 2루는 비어둔다.
					// 큐가 비어있지 않으면 사이즈가 3인지 검사.
					// 사이즈가 3인 경우 베이스를 3루씩 앞당기면서 베이스의 선수 여부에 따라 점수를 더해준다.
					// 사이즈가 3이 아닌 경우 1, 0, 0을 푸시하여 3루에 선수 1명 진루, 1, 2루에는 주자가 없다.
					if (base.empty())
					{
						base.push(1);
						base.push(0);
						base.push(0);
					}
					else
					{
						if (base.size() == 3)
						{
							for (int i = 0; i < 3; i++)
							{
								sum += base.front();
								base.pop();
							}
						}
						base.push(1);
						base.push(0);
						base.push(0);
					}
				}
				else if (state == 4)
				{
					// 홈런
					// 모든 주자가 들어와야 하기 때문에 큐가 빌 때까지 베이스의 선수 여부에 따라 점수를 더해준다.
					// 큐가 비게되면 홈런을 친 선수의 점수까지 더해주는 ++을 진행.
					while (!base.empty())
					{
						sum += base.front();
						base.pop();
					}
					sum++;
				}

				if (index == 9) index = 0;
			}
		}
		//모든 타순을 다르게 하여 최대값을 얻는 점수를 저장.
		ans = ans < sum ? sum : ans;

	} while (next_permutation(player.begin(), player.end()));

	cout << ans;

	return 0;
}

// https://codingnotes.tistory.com/113 킵 해두자

07-5 배열 돌리기 4 ( 17406 )

• 배열 A의 값의 최솟값을 출력한다 (참고)

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

struct Roll
{
	int row, col, size;
};

int N, M, K;
int grid[51][51];
int copiedGrid[51][51]; // Copy of the grid for simulation
vector<Roll> operations;
int order[6];       // Order of rotation operations
bool isChosen[6];   // Indicates if a rotation operation is chosen
int minValue = 987654321;

void performRoll(int row, int col, int size)
{
	for (int d = 1; d <= size; d++)
	{
		int start_x = col - d;
		int start_y = row - d;
		int end_x = col + d;
		int end_y = row + d;

		int tmp = copiedGrid[start_y][start_x];

		// Left side
		for (int i = start_y; i < end_y; i++)
			copiedGrid[i][start_x] = copiedGrid[i + 1][start_x];

		// Bottom side
		for (int j = start_x; j < end_x; j++)
			copiedGrid[end_y][j] = copiedGrid[end_y][j + 1];

		// Right side
		for (int i = end_y; start_y < i; i--)
			copiedGrid[i][end_x] = copiedGrid[i - 1][end_x];

		// Top side
		for (int j = end_x; start_x < j; j--)
			copiedGrid[start_y][j] = copiedGrid[start_y][j - 1];

		copiedGrid[start_y][start_x + 1] = tmp;
	}
}

void simulate()
{
	int result = 0;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			copiedGrid[i][j] = grid[i][j];

	// Perform rotation operations in the specified order
	for (int i = 0; i < K; i++)
	{
		int operationIdx = order[i];
		int row = operations[operationIdx].row;
		int col = operations[operationIdx].col;
		int size = operations[operationIdx].size;
		performRoll(row, col, size);
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
			result += copiedGrid[i][j];

		minValue = min(minValue, result);
		result = 0;
	}
}

void dfs(int count)
{
	if (count == K)
	{
		simulate();
		return;
	}

	for (int i = 0; i < K; i++)
	{
		if (isChosen[i]) continue;

		order[count] = i;
		isChosen[i] = true;
		dfs(count + 1);
		isChosen[i] = false;
	}
}

void solve()
{
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
			cin >> grid[i][j];
	}

	for (int i = 0; i < K; i++)
	{
		int row, col, size;
		cin >> row >> col >> size;
		operations.push_back({ row, col, size });
	}

	dfs(0);
	cout << minValue << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	return 0;
}

// https://11001.tistory.com/30
// https://jaimemin.tistory.com/1482

07-6 테트리스 ( 3019 )

• 블록을 놓는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오 (참고)

// 강좌 - 알고리즘 중급 - 2/3
// https://www.acmicpc.net/problem/3019
// https://hsdevelopment.tistory.com/506 참고

#include <bits/stdc++.h>
using namespace std;

const int MAX = 105;

int board[MAX], c, p;
vector<string> v;

int simulation(int number)
{
	int ret = 0;

	if (number == 1)
	{
		v.push_back("0");
		v.push_back("0000");
	}
	else if (number == 2)
	{
		v.push_back("00");
	}
	else if (number == 3)
	{
		v.push_back("001");
		v.push_back("10");
	}
	else if (number == 4)
	{
		v.push_back("100");
		v.push_back("01");
	}
	else if (number == 5)
	{
		v.push_back("000");
		v.push_back("01");
		v.push_back("101");
		v.push_back("10");
	}
	else if (number == 6)
	{
		v.push_back("000");
		v.push_back("00");
		v.push_back("011");
		v.push_back("20");
	}
	else if (number == 7)
	{
		v.push_back("000");
		v.push_back("02");
		v.push_back("110");
		v.push_back("00");
	}

	for (int i = 0; i < v.size(); i++)
	{
		int len = v[i].length(); // 현재 도형의 길이를 구합니다

		vector<int> temp;
		for (auto strnum : v[i])
		{
			temp.push_back(strnum - '0'); // 현재 도형의 각 자리 숫자를 temp 벡터에 저장합니다
		}

		for (int j = 0; j + len - 1 < c; j++)
		{
			bool calc = true;
			for (int k = j; k < j + len - 1; k++)
			{
				// board의 모든 구역에 temp를 맞춰봐야 하니까 board수식과 temp 수식이 다르다
				// 현재 도형과 게임 보드의 숫자 차이를 비교하여 일치하는지 확인합니다
				if (board[k] - board[k + 1] != temp[k - j] - temp[k - j + 1])
				{
					calc = false;
					break;
				}
			}
			if (calc)
			{
				++ret; // 현재 도형과 일치하는 부분을 찾았으므로 ret 값을 증가시킵니다
			}
		}
	}

	return ret;
}

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

	cin >> c >> p;

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

	cout << simulation(p) << endl;

	return 0;
}

07-7 직사각형으로 나누기 ( 1451 )

• 입력으로 주어진 직사각형을 3개의 작은 직사각형으로 나누었을 때, 각각의 작은 직사각형의 합의 곱을 최대로 하는 프로그램을 작성하시오 (참고)

// 강좌 - 없음
// https://www.acmicpc.net/problem/1451

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

int N, M;
int Numbers[101][101];
long long Max = -1;

int getSum(int startY, int startX, int endY, int endX)
{
	int sum = 0;
	for (int i = startY; i <= endY; i++)
	{
		for (int j = startX; j <= endX; j++)
		{
			sum += Numbers[i][j];
		}
	}

	return sum;
}

void solution()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			scanf("%1d", &Numbers[i][j]);
		}
	}

	// 1번 모양
	for (int i = 0; i < N - 2; i++)
	{
		for (int j = i + 1; j < N - 1; j++)
		{
			long long square1 = getSum(0, 0, i, M - 1);
			long long square2 = getSum(i + 1, 0, j, M - 1);
			long long square3 = getSum(j + 1, 0, N - 1, M - 1);
			Max = max(Max, square1 * square2 * square3);
		}
	}

	// 2번 모양
	for (int i = 0; i < M - 2; i++)
	{
		for (int j = i + 1; j < M - 1; j++)
		{
			long long square1 = getSum(0, 0, N - 1, i);
			long long square2 = getSum(0, i + 1, N - 1, j);
			long long square3 = getSum(0, j + 1, N - 1, M - 1);
			Max = max(Max, square1 * square2 * square3);
		}
	}

	// 3번 모양 ( 늘어나는 직사각형을 가장 우선시 한다 )
	for (int i = M - 1; 0 < i; i--)
	{
		for (int j = 0; j < N - 1; j++)
		{
			long long square1 = getSum(0, i, N - 1, M - 1);
			long long square2 = getSum(0, 0, j, i - 1);
			long long square3 = getSum(j + 1, 0, N - 1, i - 1);
			Max = max(Max, square1 * square2 * square3);
		}
	}

	// 4번 모양 ( 늘어나는 직사각형을 가장 우선시 한다 )
	for (int i = 0; i < M - 1; i++)
	{
		for (int j = 0; j < N - 1; j++)
		{
			long long square1 = getSum(0, 0, N - 1, i);
			long long square2 = getSum(0, i + 1, j, M - 1);
			long long square3 = getSum(j + 1, i + 1, N - 1, M - 1);
			Max = max(Max, square1 * square2 * square3);
		}
	}

	// 5번 모양 ( 늘어나는 직사각형을 가장 우선시 한다 )
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 0; j < M - 1; j++)
		{
			long long square1 = getSum(0, 0, i, M - 1);
			long long square2 = getSum(i + 1, 0, N - 1, j);
			long long square3 = getSum(i + 1, j + 1, N - 1, M - 1);
			Max = max(Max, square1 * square2 * square3);
		}
	}

	// 6번 모양 ( 늘어나는 직사각형을 가장 우선시 한다 )
	for (int i = N - 1; 0 < i; i--)
	{
		for (int j = 0; j < M - 1; j++)
		{
			long long square1 = getSum(i, 0, N - 1, M - 1);
			long long square2 = getSum(0, 0, i - 1, j);
			long long square3 = getSum(0, j + 1, i - 1, M - 1);
			Max = max(Max, square1 * square2 * square3);
		}
	}

	cout << Max << endl;
}

int main()
{
	solution();
	return 0;
}

// https://nim-code.tistory.com/89
// https://dbstndi6316.tistory.com/116

07-8 십자가 2개 놓기 ( 17085 )

• 첫째 줄에 놓은 십자가 넓이의 곱의 최댓값을 출력한다 (참고)

// 강좌 - 알고리즘 중급 - 2/3

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int n, m;
char map[16][16];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

bool visited[16][16];
int chk[16][16];

typedef long long ll;
ll ans = 0;

bool checkRange(int x, int y)
{
	if (x < 0 || m <= x || y < 0 || n <= y)
		return false;

	return true;
}

void dfs(int cnt, ll res)
{
	if (cnt == 2)
	{
		// 최대 너비를 계산
		ans = ans < res ? res : ans;
		return;
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (chk[i][j] && !visited[i][j])
			{
				// 현재 위치를 방문했음을 표시하고, 방문 배열을 복사
				bool c_visited[16][16];
				memcpy(c_visited, visited, sizeof(visited));

				visited[i][j] = true;
				int sum = 1;

				int limit = chk[i][j] - 1;
				int idx = 1;

				// limit이 0일 경우 십자가의 넓이는 1이다
				if (!limit) dfs(cnt + 1, res * sum);

				while (limit--)
				{
					bool state = true;
					for (int d = 0; d < 4; d++)
					{
						int ny = i + dy[d] * idx;
						int nx = j + dx[d] * idx;

						if (checkRange(nx, ny) && !visited[ny][nx])
						{
							visited[ny][nx] = true;
							sum++;
						}
						else
						{
							state = false;
							break;
						}
					}

					if (state)
					{
						dfs(cnt + 1, res * sum);
						idx++;
					}
					else break;
				}
				// 방문 배열을 이전 상태로 되돌림
				memcpy(visited, c_visited, sizeof(visited));
			}
		}
	}
}

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

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> map[i][j];
		}
	}

	// 각 위치에서 십자가의 최대 크기를 구함
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == '#')
			{
				int idx = 1;
				bool state = true;
				while (state)
				{
					for (int d = 0; d < 4; d++)
					{
						int ny = i + dy[d] * idx;
						int nx = j + dx[d] * idx;

						if (!checkRange(nx, ny) || map[ny][nx] != '#')
						{
							state = false;
							break;
						}
					}
					if (state) idx++;
				}
				chk[i][j] = idx;
			}
		}
	}

	dfs(0, 1);
	cout << ans << '\n';
	return 0;
}

// 강좌 - 알고리즘 중급 - 2/3
// https://www.acmicpc.net/problem/17085

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll rows, cols, ans;
string grid[20];

ll findLargestCross(ll x, ll y, ll depth)
{
	ll ret = 0;
	for (int i = 0; i <= 7; i++) // 십자가 길이에 대한 반복문
	{
		ll valid = 1;
		for (int j = -i; j <= i; j++) // 배치 가능 여부 확인
			if (x + j < 0 || rows <= x + j || y + j < 0 || cols <= y + j || grid[x + j][y] != '#' || grid[x][y + j] != '#')
				valid = 0;

		if (valid)
		{
			for (int j = -i; j <= i; j++)
			{
				grid[x + j][y] = '.';
				grid[x][y + j] = '.';
			}

			if (depth) // 두 번째 십자가인 경우 바로 반환
				ret = i * 4 + 1;
			else // 첫 번째 십자가인 경우 다시 탐색
			{
				for (int j = 0; j < rows; j++)
					for (int k = 0; k < cols; k++)
						ret = max(ret, (i * 4 + 1) * findLargestCross(j, k, 1));
			}

			for (int j = -i; j <= i; j++)
			{
				grid[x + j][y] = '#';
				grid[x][y + j] = '#';
			}
		}
		else
			break;
	}

	return ret;
}

int main()
{
	cin >> rows >> cols;
	for (int i = 0; i < rows; i++)
		cin >> grid[i];

	for (int i = 0; i < rows; i++)
		for (int j = 0; j < cols; j++)
			ans = max(ans, findLargestCross(i, j, 0));

	cout << ans;
	return 0;
}

// https://jayrightthere.tistory.com/entry/BOJ-17085-%EC%8B%AD%EC%9E%90%EA%B0%80-2%EA%B0%9C-%EB%86%93%EA%B8%B0
// https://nanyoungkim.tistory.com/184
// https://he1fire.tistory.com/108

07-9 스도쿠 ( 2580 )

• 게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오 (참고)

// 강좌 - 코딩 테스트 준비 - 연습

#include <iostream>
using namespace std;

int emptyCellCount = 0; // 빈 셀의 개수를 저장하는 변수
int sudoku[9][9]; // 스도쿠 보드를 나타내는 2차원 배열
int emptyCells[81][2]; // 빈 셀의 좌표를 저장하는 배열

// 백트래킹 함수
bool backtracking(int k)
{
	if (k == emptyCellCount) return true; // 모든 빈 셀에 대한 수를 다 채웠을 경우 1을 반환

	int y = emptyCells[k][0], x = emptyCells[k][1]; // 현재 채워야 할 빈 셀의 좌표
	int startX = (x / 3) * 3, startY = (y / 3) * 3; // 현재 채워야 할 빈 셀이 속한 3x3 영역의 시작 좌표
	bool check[10] = { false }; // 현재 채워야 할 빈 셀에서 가능한 숫자를 체크하는 배열
	bool result = false; // 백트래킹 결과를 저장하는 변수

	// 현재 행과 열에 이미 사용된 숫자를 체크
	for (int i = 0; i < 9; i++)
		check[sudoku[y][i]] = check[sudoku[i][x]] = true;

	// 현재 3x3 영역에 이미 사용된 숫자를 체크
	for (int i = startY; i < startY + 3; i++)
		for (int j = startX; j < startX + 3; j++)
			check[sudoku[i][j]] = true;

	// 가능한 숫자를 하나씩 시도하면서 백트래킹 수행
	for (int i = 1; i <= 9; i++)
	{
		if (check[i] == false) // 숫자 i가 사용되지 않았을 경우
		{
			sudoku[y][x] = i; // 숫자 i를 현재 채워야 할 빈 셀에 대입
			result = backtracking(k + 1); // 다음 빈 셀로 넘어가기 위해 백트래킹 수행
			if (result) break; // 백트래킹 결과가 true인 경우 (스도쿠가 완성된 경우) 루프 종료
			sudoku[y][x] = 0; // 백트래킹 결과가 false인 경우 (스도쿠가 완성되지 않은 경우) 숫자 i를 제거하고 다른 숫자 시도
		}
	}

	return result; // 백트래킹 결과 반환
}

int main()
{
	// 스도쿠 보드 입력 받기
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> sudoku[i][j];
			if (sudoku[i][j] == 0)
			{
				emptyCells[emptyCellCount][0] = i; // 빈 셀의 행 좌표를 저장
				emptyCells[emptyCellCount][1] = j; // 빈 셀의 열 좌표를 저장
				emptyCellCount++; // 빈 셀 개수 증가
			}
		}
	}

	backtracking(0);

	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
			cout << sudoku[i][j] << " ";
		cout << "\n";
	}
}

07-10 N-Queen ( 9663 )

• N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오 (참고)

// 강좌 - 코딩 테스트 준비 - 연습

#include<iostream>
#include<cmath>

#define endl "\n"
#define MAX 15
using namespace std;

int N, Answer;
int board[MAX];

void Input()
{
	cin >> N;  // N 입력 받기
}

bool CanPlaceQueen(int row)
{
	for (int i = 0; i < row; i++)
	{
		if (board[i] == board[row] || abs(board[row] - board[i]) == row - i)
			return false;  // 같은 열이거나 대각선에 위치한 퀸이 있으면 놓을 수 없음
	}

	return true;  // 놓을 수 있는 자리
}

void DFS(int row)
{
	if (row == N)
	{
		Answer++;  // 퀸을 모두 놓았으면 경우의 수 증가
		return;
	}

	for (int col = 0; col < N; col++)
	{
		board[row] = col;  // 현재 행에서 열의 위치 지정
		if (CanPlaceQueen(row))
			DFS(row + 1);  // 다음 행으로 이동하여 퀸 놓기 시도
	}
}

void PrintAnswer()
{
	cout << Answer << endl;  // 결과 출력
}

void Solve()
{
	Input();  // 입력 받기
	DFS(0);  // 퀸 놓기 시작
	PrintAnswer();  // 결과 출력
}

int main(void)
{
	Solve();

	return 0;
}

Chapter 08 슬라이딩윈도우 + 투포인터 ( 중요도 상 )

08-1 두 큐 합 같게 만들기 ( 2022 KAKAO TECH INTERNSHIP )

• 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요 (참고)

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

int solution(vector<int> queue1, vector<int> queue2)
{
	// 각 큐의 합을 저장하는 변수
	long long sum1 = 0, sum2 = 0;
	// 큐 1과 큐 2를 저장하는 큐
	queue<int> q1, q2;

	// 큐 1에 있는 모든 수를 큐에 추가하고 각 수의 합을 구함
	for (int num : queue1)
	{
		q1.push(num);
		sum1 += num;
	}

	// 큐 2에 있는 모든 수를 큐에 추가하고 각 수의 합을 구함
	for (int num : queue2)
	{
		q2.push(num);
		sum2 += num;
	}

	// 큐 1과 큐 2에서 뽑아야 하는 수의 인덱스
	int idx1 = 0, idx2 = 0;
	// 더해진 총 수의 개수
	int total = queue1.size() + queue2.size();
	// 수행해야 하는 연산의 횟수
	int operations = 0;

	// 두 큐에서 뽑아야 할 수의 인덱스가 총 수의 개수보다 작을 때까지 반복
	while (idx1 < total && idx2 < total)
	{
		// 두 큐의 합이 같으면 연산을 수행하지 않고 연산 횟수를 반환
		if (sum1 == sum2)
		{
			return operations;
		}

		// 연산 횟수를 증가
		operations++;

		// 큐 1의 합이 큐 2의 합보다 작으면 큐 2에서 수를 뽑아 큐 1에 추가
		if (sum1 < sum2)
		{
			int cur = q2.front();
			q2.pop();

			q1.push(cur);
			sum1 += cur;
			sum2 -= cur;
			idx2++;
		}
		// 큐 2의 합이 큐 1의 합보다 작으면 큐 1에서 수를 뽑아 큐 2에 추가
		else
		{
			int cur = q1.front();
			q1.pop();

			q2.push(cur);
			sum2 += cur;
			sum1 -= cur;
			idx1++;
		}
	}

	// 큐 1과 큐 2의 합이 같아질 수 없으면 -1 반환
	return -1;
}

08-2 귀여운 라이언 ( 15565 )

• 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라 (참고)

#include<bits/stdc++.h>
using namespace std;

int N, K;
vector<int> pos;

int main()
{
	int currentDoll;
	cin >> N >> K;

	for (int i = 0; i < N; ++i)
	{
		cin >> currentDoll;
		if (currentDoll == 1)
			pos.push_back(i);
	}

	if (pos.size() < K)
	{
		cout << -1 << endl;
		return 0;
	}

	int ans = 1e9;
	// size가 5 K가 3이라고 가정하고 상상해 보자
	for (int i = 0; i <= pos.size() - K; ++i)
	{
		ans = min(ans, pos[i + K - 1] - pos[i] + 1);
	}

	cout << ans << endl;
}

08-3 수 고르기 ( 2230 )

• N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오 (참고)

#include<bits/stdc++.h>
using namespace std;

// MAX가 1e9면 안된다는것 주의
#define MAX 2000000000

int main()
{
	int answer = MAX;

	int n = 0, target = 0;
	cin >> n >> target;

	vector<int> vecNumber(n, 0);
	for (int i = 0; i < n; ++i)
		cin >> vecNumber[i];

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

	// target이 0이라면 start가 OutOfBounds를 유발할 수 있다
	int start = 0, end = 0;
	while (start < n && end < n)
	{
		if (vecNumber[end] - vecNumber[start] < target)
			end = end + 1;
		else
		{
			answer = min(answer, vecNumber[end] - vecNumber[start]);
			start = start + 1;
		}
	}

	cout << answer << endl;
}

08-4 겹치는 건 싫어 (20922)

• 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자 (참고)

#include<bits/stdc++.h>
#define AMAX 200001
#define DMAX 100001
using namespace std;

int arr[AMAX];
int dup[DMAX];

int main()
{
	ios::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];
	}

	int answer = 0;
	int left = 1;
	int right = 1;

	while (right <= n)
	{
		if (dup[arr[right]] < k)
		{
			dup[arr[right]]++;
			answer = max(answer, right - left + 1);
			right = right + 1;
		}
		else
		{
			dup[arr[left]]--;
			left = left + 1;
		}
	}
	cout << answer;

	return 0;
}

08-5 두 용액 ( 2470 )

• 산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오 (참고)

#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;

	vector<int> ans(2);
	int start = 0, end = n - 1, min = 2000000001;
	int arr[n];

	for (int i = 0; i < n; i++) cin >> arr[i];

	sort(arr, arr + n);
	while (start < end)
	{
		int sum = arr[start] + arr[end];

		if (abs(sum) < abs(min))
		{
			ans[0] = arr[start];
			ans[1] = arr[end];
			min = sum;
		}

		if (sum < 0) start++;
		else end--;
	}

	for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";

	return 0;
}

08-6 회전 초밥 ( 2531 )

• 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

int N, d, k, c;
int dish, cnt, coupon, maxi = 0;
int sushi[300001];
int check[3001];
vector<int> eat;

int main()
{
	// N:접시수 d:초밥종류수 k:연속접시 C:쿠폰번호
	cin >> N >> d >> k >> c;

	// 회전벨트 위 초밥
	for (int i = 0; i < N; i++) cin >> sushi[i];

	// 슬라이딩 윈도우
	for (int i = 0; i < N; i++)
	{
		dish = 0; // 중복된 스시 체크
		coupon = 1; // 쿠폰 스시가 있는지 확인
		for (int j = i; j < i + k; j++)
		{
			if (check[sushi[j % N]] == 1) dish++; // 이미 먹은 초밥일 경우 중복 수 표시	
			else check[sushi[j % N]] = 1; // 처음 먹어보는 초밥일 경우 체크		

			if (sushi[j % N] == c) coupon = 0; // 쿠폰 스시 있을 시
		}

		maxi = max(maxi, k - dish + coupon); //연속으로 먹을 수 있는 최대접시 - 중복접시 + 쿠폰스시	
		memset(check, 0, sizeof(check)); // 체크 초기화
	}

	cout << maxi;
}

08-7 가장 긴 짝수 연속한 부분 수열 (large) ( 22862 )

• 수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자

#include <bits/stdc++.h>
using namespace std;

int arr[1000010];

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

	int n, k;
	cin >> n >> k;

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

	int start = 0, end = 0;
	int cnt = (arr[start] & 1) ? 1 : 0;
	int max_len = 0;

	while (start < n && end < n)
	{
		while (end < n - 1)
		{
			if (arr[end + 1] & 1)
			{
				if (cnt < k)
					cnt++;
				else
					break;
			}
			end++;
		}

		max_len = max(max_len, end - start + 1 - cnt);

		if (arr[start] & 1)
			cnt--;

		start++;
	}

	cout << max_len;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int result = 0;

    int numCount, maxDeleteCnt;
    cin >> numCount >> maxDeleteCnt;

    vector<int> numbers;
    int input;
    for (int i = 0; i < numCount; i++)
    {
        cin >> input;
        numbers.push_back(input);
    }

    int currentDeleteCnt = 0;
    int currentLen = 0;
    int left = 0;
    int right = 0;

    while (right < numCount)
    {
        if (numbers[right] % 2 == 0)
        {
            currentLen++;
            right++;
            result = max(result, currentLen - currentDeleteCnt);
        }
        else
        {
            if (currentDeleteCnt + 1 <= maxDeleteCnt)
            {
                currentDeleteCnt++;
                currentLen++;
                result = max(result, currentLen - currentDeleteCnt);
                right++;
            }
            else
            {
                if (right > left)
                {
                    if (numbers[left] % 2 == 1) currentDeleteCnt--;
                    left++;
                    currentLen--;
                }
                else
                {
                    left++;
                    right++;
                }
            }
        }
    }

    cout << result;

    return 0;
}

08-8 좋다 ( 1253 )

• N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라

#include<bits/stdc++.h>
using namespace std;

int N;
long long num[2010];
int Left, Right;
int ans;

int main(void)
{
	cin >> N;

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

	sort(num + 1, num + N + 1);

	for (int i = 1; i <= N; i++)
	{
		long long find = num[i];
		Left = 1;
		Right = N;

		// 투포인터 알고리즘 활용 
		while (Left < Right)
		{
			if (num[Left] + num[Right] == find)
			{
				if (Left == i) Left++;
				else if (Right == i) Right--;
				else
				{
					ans++;
					break;
				}
			}
			else if (num[Left] + num[Right] < find) Left++;
			else Right--;
		}
	}

	cout << ans;

	return 0;
}

08-9 부분합 ( 1806 )

• 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

#define MAX 1e9

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

	int right = 0;
	int left = 0;
	int sum = arr[0];
	int minlength = MAX;
	while (left < N && right < N)
	{
		// 합이 크면 왼쪽 최소길이 갱신하고 움직이기
		if (S <= sum)
		{
			int length = right - left + 1;
			minlength = min(minlength, length);
			sum = sum - arr[left];
			left++;
		}
		// 합이 작으면 오른쪽 움직이기
		else
		{
			right++;
			sum = sum + arr[right];
		}
	}
    
	// 조건 만족할 수 없으면 0
	if (minlength == MAX)
	{
		minlength = 0;
	}
    
	cout << minlength;
	return 0;
}

08-10 용액 합성하기 ( 14921 )

• 이 중 두 개의 용액을 혼합하여 만들 수 있는 0에 가장 가까운 특성값 B를 출력하시오

#include<bits/stdc++.h>
#define MAX 100000
using namespace std;

int a[MAX];
int answer = 200000000;

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

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];

	int left = 0;
	int right = n - 1;
	sort(a, a + n);
	while (left < right)
	{
		// 두 용액 혼합
		int sum = a[left] + a[right];

		// 0에 더 가까우면 업데이트
		if (abs(sum) < abs(answer))
		{
			answer = sum;
		}

		if (sum == 0)
			break;
		else if (sum < 0)
			left++;
		else
			right--;
	}

	cout << answer;
	return 0;
}

08-11 고냥이 ( 16472 )

• 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지가 궁금해졌다

#include<bits/stdc++.h>
using namespace std;
int alpha[26];

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

	int num, len, result = 0;
	string str;
	cin >> num >> str;
	len = str.size();
	int l = 0, r = 0, cnt = 0;

	while (l < len && r < len)
	{
		while (cnt <= num && r < len)
		{
			int idx = str[r] - 'a';
			alpha[idx]++;
			if (alpha[idx] == 1) cnt++;
			if (cnt <= num) result = max(result, r - l + 1);
			r = r + 1;
		}
		while (num < cnt && l < len)
		{
			int idx = str[l] - 'a';
			alpha[idx]--;
			if (alpha[idx] == 0) cnt--;
			l = l + 1;
		}
	}

	cout << result;
	return 0;
}

Chapter 09 문자열 ( 중요도 중 )

09-1 회문 ( 17609 )

• 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다

09-2 문자열 게임 2 ( 20437 )

• T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다 만약 만족하는 연속 문자열이 없을 시 -1을 출력한다

09-3 회문은 회문아니야!! ( 15927 )

• 팰린드롬이 아닌 가장 긴 부분문자열의 길이를 출력한다 그런 부분문자열이 없으면 -1을 출력한다

09-4 IPv6 ( 3107 )

• 첫째 줄에, 입력으로 주어진 IPv6의 축약되지 않은 형태를 출력한다

09-5 잠수함식별 ( 2671 )

• 입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 “SUBMARINE”을 출력하고, 그렇지 않으면 “NOISE”를 출력한다

09-6 비슷한 단어 ( 2179 )

• 첫째 줄에 S를, 둘째 줄에 T를 출력한다 단, 이 두 단어는 서로 달라야 한다 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다

09-7 문자열 폭팔 ( 9935 )

• 첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다

09-8 매칭 점수 ( 2019 KAKAO BLIND RECRUITMENT )

• N줄에 걸쳐 문제에서 설명한 대로 문자열을 정렬한 결과를 출력한다

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

09-9 가사 검색 ( 2020 KAKAO BLIND RECRUITMENT )

• 가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요

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

09-10 문자열 압축 ( 2020 KAKAO BLIND RECRUITMENT )

• 압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요

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

Chapter 10 DP ( 중요도 하 )

10-1 타일 채우기 ( 2133 )

• 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자

// https://www.youtube.com/watch?v=E_-dFdvy288 참고
// https://velog.io/@matcha_/%EB%B0%B1%EC%A4%80-2133-%ED%83%80%EC%9D%BC-%EC%B1%84%EC%9A%B0%EA%B8%B0-C-DP 참고

#include <iostream>
using namespace std;

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

    int N;
    cin >> N;

    int d[31];
    d[0] = 1;  // 초기 조건: 세로로 놓인 2x0 타일 1개
    d[1] = 0;  // 초기 조건: 세로로 놓인 2x1 타일은 만들 수 없음
    d[2] = 3;  // 초기 조건: 가로로 놓인 2x1 타일 3개

    for (int n = 3; n <= N; n++)
    {
        if (n % 2 != 0)
            d[n] = 0;  // 홀수인 경우 타일을 만들 수 없음
        else
        {
            for (int i = 2; i <= N; i = i + 2)
            {
                if (i == 2)
                    d[n] = d[n - i] * d[2];  // 2x2 타일 1개로 구성
                else if (0 <= (n - i))
                    d[n] = d[n] + d[n - i] * 2;  // 2x(i) 타일을 추가로 넣을 때의 경우의 수
            }
        }
    }
    cout << d[N];
}

10-2 가장 큰 정사각형 ( 1915 )

• 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오

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

10-3 미로에 갇힌 상근 ( 5069 )

• 상근이가 있는 방에서 시작해서 방을 n번 이동해서, 다시 원래 있던 방으로 돌아오는 경로의 수를 구하려고 한다

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

10-4 방법을 출력하지 않는 숫자 맞추기 ( 13392 )

• 상근이가 있는 방에서 시작해서 방을 n번 이동해서, 다시 원래 있던 방으로 돌아오는 경로의 수를 구하려고 한다

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

10-5 영훈이의 색칠공부 ( 14578 )

• N과, 장난감의 수가 주어질 때, 트리를 장식하는 경우의 수를 출력하는 프로그램을 작성하시오

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

10-6 경로 찾기 ( 1513 )

• 오락실을 0개 방문했을 때부터, C개 방문했을 때 까지 경우의 수를 출력하는 프로그램을 작성하시오

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

10-7 로봇 조종하기 ( 2169 )

• 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오

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

10-8 욕심쟁이 판다 ( 1937 )

• 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라

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

10-9 타일 채우기 ( 2718 )

• 타일을 채우는 방법의 개수를 출력하는 프로그램을 작성하시오

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

10-10 파이프 옮기기 2 ( 17069 )

• 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자

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

// https://nurbscalculator.in/
class BSpline
{
private:
    std::vector<double> knots;
    std::vector<std::vector<double>> controlPoints;
    int degree;

public:
    BSpline(const std::vector<double>& knotVector, const std::vector<std::vector<double>>& controlPts, int deg)
        : knots(knotVector), controlPoints(controlPts), degree(deg) {}

    double basisFunction(int i, int k, double t) {
        if (k == 1) {
            if (knots[i] <= t && t < knots[i + 1]) return 1;
            else return 0;
        }

        double term1 = 0, term2 = 0;

        if (knots[i + k - 1] - knots[i] != 0)
            term1 = (t - knots[i]) / (knots[i + k - 1] - knots[i]) * basisFunction(i, k - 1, t);

        if (knots[i + k] - knots[i + 1] != 0)
            term2 = (knots[i + k] - t) / (knots[i + k] - knots[i + 1]) * basisFunction(i + 1, k - 1, t);

        return term1 + term2;
    }

    std::vector<double> evaluate(double t) {
        std::vector<double> point(controlPoints[0].size(), 0.0);

        for (int i = 0; i < controlPoints.size(); ++i) {
            double basis = basisFunction(i, degree + 1, t);
            for (int j = 0; j < point.size(); ++j) {
                point[j] += basis * controlPoints[i][j];
            }
        }

        return point;
    }
};

int main()
{
    // 제어점의 수를 n이라고 하면 B-spline 곡선의 차수를 k라고 합니다
    // 그러면 knots 벡터의 크기는 n + k + 1이어야 합니다 ( Clamped at start, Clamped at end )
    std::vector<double> knots = { 0, 0, 0, 0, 1, 1, 1, 1 };
    std::vector<std::vector<double>> controlPoints = { {0, 0, 1}, {1, 1, 0}, {2, -1, 0 }, {3, 0, 0} };
    int degree = 3;

    BSpline spline(knots, controlPoints, degree);

    // Evaluate the spline at t = 0.4
    std::vector<double> result = spline.evaluate(0.4);

    // Output the result
    std::cout << "Result at t = 0.4: (" << result[0] << ", " << result[1] << ", " << result[2] << ")" << std::endl;

    return 0;
}

맨 위로 이동하기