본문 바로가기

알고리즘90

그리디 1. 그리디로 항상 최적해를 구할 수 있다면, 그리디는 dp보다 훨씬 빠르다. (그리디로 풀리면 보통 dp로도 풀린다) 2. 시공간 제약으로 인해 최적해를 찾는 것이 극히 제한되는 경우, 근사해를 찾아준다. ps에선 1번 용도로만 사용된다. 근사해 찾기는 조합탐색이나 메타휴리스틱을 사용한다. 탐욕적 선택 속성(greedy choice property) : dp처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있는 속성 최적 부분 구조(optimal substructure) : dp처럼 부분 문제의 최적해에서 전체 문제의 최적해를 만들수 있는지 ->대부분 자명해서 증명할 필요가 없는 경우가 많다. 하지만 예외 존재 알고리즘이 위 두 속성을 만족하는지 검증해야 한다. 1. 활동.. 2019. 12. 18.
codeforces #604 div2 D - Beatiful Sequence (수학,발상) http://codeforces.com/contest/1265/problem/D - 댓글풀이 0,1,2,3이 각각 a,b,c,d번 나오는 숫자의 배열 a 를 만드는데 다음 조건을 만족해야 한다. 문제의 조건을 만족하기 위해선, 어떤 연속한 수도 같은 parity를 가질 수 없다. 따라서, 1. 배열의 크기가 홀수인 경우엔 cnt(even)와 cnt(odd)가 1 차이가 나야 한다. cnt(even)이 더 큰 경우 0과 2를 배열a의 홀수번 idx에 순서대로 배치하고, 1과 3을 배열 a의 짝수 idx에 순서대로 배치하면 된다. cnt(odd)가 더 큰 경우는 그 반대로 하면 된다. 2. 배열의 크기가 짝수일 경우엔 cnt(even)=cnt(odd) 1번처럼 하면 된다. 무엇을 먼저 배치할진 자유 그리고 .. 2019. 12. 7.
Educational round #72 div2 D - Coloring Edges (방향그래프 사이클) https://codeforces.com/contest/1217/problem/D (editorial 풀이) 방향그래프가 주어진다. 정점(n)과 간선(m)의 최대는 각각 5000이다. 각 간선에 최소한의 색(k)을 칠해서 같은 색의 간선끼리 cycle이 생기지 않도록 하는 k와 그때 간선의 색을 모두 출력하는 문제다. editorial의 설명 -> 간선 (u,v)가 back edge : if there is a path from v to u by edges from dfs tree 문제 풀땐 if there is a 'edge' from v to u by edges from dfs tree 로 생각하도록 하겠다. dfs tree를 그리고 back edge를 추가한 그래프를 떠올려보자. 다음은 1, 2 /.. 2019. 12. 5.
codeforces #603 div2 D - Secrete Passwords ( 이분매칭, disjoint set ) http://codeforces.com/contest/1263/problem/D editorial은 biparite graph 어쩌고로 풀던데, 나는 유파로 풀었다. 문자열이 최대 2e5개 들어온다. . i번째 문자열과 j번째 문자열이 단 한 개라도 같은 알파벳을 사용했다면 두 문자열은 equivalent다 . k번째와 i번째 문자열이 equivalent하고 k번째와 j번째 문자열이 equivalent하다면 i번째와 j번째는 equivalent다. 위 상황에서 컴포넌트의 수를 구하는 문제이다. 간선만 잘 깔아주면 된다. 하지만 n이 커서 단순히 모든 요소를 비교하는 식으로 간선을 이을 수 없다. bool s[MAX][26] = { 0 }; string 형으로 문자열을 입력받은 후, 위에 저장해 뒀다. (.. 2019. 12. 2.

티스토리툴바