안 쓰던 블로그

신년맞이 작심20일 boj 챌린지 -하루에 정해진 분량만큼 문제 풀이(계획서 참고) -각 문제별 간단 해결 방법+깃헙 링크 블로그 정리 1991 트리 순회 전: 루트->왼->오 중: 왼->루트->오 후: 왼->오->루트 전: 출력->왼 탐색->오 탐색 중: 왼 탐색->출력->오 탐색 후: 왼 탐색->오 탐색->출력 탐색은 어차피 같으므로 출력만 나누면 한 번에 한 함수에 때려넣을 수 있다 github.com/proqk/Algorithm/blob/master/Tree/1991%20%ED%8A%B8%EB%A6%AC%EC%88%9C%ED%9A%8C(3).cpp 2250 트리의 높이와 너비 1. 트리 만들기 2. 중위순회 돌면서 몇 번 노드가 몇 번째 레벨에 있는지 저장 3. 2번을 하면서 레벨마다 최소, 최대..

www.acmicpc.net/problem/6603 n개 중에 6개를 뽑는 모든 경우의 수 구하기 몇개를 뽑는지 정해져 있다면 순열을 이용할 수 있다 뽑는 6개에 대해 1이라고 하고, n-6에 대해 0이라고 한 순열을 만들고 모든 순열을 돌면서 1인 경우의 값을 출력한다 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; while (1) { cin >> n; vector a(n), d; if (n == 0) break; for (int i = 0; i > a[i]; for (int i = 0; i < n - 6; i++) d.pu..

순열 next_permutation()과 prev_permutation() 직접 구현하기 다음 순열, 이전 순열, 모든 순열 순열 크기 n이 3인 수열을 사전순으로 나열하면 다음과 같다 123 132 213 231 312 321 n=3인 수열은 총 6개가 있다 여기서 먼저 알 수 있는 사실은 크기가 n인 순열을 총 n!개 존재한다는 것이다 첫 번째 오는 수를 n가지 중에서 선택, 그 다음 수를 n-1가지 중에서 선택, 그 다다음 수를 n-2가지 중에서 선택..을 반복하기 때문에 총 가지 수는 n*(n-1)*(n-2)*...*2*1 즉, n!이다 또 알 수 있는 사실은 첫 순열은 오름차순, 마지막 순열은 내림차순이라는 것이다 그러므로 중간 순열을 구하고 싶다면 첫 순열에서 다음, 다음, 다음으로 넘어가서 ..

합이 n이고 길이가 최소 l인 연속된 수열을 구하는 문제 합이 n인 연속된 수열을 $x+(x+1)+(x+2)...(x+L-1)$ 로 두고 x에 대한 식으로 바꾸면 위에 풀이처럼 된다 l이 100까지라고 했으니까 l~100 사이에서 조건에 맞는 x를 찾으면 끝 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long n; int l, res = -1, index = 0; cin >> n >> l; for (int i = l; i = 0) { //나눠 떨어지고, 길이가 맞으면 찾음 res = (n - k) / i; index = i; break; } } if (re..

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