기술 블로그

그리디(탐욕) 알고리즘이다. 이 코드에서 주의할 점은 25번 째 줄 코드 >가 아니라, >=이다. https://www.acmicpc.net/problem/5585 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include #include #include #include #include #include #include using namespace std; int Coin[6] = { 500, 100, 50, 10, 5, 1 }; int money = 0; int Search(){ int total = 1000 - money; int ret = 0; for (int i = ..

이분 매칭 문제이다. 1. 상어 1의 3가지와 상어 2의 3가지가 같을 때, 잘 처리해야 한다.2. 각각 2마리씩 먹을 수 있으므로, DFS를 2번 돌린다.3. 2번 돌릴 때에, 그 사이에 visit를 한 번 더 초기화 해줘야한다.(http://donggod.tistory.com/51 참고) https://www.acmicpc.net/problem/1671 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110..

C++ STL의 Map을 이용하면 된다. 자동 정렬해주기 때문이다. https://www.acmicpc.net/problem/11656 12345678910111213141516171819202122232425262728293031323334#include #include #include #include #include #include #include #include #include using namespace std; map dict; int main(void){ string s; cin >> s; int len = s.size(); for (int i = 0; i first.c_str()); } return 0;}Colored by Color Scriptercs

똑같은 문제 풀이 : http://hsdevelopment.tistory.com/90 https://www.acmicpc.net/problem/1167 84번 째 줄은 삭제해야 한다. 문제에서 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 문제에서 각 하나의 정점에 대한 정보들이 '차례대로 모두' 주어지므로, 굳이 84번 째 줄을 작성할 필요는 없다 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576..

처음에는 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 : 소..