데옴's 기록장

오랜만에 푼 재밌는 골드 그리디 문제였다.쉬운 문제여서 정신적 건강에 많이 도움이 되었다. 문제에 정점이 N개, 루트노드가 1인 트리가 주어진다.각 노드에는 가중치가 있고 i(1모든 리프노드는 자신의 부모노드보다 가중치의 크기가 작거나 같기 때문에 루트노드에서 인접한 노드들을 선택하는 상황이 가장 큰 이득을 볼 수 있게 만들 수 있다. 즉, 루트노드를 우선순위큐에 넣고, 그 루트노드에 연결된 노드들을 우선순위큐에 넣으면서 계속 관리하면 각 상황마다 얻을 수 있는 가치의 크기가 최대가 된다.  사실 그리디라기보다는 bfs에 가까운 문제였다.

그냥 문제가 너무 길다. 문제를 요약하자면 모든 정점들이 어느 한 정점으로 연결되어 있는 트리가 있고 두가지 쿼리가 주어진다. 1. 두 정점의 간선을 끊는다 2. 선택한 정점과 연결된 정점들의 개수를 센다. 일반적인 방법으로는 문제를 해결하기에는 어려워보인다. 1번 쿼리는 n-1개 들어오기 때문에 최종 상태에서는 모든 정점들이 서로 연결되어 있지 않음을 알 수 있다. 그러면 여기서 쿼리를 거꾸로 수행해보고 싶은 생각이 들 수 있다. 간선을 끊는 쿼리를 구현하는 것은 어려우므로 쿼리를 거꾸로 실행하게 되면 간선을 추가하는 쿼리로 바뀌게 된다! 여기서 바로 유니온 파인드를 사용할 수 있다. 1번 쿼리가 들어오면 두 정점을 유니온 하고 2번 쿼리가 들어오면 연결된 정점들의 개수를 세어주기만 하면 된다. 정점들..

디미고에 와서 1순위 목표는 해킹을 배우는 것이었다. 나는 선배들의 추천으로 리버싱을 해보게 되었고 리버싱을 가볍게 공부한 후 기초문제들을 풀어보았다. 처음에는 막막했는데 친구랑 같이 그냥 머리박고 하니까 잘 풀리더라ㅋㅋ rev-basic 0 그냥 ida로 디컴파일 하면 바로 플래그를 준다. rev-basic 1,2 함수 안에 보이는 문자들을 나열하면 플래그를 얻을 수 있다. rev-basic 3,4,5,6,7,8 함수안에서 암호화?가 이루어지는 것 같다. 이걸 잘 분석해서 역연산을 하는 방법도 있지만 n의 범위가 매우 작기 때문에 그냥 브루트포싱을 해도 된다. 나는 3~8의 모든 문제를 브루트포스로 해결했다. 사실 이 문제들은 그냥 알고리즘적인 사고가 어느정도 된다면 매우 쉽게 풀 수 있었다. 앞으로 ..