백준 (7) 썸네일형 리스트형 [BOJ] 2565 전깃줄/Dynamic Programming/이분 탐색/최장 증가 부분 수열(LIS)/C++ 풀이 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 문제에서 제시해준 예제를 통해 풀이를 생각했다. 위 처럼 전깃줄 개수가 처음에 주어지고 그 다음 (시작 전봇대 위치 - 끝 전봇대 위치)들이 주어진다. 시작 위치 기준으로 정렬한다면 다음과 같이 된다. 이 때 문제의 예시의 답에서 알려준 끝 전봇대 위치가 1, 8, 9인 전깃줄을 제외하고 관찰해보면 흥미로운 특징이 보인다. 바로 2, 4, 6, 7, 10은 증가하는 수열이라는 것이다. 시작 전.. [BOJ] 포도주 시식 / Dynamic programming https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net C++ 풀이 코드 #include #include #define MAX_N (10000) using namespace std; int N; int wines[MAX_N + 1]; int dp[MAX_N + 1]; int answer; void solve() { cin >> N; for (int i = 1; i > wines[i]; } if (N == 1) { cout [프로그래머스] 스킬트리 / C++ 풀이 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/49993 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 #include #include using namespace std; bool isMatchedFromFront(string skill, string order) { for(int i = 0; i < order.length(); ++i) { if(skill[i] != order[i]) { return false; } } return true; } int solution(string.. [프로그래머스] N개의 최소공배수 / 정수론 / 유클리드 호제법 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12953 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr C++ 풀이 #include #include using namespace std; int getGCD(const int a, const int b) { if(b == 0) { return a; } return getGCD(b, a%b); } int solution(vector arr) { int answer = 1; for(const auto& n : arr) { int gcd = ge.. [백준] 1753 최단경로 / 다익스트라 알고리즘 / C++ 풀이 문제 링크 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 전략 '시작점에서 다른 모든 정점으로의 최단 경로'를 구하라고 한다. 다익스트라 알고리즘을 사용하면 특정 시작 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있다. 따라서 다익스트라 알고리즘으로 접근한다. C++ 풀이 /* https://www.acmicpc.net/problem/1753 */ #include #include #include.. [프로그래머스] 선입 선출 스케줄링 / 이분탐색, binary search / C++ 풀이 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12920 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전략 각 코어가 작업을 받을 수 있는 시각인지 확인하며 n개를 처리할 때까지 반복문을 돌리면 시간 초과가 난다. 일의 개수는 최대 50,000이고 코어의 수는 최대 10,000 개다. 최악의 경우 5억( = 50,000 * 10,000)회의 반복문이 돌기 때문에 효율성 테스트를 통과할 수 없다. 따라서 더 효율적인 방법을 생각해야 한다. 문제에서 '한 코어에서 작업이 끝나면 작업이.. [백준] 2468 안전 영역 / BFS, 깊이 우선 탐색 문제 링크 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 전략 가능한 모든 수위에 대해 물에 잠기는 지점과 안전한 지점을 표시한다. 서로 연결된 안전한 지점을 BFS를 통해 찾는다. BFS가 호출된 수가 안전 영역의 개수이다. 코드 #include #include #include using namespace std; int board[101][101]; int land[101][101]; //-1 : 침수, 1 : 안전지역 int N; int .. 이전 1 다음
