기술 블로그

처음에는 BFS를 1 ~ 정점 끝까지 다 돌면서, 최댓값을 구하려고 했으나 생각해보니 너무 비효율적이었다. 그래서 다른 분의 글을 보았는데, 요약하자면 트리의 지름은 우선 아무 정점(여기에서 나는 편하게 root 노드로 잡았다.)에서 출발하여 가장 먼 곳에 있는 정점을 찾는다. 찾은 이 정점은 트리의 지름에 해당하는 두 정점 중 하나이다. 그러므로, 이 정점에서 다시 가장 먼 곳에 있는 정점을 찾으면 이 두 개의 정점이 트리의 지름에 해당한다. 이 문제는 '가중치'를 활용한 문제이다. 내가 참고한 글 2개1. http://blog.sisobus.com/2013/10/backjoon-online-judge-no1967.html#.W7BSDWgzZPZ2. http://blog.myungwoo.kr/112 h..

뭔가 살짝 노가다(?)로 구현한 것 같다. 다른 분들은 행렬로 구현 하셨는데, 나중에 행렬로 구현 해봐야겠다. 순회할 때, '중앙'이 기준이다. 그리고, 항상 왼쪽이 오른쪽보다 먼저 나온다. 전위 순회 : 중왼오중위 순회 : 왼중오후위 순회 : 왼오중 https://www.acmicpc.net/problem/1991 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091..

이분 매칭 문제이다. 81번 째 줄을 조심하자. https://www.acmicpc.net/problem/11375 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include #include #include #include #include #include #include #include using namespace std; #define MAX 1000 int Connection[MAX][MAX] = { -1, }; int work[MAX] = ..

기본적인 이분 매칭이다. 조금 더 이분 매칭을 활용할 수 있도록, 관련 알고리즘 문제들을 많이 풀어봐야겠다. https://www.acmicpc.net/problem/2188 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#include #include #include #include #include #include #include #include using namespace std; #define MAX 200 int N = 0, M = 0; // N : 소..

N과 M(1) 코드에서 살짝만 추가해주면 된다. 출력 부분에서 vc vector가 오름차순인지 아닌지 검사하면 된다.(21 ~ 24번 째 코드) N과 M(1) : http://hsdevelopment.tistory.com/31 문제 : https://www.acmicpc.net/problem/15650 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include #include #include #include #include #include #include #include using namespace std; bool used[9] = { false, ..

문제 저작권상 간략하게 올린다. (0, 0)에서 출발하여 (7, 7)로 도달할 수 있는가?단, 0은 벽, 1은 좌우 이동 가능, 2는 상하 이동 가능, 3은 상우 이동 가능, 4는 좌하 이동 가능이다. ※ 알게된 것2차원 격자에서 두 방향으로만 이동 가능한 이런 문제는 DFS/BFS를 굳이 안 써도, 대부분 반복문만으로 해결 가능하다. (물론 우회나 퇴보는 불가능) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include #include #include #include #include #include #include #i..

소수 문제이다. 에라토스테네스의 체를 활용한 문제이다. 문제 : https://www.acmicpc.net/problem/4948 에라토스테네스의 체 : http://hsdevelopment.tistory.com/78 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include #include #include #include #include #include using namespace std; #define MAX 2 * 123456 + 1 bool prime[MAX] = { true, }; void primeNumber() // 소수..

C언어로 구현하고 싶어서 처음에는 C언어로 구현하였었는데,시간 초과가 떴다. 분명 로직상 오류가 없었던 것 같아서, C++로 구현하였더니, 바로 통과가 떴다. 아마 C언어로 구현한 퀵 정렬에서 시간을 많이 소비해서 그런 듯 하다. right, left 위치 찾아가는 부분 때문인 듯 하다. https://www.acmicpc.net/problem/11652 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include #include #include #include #include #include using namespace std; ..