안 쓰던 블로그

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를 루트로 하는 서브 트리의 독립집합..

1. cin, cout, endl 사용금지(느림) printf, scanf, \n사용 이런 식으로 언어마다 사용하면 좋은 입출력 함수가 있어서 자기 언어 관련으로 백준 입출력 팁을 구글에 검색해서 보면 도움이 될 것 같아요 2. for문 줄이기 특히 중첩 for문 3. 끝나지 않는 while(1) 1. 비주얼 스튜디오, vs code등의 컴파일러나 ideone등의 웹 컴파일러에서 미리 코드 실행!!! 코드 실행으로 컴파일 에러는 대부분 해결!! 2. 백준에서 알려주는 에러 메시지를 잘 확인 3. 문법 에러 4. 함수에 적당한 헤더를 가져왔는지 확인하기. 원래는 안 되는 코드인데 컴파일러에서 임의로 돌게 해 주는 것들도 있음 예: #include 에서 strlen 함수를 쓰지 마세요 strlen은 stri..

www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 처음 풀이-dp #include #include #include using namespace std; int dp[100001], coin[2] = { 2,5 }, n; int f(int v) { if (v 0) return dp[v]; int res = 1e9; for (int i = 0; i < 2; i++) { res = min(res, f(v - coin[i]) + 1); dp[v] = res; } return res; } int m..

www.acmicpc.net/problem/15721 1) 뻔 – 데기 – 뻔 – 데기 – 뻔 – 뻔 – 데기 – 데기 뻔 – 데기 – 뻔 - 데기 – 뻔 – 뻔 – 뻔 – 데기 – 데기 – 데기 뻔 – 데기 – 뻔 - 데기 – 뻔 – 뻔 – 뻔 - 뻔 – 데기 – 데기 – 데기 - 데기 ... 한 바퀴 돌 때마다 이런 식으로 뻔과 데기가 늘어난다 2) 만약 사람이 7명이고 16번째 뻔을 말한 사람을 구하려면 입력은 7 16 0이고 뻔 데기 뻔 데기 뻔 뻔 데기 데기 뻔 데기 뻔 데기 뻔 뻔 뻔 데기 데기 데기 뻔 데기 뻔 데기 뻔 뻔 뻔 뻔 데기 데기 데기 데기 뻔 이니까 2번째 사람이 16번째 뻔을 말했으니 2를 출력한다 사람은 0부터 센다 3) 사람이 1명일 수도 있다 1명이면 혼자서 뻔 데기를 다..