국문과 유목민

드디어 이코테의 80~90%정도의 문제를 풀었다. 오늘은 그래프 이론 2문제를 풀었는데, 크루스칼 알고리즘을 활용한 문제와 위상정렬 알고리즘을 활용한 문제였다. 두 문제 다 순전히 내 힘으로 풀지 못했던 것 같아 내심 아쉽다. 다시 한 번 풀면서 문제를 익힐 시간이 필요할 것 같다. 그래도 이런 문제들을 풀면서 문제들을 푸는 기법들을 배우고 있는 것 같아 뭔가 성장하는 것 같은 느낌이 든다. 역시 아무것도 안 하는 것보다 뭐라도 하는게 나은 건 당연한 것 같다. 내일부터는 이코테 기출문제들을 풀면서 시간이나 난이도 등 때문에 넘겼던 문제들을 마저 푸는 시간을 가질 생각이다. 난이도가 높다보니 순전히 내 힘으로 풀겠다라는 객기어린 생각은 없기 때문에 최대한 생각을 하면서도, 내심 금방 해답을 볼 거 같기는..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 + a 1. 문제 설명 - 3차원의 행성의 좌표가 주어지며, 각 행성을 연결하는 도로를 최소한의 비용으로 짓고자 한다. 이때 각 행성을 연결할 수 있는 최소 비용은 얼마인지를 묻는 문제 2. 접근 방식 - 각 행성의 좌표를 X축, Y축, Z축끼리만 따로 계산한다. - 그리고 각 행성의 거리에 대한 계산 정보를 X, Y, Z축 모두 계산해서 하나의 리스트에 넣고 정렬을 수행한다. - 각 거리에 대한 계산정보가 담긴 리스트를 돌면서 사이클이 발생하지 않을 때만 집합 연산을 수행한다. (이렇게 하면 X, Y, Z축 우선 순위에 상관없이 비용이 ..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 1. 문제 설명 - 마을에 설치되어 있는 가로수를 줄여서 비용을 줄이려고 한다. 가로수를 줄였을 때 절약할 수 있는 금액의 최대를 출력하는 문제 2. 접근 방식 - 최소비용으로 모든 노드를 연결하는 문제(크루스칼 알고리즘) - 추후 간선의 길이가 길어질 것을 대비해 heapq를 활용해서 구해봤다. 3. 코드 def find_parent(parent, a): if parent[a] != a: parent[a] = find_parent(parent, parent[a]) return parent[a] def union_parent(parent,..