재시민

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

문제 설명

연속된 k 개의 초밥을 먹으면 1개의 쿠폰을 준다.

이 때, 이벤트를 참여하면서 먹을 수 있는 초밥 개수의 최댓값을 구하자.

인사이트

처음에 생각한 방법

1. 투포인터를 사용하기 위해 deque을 사용하고 left, right를 이용해 슬라이딩 윈도우를 구현하자.
2. 한번의 슬라이딩 윈도우 탐색을 하고나면 deque의 원소를 unorderd_set 에 옮겨 중복되는 값을 제거하고 쿠폰으로 받는 초밥의 번호가 포함되어있는지 확인해 최대 가짓수를 최신화한다.

오류 코드

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

int N, d, k, c;

vector<int> rail;
unordered_set<int> s;
deque<int>dq;

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

    cin >> N >> d >> k >> c;

    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        rail.push_back(n);
    }

    for (int i = 0; i < k; i++) {
        dq.push_back(rail[i]);
    }

    int left = 0;
    int right = k - 1;

    int maxx = dq.size();
    for (int i = 1; i <= N; i++) {
        dq.pop_front();

        left++;
        right++;

        if (left >= N) {
            left = 0;
        }
        if (right >= N) {
            right = 0;
        }

        dq.push_back(rail[right]);
        //최댓값 최신화

        unordered_set<int> tmp(dq.begin(), dq.end());

        bool is_coupon = false;

        if (tmp.find(c) != tmp.end()) {
            is_coupon = false;
        }
        else {
            is_coupon = true;
        }

        if (maxx <= tmp.size()) {
            maxx = tmp.size();
            if (is_coupon) {
                maxx += 1;
            }
        }
    }
    cout << maxx;
    return 0;
}

하지만 시간초과라는 결과를 얻게 되었다. for 루프를 돌 때마다 새로운 set을 생성하고 탐색하는 과정에서 O(Nk) 의 시간이 걸린다.

수정된 인사이트

1. deque 을 이용한 윈도우
   -> unordered_map 을 사용
2. unodered_set 을 사용한 중복제거
   -> unordered_map에서 key(초밥번호) 에 해당하는 value 값의 조정을 통해 중복이면 1 초과인지 확인을 해 체크

정답코드

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

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

    int N, d, k, c;
    cin >> N >> d >> k >> c;

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

    unordered_map<int, int> sushi_count;
    int total_types = 0; // 현재 윈도우 내의 초밥 종류 수
    int max_types = 0;

    // 초기 윈도우 설정
    for (int i = 0; i < k; i++) {
        if (sushi_count[rail[i]]++ == 0) total_types++;
    }
    // 쿠폰 초밥 추가
    if (sushi_count[c]++ == 0) total_types++;

    max_types = total_types;

    // 슬라이딩 윈도우
    for (int i = 1; i < N; i++) {
        // 앞에서 초밥 제거
        if (--sushi_count[rail[i-1]] == 0) total_types--;

        // 뒤에 새로운 초밥 추가
        int new_sushi = rail[(i + k - 1) % N];
        if (sushi_count[new_sushi]++ == 0) total_types++;

        // 쿠폰 초밥 확인
        max_types = max(max_types, total_types + (sushi_count[c] == 0));
    }

    cout << max_types;

    return 0;
}

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

문제 설명

0으로 이루어진 바다위에 떠있는 1로 이루어진 섬.

섬끼리 다리를 지으려고 하는데 가장 짧은 다리를 구하자.

인사이트

섬들 중 어느 섬이든 간에 가장 짧은 다리를 만드는 경우를 출력하면 된다.

1. 전체 BFS 순회를 통해 몇 개의 섬이 있으며 지도에 있는 1이 몇번째 섬에 부분에 해당하는지 파악
2. 지도를 이중 for loop를 통해 지도 값이 1 인 칸에 대하여 주위 네 개의 면 중 0이 있다면 큐에 넣는다.
   1. 큐에 들어온 좌표를 기준으로 BFS 를 실행
   2. 주위 네 개의 면 중 하나가 0 이면 큐에 push
   3. 주위 네 개의 면 중 하나가 1 이고 다른 섬이면 정답 벡터의 담기
      1. 시작 좌표, 끝 좌표를 이용해 |끝좌표 - 시작좌표| - 1 값을 구해 최소 다리 길이를 구함
3. 이중 for loop 가 끝나면 정답 벡터의 최솟값을 출력

정답 코드

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

using namespace std;

int N, M;

