안 쓰던 블로그

처음 접근 방법 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/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..

스택이란 ‘쌓아올린 더미’를 말합니다. 책을 쌓아서 탑을 만들면 스택이고, 편의점 냉장고에 캔음료수가 일렬로 줄 서 있는 것도 스택입니다. 이렇듯 스택은 마지막으로 들어온 것부터 나가는 특징을 가지고 있습니다. 책 탑에서 맨 아래 책을 빼면 무너지고, 편의점에서 음료수를 앞에서부터 빼지 못 하는 점을 생각하면 됩니다. 그런 현실의 개념을 추상화한 것이 바로 스택입니다. 스택을 가지고 주로 삽입, 삭제, 검색 작업을 하는데, 스택의 특징에 따라 가장 최근에 들어온 데이터를 빼고, 아니면 그 뒤에 새로운 데이터를 넣게 됩니다. 스택의 특징을 영어로는 LIFO(Last In First Out), 한자로는 후입선출이라 합니다. 여기서 중요한 건, 편의점의 캔음료를 중간에 있는 것부터 뺄 수 없듯 이 스택에서도 ..