안 쓰던 블로그

처음 접근 방법 1. goal에서부터 1로 이어진 간선들을 따라 거꾸로 이동하며 time의 합을 구한다 2. 1에 도착하면 합을 리턴한다 3. 1~2번 과정을 goal에 연결된 모든 간선에다가 하고 리턴된 합 중에 max값을 출력 그래서 처음에 그래프에 간선을 거꾸로 넣었고 ( v[b].push_back(a); ) go함수에서도 거꾸로 재귀가 돌았다 한 가지 의문인 점이 있었는데, 처음에 함수를 int형으로 만들어서 sum매개변수에 연산 후 return sum으로 했다 그러니까 아래 코드 기준으로 하면 int go(int now, int sum) { 연산 종료 조건 시 return sum; 아니면 재귀 } 이런 식이었음 근데 분명 재귀도는 함수의 종료 조건 if문 걸려 들어가서 return하기 직전 즉,..

위상 정렬: 비 순환 방향 그래프에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 것 그래프에서 반드시 자신보다 선행되어야 할 일을 다 끝내야만 작업에 들어갈 수 있는 조건이 주어질 때 사용한다 수행 과정 1. 자기 자신을 가리키는 간선이 없는 정점을 찾아서 큐에 넣음(in-degree가 0인 정점) 2. 큐에서 정점 하나를 출력하고 그 정점에서 출발하는 간선 전부 삭제(간선-=1), 정점도 삭제(pop) 3. 간선을 삭제하다가 간선이 없는 정점이 생기면 큐에 넣음 4. 아직 그래프에 정점이 남아있으면 1번으로 돌아가고, 아니면 종료 #include #include #include using namespace std; int cnt[32001]; //자신에게 들어오는 간선 개수 int main() ..

print(chr(int(input())+44031)) print(ord(input())-44031)

first=["ㄱ", "ㄲ", "ㄴ", "ㄷ", "ㄸ", "ㄹ", "ㅁ", "ㅂ", "ㅃ", "ㅅ", "ㅆ", "ㅇ", "ㅈ", "ㅉ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ"] second=["ㅏ", "ㅐ", "ㅑ", "ㅒ", "ㅓ", "ㅔ", "ㅕ", "ㅖ", "ㅗ", "ㅘ", "ㅙ", "ㅚ", "ㅛ", "ㅜ", "ㅝ", "ㅞ", "ㅟ", "ㅠ", "ㅡ", "ㅢ", "ㅣ"] third=["", "ㄱ", "ㄲ", "ㄳ", "ㄴ", "ㄵ", "ㄶ", "ㄷ", "ㄹ", "ㄺ", "ㄻ", "ㄼ", "ㄽ", "ㄾ", "ㄿ", "ㅀ", "ㅁ", "ㅂ", "ㅄ", "ㅅ", "ㅆ", "ㅇ", "ㅈ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ" ] n=ord(input())-44032 print(first[n//..

www.acmicpc.net/problem/12995 트리나라는 n개의 도시로 이루어져 있고 각 도시 1~n은 모두 연결되어 있다 직원 k명이 전부 이사를 가야 하는데 모든 직원이 서로 다른 도시로 가야 해서 k개의 이사할 도시를 정해야 한다 k개의 도시는 모두 연결되어 있어야 한다 이사할 도시 k개를 고르는 방법의 수를 구하는 문제 k개 도시를 골라야 하면서 전부 연결되어 있어야 하니 다른 트리에서의 dp문제였던 트리의 독립집합이나 사회망 서비스와는 비슷하지만 다른 접근이 필요했다 예를 들어 k=15라고 하면 a, b서브트리에 13을 주고 c서브트리에 2를 줄 수도 있고 a에 2를 주고 b에 12를 주고 c에 1을 주는 방법도 있는 등 다양한 방법이 나올 수 있는데 이걸 어떻게 구현하느냐에 대한 문제였..

www.acmicpc.net/problem/2533 트리의 독립집합 foxtrotin.tistory.com/334 과 유사한 문제 얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 아이디어를 받아들인다 모든 사람이 새로운 아이디어를 수용하기 위해 필요한 최소 얼리 아답터의 수를 구하는 문제 친구 관계가 트리이기 때문에 트리에서의 다이나믹 프로그래밍을 할 수 있다 얼리 아답터는 주변 사람에게 영향을 준다. 즉, 얼리 아답터 둘이 붙어 있으면 비효율적이므로 떨어져 있어야 한다 이 말은 어떤 정점이 얼리 아답터라면 그 자식들은 전부 얼리 아답터가 아니라는 의미이기도 하다 하지만 어떤 정점이 얼리 아답터가 아니라면, 그 자식들은 얼리 아답터일 수도, 아닐 수도 있다(적어도 1명은 얼리 아답터..

www.acmicpc.net/problem/2213 독립집합: 서로 간선으로 연결되어 있지 않은 정점들의 집합 체크 표시한 정점들의 집합은 독립집합이다 각 정점에는 가중치가 있어서 가중치의 합이 최대가 되는 트리의 독립집합을 구하는 문제 문제에 핵심은, 어떤 정점이 독립집합에 포함되어 있다면 그 자식은 포함되지 않아야 한다 예를 들어 위에서 2가 독립집합이라면 바로 아래 자식 2, 7은 포함되면 안 된다 2가 독립집합이 아니라면 2, 6은 독립집합에 포함되어도 되고, 안 되어도 된다 트리의 독립집합은 DP로 풀 수 있다 D[v][0] : 정점 v가 독립집합에 포함되지 않은 경우 최댓값 D[v][1] : 정점 v가 독립집합에 포함된 경우에 최댓값 이 두 경우를 구하면 v를 루트로 하는 서브 트리의 독립집합..