주소https://www.acmicpc.net/problem/2468 문제재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.6826232346673327253689527이제 위와 같은 지역에 ..

주소https://www.acmicpc.net/problem/14495 문제피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다.1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구해보자! 입력자연수 n(1 ≤ n ≤ 116)이 주어진다. 출력n번째 피보나치 비스무리한 수를 출력한다. 예제 입력 110 예제 출력 119 풀이dp 사용해서 풀면 된다.vector로 선언했더니 int 범위를 넘어가서 틀렸다.숫자가 클 것 같으면 long long으로 선언하는 것을 잊지 말자. 코드#include#includeusing nam..

주소https://www.acmicpc.net/problem/1929 문제M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 예제 입력 13 16예제 출력 13571113풀이에라토스테네스의 체 알고리즘을 사용하면 된다.vector 선언 후에 0, 1을 false 처리해주는 것을 잊지 말자. 코드#include#includeusing namespace std;int main(int argc, char** argv){ ios::sync_with_stdio(false); ..

문제 주소https://school.programmers.co.kr/learn/courses/30/lessons/150369  풀이https://school.programmers.co.kr/questions/43364못 풀어서 위의 게시물을 참고하였다. d와 p가 0이 될 때까지 while문을 반복하는 것이 핵심이다. 일단 d와 p에서 이렇게 뺀다. d -= deliveries[i]; p -= pickups[i]; 물류창고에 들르면 d와 p에 cap 만큼의 여유가 생긴다.그렇기 때문에 d와 p에 cap 만큼 더한 후에 count를 증가시켜 물류창고에 들른 횟수를 기록해준다. while (d  while문을 빠져나오면 answer에 i에서 물류창고 까지의 거리 * co..

문제 주소https://school.programmers.co.kr/learn/courses/30/lessons/258711 풀이새로 추가된 정점이 모든 그래프와 연결된다는 것과 그래프의 특성만 알면 쉽게 풀 수 있는 문제였다.새로 추가된 정점은 들어오는 간선이 없고 나가는 간선이 2개 이상이다. if (in[i].size() == 0 && out[i].size() > 1){ answer[0] = i; start_node = out[i]; } 8자 그래프의 중앙에 위치한 정점은 들어오는 간선이 2개, 나가는 간선이 2개이다. else if (in[i].size() >= 2 && out[i].size() >= 2){ ..

문제 주소https://school.programmers.co.kr/learn/courses/30/lessons/49191 풀이count를 그래프 입력하면서 갱신하는 것이 아니라 그래프를 다 입력한 후에 갱신하는 것이 핵심이었다.dfs 할 때 (현재 노드의 count += 이전 노드의 count) 이런 식으로 생각했었는데 그냥 count를 +1씩 해주면 되는 거였다. 코드#include #include #include using namespace std;void update_count(int index, vector>& graph, unordered_map& count, vector& visited){ visited[index] = true; for (auto e: graph[index..

문제 주소https://school.programmers.co.kr/learn/courses/30/lessons/49189 풀이단방향 간선이 아니라 양방향 간선으로 unordered_map에 입력해야 한다!단방향 간선으로 입력해서 다 틀린 거였다....그 다음은 그냥 다익스트라 최단 거리 알고리즘 사용한 후에 가장 먼 노드의 개수 구하면 된다. 코드#include #include #include #include #include using namespace std;#define INF 1e9int solution(int n, vector> edge) { int answer = 0; // 이어진 노드를 기록 unordered_map> m; for (auto e : edge..

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42861문제 설명코드 전문#include #include #include using namespace std;int get_parent(int i, vector& parent){ if (parent[i] == i) return i; return parent[i] = get_parent(parent[i], parent);}void union_parent(int a, int b, vector& parent){ int a_parent = get_parent(a, parent); int b_parent = get_parent(b, parent); if (a_pare..

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42860문제 설명코드 전문#include #include #include using namespace std;int solution(string name) { int answer = 0; int length = name.length(); int move = length - 1; for (int i = 0; i 풀이며칠 간 못 풀어서 질문하기에 있는 풀이를 봤다.https://school.programmers.co.kr/questions/76244 move는 오른쪽, 왼쪽 이동 횟수만 저장한다.오른쪽으로만 진행했을 때 이동 횟수는 최대가 된다. 최댓값으로 초기화 해준다.i..