전체 글108 [BOJ] 백준 15892번: 사탕 줍는 로봇 https://www.acmicpc.net/problem/15892 15892번: 사탕 줍는 로봇 첫 번째 줄에 성원이네 집안에 있는 방의 개수를 나타내는 자연수 n(2 ≤ n ≤ 300)과 복도의 개수를 나타내는 자연수 m(1 ≤ m ≤ 5,000)이 공백으로 구분되어 주어진다. 두 번째 줄부터 m개의 줄에 �� www.acmicpc.net 사탕의 개수를 노드 간 연결된 간선의 용량으로 생각하면 네트워크 플로우 (최대 유량)으로 쉽게 풀 수 있음. 네트워크 플로우의 개념은 BFS로 시작->도착점 경로의 최소 유량 flow를 탐색하여 u->v 유량에 더해주고 역방향 v->u 유량에서 빼서 더이상 유량을 흘려보낼 수 없을 때 까지 반복합니다. 주의할 점은, 이 문제는 양방향이라 실수할 확률이 낮지만 단방향.. 2020. 7. 20. [BOJ] 백준 2150번: Strongly Connected Component https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 강한 연결 요소 (SCC, Strongly Connected Component) 알고리즘은, v에서 u로가는 경로가 있을 때, 반대로 u에서 v로 갈 수 있는 경로가 존재하는 최대의 그룹 크기를 찾는 알고리즘입니다. 코사라주 알고리즘과 타잔 알고리즘으로 강한 연결 요소를 찾을 수 있는데, 본 포스팅에서는 코사라주 알고리즘에 대하.. 2020. 7. 17. [BOJ] 백준 1071번: 소트 제 코드를 그대로 복사해서 제출하신 분들이 있어서 정답코드를 지웁니다. 아래는 제 코드를 그대로 복사해서 제출한 목록입니다. 주석도 안지우고 그대로 제출하셨네요.. 메모리 1984, 시간 0, 코드길이 1349 채점번호 21290911 (비공개), 22023209 https://www.acmicpc.net/problem/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 이웃한 두 수가 연속되지 않는 (a[i] + 1 != a[i+1]) 인 사전순으로 가장 앞선 순열을 찾는문제. 주어진 입력을 정렬 후,.. 2020. 7. 16. [BOJ] 백준 3176번: 도로 네트워크 백준문제 3176번: 도로 네트워크 문제 N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. 총 K www.acmicpc.net 이번 포스팅은 LCA와 LCA에서의 노드간 가중치, 특성 등을 다루는 방법을 논의한다. LCA는 공통 부모노드를 찾는 알고리즘으로 2^i 번째 부모노드만을 고려하여 ( i >= 0, 인 정수) 의 lgN 복잡도로 빠르게 수행 가능하다. 이때 두 노드를 잇는 경로에서 각 경로의 distance (cost)를 다루는 문제에서 j번째 노드부터 2^i번째 부모까지의 거리 요소를 dist[i][j]로 저장하면 역시 lgN의 복잡도로 다룰수있다. (LCA찾는 .. 2020. 7. 5. [ 0/1 Knapsack] 배낭 냅색 알고리즘 냅색 문제(Knapsack Problem)는 물건들의 무게 w와 가치 v가 주어지고 배낭의 용량 c가 주어질때 배낭에 넣은 물건들의 가치의 합이 최대 몇인지 구하는 문제입니다. 0/1 냅색은 물건을 쪼개어 담을 수 없는 문제입니다. 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 직관적으로 떠오르는 풀이는 특정 무게 _w에서 최대 가치의 합 dp[_w]을 구해가자! 입니다. i번째 물건의 무게와 가치를 각각 arr[i][0], arr[i][1]이.. 2020. 7. 3. [BOJ] 백준 2225번: 합분해 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 0~N까지 정수 K개를 더하여 N을 만드는 경우의 수를 구하는 문제입니다. 이를 식으로 나타내면 아래와 같습니다. 각 a의 값은 0 이상이므로 중복 순열의 식으로 구할 수 있습니다. #include #include #include #include #include #include #include #include #define MOD (1000000000) using namespace std; int n, m; int ncr[401][401] = { 0, }; int main() { ios_base::sync_with_stdi.. 2020. 6. 29. [BOJ] 백준 1005번: ACM Craft 문제 링크 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 예제 그림은 4번 건물을 짓기 위하여 2번과 3번 건물이 모두 지어져야 하고, 2번과 3번을 짓기 위하여 1번 건물이 지어져야 하는 경우를 보여준다. 이때 4번 건물을 짓기위해 걸리는 최소 시간은 1->3->4 를 짓는 시간인 120초가 걸리게 된다. 즉, i번 건물까지 짓는 시간은 자신의 상위 건물(j..) 들 중 가장 오래 걸리는 시간에 영향을 받는다. 동적 계획법을 사용하여 dp[i]를 i번째 것물을 짓는 최소 시간이라고 한다면 아래 식으.. 2020. 6. 29. [알고스팟] 합친 LIS ID: JLIS 2020/06/25 - [알고리즘] - 최장 증가 부분수열: LIS (Longest Increasing Sub-sequence) 최장 증가 부분수열: LIS (Longest Increasing Sub-sequence) LIS 길이는 꽤 단순하게 구할 수 있다. 10 20 10 30 20 50의 전체 수열이 있다면 먼저 10을 벡터에 넣는다 10 그 다음 수를 벡터의 마지막 수와 비교하여 1) 마지막 수보다 크다면 그대로 벡터에 삽입 10 2 seongjuk.tistory.com 이전 포스팅에서 LIS 알고리즘을 다뤘는데요, 이번에는 확장된 LIS인 두 배열에서 최장 증가 부분 수열을 뽑는 문제에 대해 다루려고 합니다. 문제 링크 algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열.. 2020. 6. 28. [알고스팟] 와일드카드 ID: WILDCARD 문제 링크 algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 algospot.com 와일드카드란 어떤 문자도 가능한 만능 문자로 *는 0글자 이상의 문자로 대체 가능하고, ?는 어떠한 문자 (1글자)로 대체될 수 있습니다. 예를 들어 b*a 는 bba, banana, ba와 같은 문자들로 대응될 수 있으며 b?a는 bba, baa, bca 로 대응 될 수 있지만 bbaa, ba와 같은 문자로 대응될 수 없습니다. 특정 와일드카드를 0개 이상 포함된 문자열이 주어지고, 대응 후보 문자열이 여러개 주어졌을 때, 대응될.. 2020. 6. 27. 이전 1 ··· 7 8 9 10 11 12 다음
