국문과 유목민

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

리스마스 휴일을 끝내고, 다시 알고리즘 스터디의 일상으로 돌아왔다. 취준생이 무슨 휴일이냐고 하면 할 말이 없기는 한데 이렇게 쉬어 버린 것을 보니 아직 위기감이 덜한 걸지도...아무튼 잘 쉰 만큼 다시금 열심히 해야겠다. 그래프 이론에 관한 문제를 오랜만에 푸는데, find_parent나 union_parent와 같은 서로소 알고리즘의 기본적인 틀은 쉽게 이해할 수 있었다. 하지만 해당 알고리즘들을 이용해서 어떻게 묶을지 등에 대한 방법을 잘 몰랐었던 것 같다. 그래프 이론에 관한 문제를 풀다가 정답을 봤을 때, 아예 생각을 못한다거나 복잡한 코드가 아닌 경우가 많았다. 그런 점에서 아직 그래프 알고리즘을 활용하는 능력과 경험이 부족해서 그렇다는 생각이 들었다. 늘 얘기하는 거지만 생각을 확장시킬 필요..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 + a 1. 문제 설명 - 여행계획을 짜려고 하는데 나라들이 연결되어만 있으면 여행을 갈 수 있다. 나라들이 연결되어 있는 정보와 여행 일정에 대한 입력이 들어오면 해당 여행 일정이 가능한지 출력을 하는 문제 2. 접근 방식 - 그래프 알고리즘을 이용해서, 여행일정에 해당하는 노드들이 서로 연결되어 있는지 확인하면 된다. - 여행일정에 해당하는 노드들이 서로 연결되어 있다는 것은 하나의 집합(부모)에 묶여있다는 뜻이라고 생각할 수 있다. 3. 코드 n, m = map(int, input().split()) ls = [] for _ in r..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 1. 문제 설명 - 비행기는 도킹할 수 있는 탑승구가 정해져 있다. 하지만 탑승구에 도킹해있는 비행기가 있으면 다른 비행기는 도킹할 수 없다. 탑승구에 더 이상 도킹이 불가능할 때까지 비행기를 받고자 할 때, 최대로 받을 수 있는 비행기는 몇 대인가? 2. 접근 방식 - 서로소 집합 알고리즘을 활용해서 문제를 풀 수 있다. - 0번째 집합(parent[0])까지 만든다. 집합을 주어진 순서대로 앞선 원소와 묶어가다가 0번째 집합에 묶이면 반복을 종료한다. 3. 코드 def find_parent(parent, a): if parent[a] ..

1. 문제 설명 N개의 강의 중 선수 강의가 있을 경우 특정 강의가 주어졌을 때, 해당 강의를 듣기 위해서 걸리는 최소한의 시간을 구하는 문제 - 위상정렬을 이용하는 문제로 위상정렬 이론에서는 리턴하는 값이 순서였다면, 이번에는 cost이다. 하지만 알고리즘 상에서 큰 변경점은 없다. 단지, 시간의 정보를 담은 리스트 변수가 하나 필요하다. 또한, 초기 input값 처리 부분을 고려하면 될 것으로 보인다. 2. 코드 from collections import deque import copy n = int(input()) indegree = [0]*(n+1) graph= [[] for _ in range(n+1)] time = [0]* (n+1) # 방향 그래프의 간선 정보 입력 받기 for i in ra..

1. 문제 설명 마을을 2개로 나누려고 하는데 가장 효율적으로 나눌 수 있는 방법을 찾는 문제 - 핵심 아이디어는 전체 그래프에서 2개의 최소 신장 트리를 만들어야 한다. - 마을을 2개로 나누는 방법은 모든 그래프를 다 잇고난 이후 비용이 가장 큰 간선을 제거해주면 된다. - 정리하자면 크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 최소 신장 트리를 구성하는 간선 중 가장 비용이 큰 간선을 제거하는 것이다. 2. 코드 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(pare..