int land[101][101];
int land_idx[101][101];
bool visited[101][101];
bool visited_idx[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<int> ans;
    cin >> N;
    //초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> land[i][j];
        }
    }

    //2차원 배열을 순회하면서 땅이 몇개인지 파악하고 각 행렬의 1이 속하는 땅의 번호를 기입
    int idx = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited_idx[i][j])continue;
            if (land[i][j] != 1)continue;
            queue<pair<int, int>> q;
            q.push(make_pair(i, j));
            visited_idx[i][j] = true;
            idx++;
            land_idx[i][j] = idx;

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

                q.pop();

                for (int k = 0; k < 4; k++) {
                    int ny = y + dy[k];
                    int nx = x + dx[k];
                    if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                    if (visited_idx[ny][nx])continue;
                    if (land[ny][nx] == 0)continue;
                    q.push(make_pair(ny, nx));
                    visited_idx[ny][nx] = true;
                    land_idx[ny][nx] = idx;
                }
            }
        }
    }


    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited[i][j])continue;
            if (land[i][j] != 1)continue;

            queue<pair<int, int>> q;
            //주변에 0이 있는 1인 시작점 찾아서 큐에 넣기
            bool check = false;
            for (int k = 0; k < 4; k++) {
                int ny = i + dy[k];
                int nx = j + dx[k];
                if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                if (land[ny][nx] == 0) {
                    if (land_idx[ny][nx] != land_idx[i][j])
                    {
                        check = true;
                    }
                }
                else {
                    continue;
                }
            }
            //4면 중 하나라도 0이면 큐에 담기
            if (check) {
                q.push(make_pair(i, j));
                visited[i][j] = true;
            } 
            //BFS
            while (!q.empty()) {
                int y = q.front().first;
                int x = q.front().second;

                q.pop();

                bool check = false;
                for (int k = 0; k < 4; k++) {
                    int ny = y + dy[k];
                    int nx = x + dx[k];
                    if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                    if (visited[ny][nx]) continue;
                    //4면 중 하나가 0 이면 큐에 푸시
                    if (land[ny][nx] == 0) {
                        if (land_idx[ny][nx] != land_idx[i][j])
                        {
                            q.push(make_pair(ny, nx));
                            visited[ny][nx] = true;
                        }
                    //4면 중 하나가 1이면 정답 벡터에 푸시
                    }else if (land[ny][nx] == 1) {
                        if (land_idx[ny][nx] != land_idx[i][j]) {
                            ans.push_back(abs(ny - i) - 1 + abs(nx - j));
                            break;
                        }
                    }

                }
            }
            //재탐색을 위한 방문 초기화
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(land[i][j] == 0)visited[i][j] = 0;
                }
            }

        }
    }

    cout << *min_element(ans.begin(), ans.end());
}

www.acmicpc.net/problem/1546

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

using namespace std;

int main(void) {
	double T,i;
	double num, max;
	double sum = 0.0;
	cin >> T;
	vector<double> mean;
	for (i = 0;i < T;i++) {
		cin >> num;
		mean.push_back(num);
		
	}
	max = *max_element(mean.begin(), mean.end());
	//cout << max << '\n';
	for (i = 0;i < T;i++) {
			mean[i] = mean[i] / max * 100;
	}
	for (i = 0;i < T;i++) {
		sum += mean[i];
	}
	cout << sum / T;
	return 0;
}

처음에는 되게 쉽다고 시작했는데

중간에 이상한 코드를 하나 짜서 나의 능지에 의심을 품었지만 찾아버리고 말았다.

하지만 브론즈 1문제 였고..

아직 갈길이 멀다.

얼른 실버 찍어야징

www.acmicpc.net/problem/1003

처음으로 풀어본 DP 문제

가끔 에브리타임 보면 DP 가 그렇게 어렵다고 하던데 도통 무슨 말인지 몰랐다.근데 오늘 알고리즘 수업을 듣고 한 번 복습 겸 문제를 풀어보았다.DP(Dynamic Programming) 즉, 동적 프로그래밍우리 교수님은 동적 프로그래밍이라는 말을 별로 달가워 하시지 않더라 ㅋㅋ

여튼 흔히 아는 피보나치 수열을 재귀함수로 표현하면 0.25 초내로 풀지 못한다.DP 배열을 선언해서 점화식 형태로 만들어 풀어주었다.처음에는 이상하게 만들어서 원하는 결과가 나오지 않았는데샤워하다가 영감이 떠올라 바로 작성했더니 실행이 되어 기분이 좋았다.

오늘 경험한 바에 따르면 DP 는 점화식 구현 같은 기분이 든다.아닐수도 있고 ^^백준을 이용하면서 랭킹 욕심에 하지도 않던 알고리즘 공부를 시작해 감회가 새롭다.랭킹시스템 덕분인 것 같다. 우리학교에서 짱먹고싶다.

#include <iostream>
using namespace std;

int dp[10000][2];
int fibo(int a) {
	dp[0][0] = 1;
	dp[0][1] = 0;
	dp[1][0] = 0;
	dp[1][1] = 1;
	if (a == 0) {
		return 0;
	}
	else if (a == 1) {
		return 0;
	}
	else {
		for (int i = 2; i <= a; i++) {
			dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
			dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
		}
	}
	return dp[a][0], dp[a][1];
}
int main(void) {
	int T;
	cin >> T;
	for (int i = 0;i < T;i++) {
		int N;
		cin >> N;
		fibo(N);
		cout << dp[N][0] << " " << dp[N][1] << '\n';
	}
	
	return 0;
}

dp[i][0], dp[i][1] 을 따로 선언해 초깃값을 선언하고 0이 나오는 횟수, 1이 나오는 횟수를 나누어 리턴했다.