[ 이것이 코딩테스트다 ] 30일차

✏️ 서론

오늘은 part 2 - 주요 알고리즘 이론과 실전 문제 중 3문제만을 남겨두고 있다.

문제를 풀고 30일간 알고리즘공부를 하면서 어땠는지 소감을 간략하게나마 작성했다.

---

✏️ 본론

⚡️ [ 문제 1 ] 팀 결성

팀 결성 문제는 전형적인 서로소 집합 알고리즘 문제인데, 보자마자 서로소를 이용해야해! 라는 생각이 들었다.

문제 중

1. 팀 합치기 연산은 두 팀을 합치는 연산이다.
2. 같은 팀 여부 확인 연산은 특정한 두 학생이 같은 팀에 속하는지 확인하는 연산이다.

여기서 팀을 숫자로 바꾸고 생각하면 편하다.
두 팀을 합치는 연산은 union_parent로 parent 수를 비교하면되고, 같은 팀 여부 확인 연산은 find_parent 함수로 a와 b가 동일한지 확인하면 된다.

다만, 입력조건에 0은 팀 합치기, 1은 같은 팀 여부확인인데 if문에 0은 안쓰고 1만썼더니 원하는 값이 출력하지 않았다. if = 0, if = 1을 붙여주도록 하자.

'''
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1
'''
import sys

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n, m = map(int, input().split())
parent = [0] * (n+1)

for i in range(1, n+1):
    parent[i] = i

for i in range(m):
    check, a, b = map(int, input().split())
    if check == 0:
        union_parent(parent, a, b)
    if check == 1:
        if find_parent(parent, a) == find_parent(parent, b):
            print('YES')
        else:
            print('NO')
👉🏽 No No Yes

---

⚡️ [ 문제 2 ] 백준 1647 - 도시 분할 계획

문제

핵심 아이디어는 전체 그래프에서 2개의 최소 신장 트리를 만들어야한다.

문제에서 마을을 2개로 분할할 계획을 세우고 있다고 했다. 마을을 2개로 분리하기전에 최소 신장트리(크루스칼)를 이용하면 최소값이 나온다.

트리 자료구조는 노드가 N개일 때 항상 간선의 개수는 N-1이다.

여기서 임의의 간선 한 개를 더 잘라도 1개의 집은 마을이 되고, 최소 신장트리는 만족한다.

문제에서 길을 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다고 적혀있는데 이는 가장 유지비가 많이 드는 길을 끊으면 다음 유지비가 최소가 된다는말과 동일하다.

import sys
input = sys.stdin.readline

'''
7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4
'''

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    else:
        return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())
parent = [0] * (v+1)
edges = []
result = 0
max_value = 0

for i in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

for i in range(1, v+1):
    parent[i] = i

edges.sort()

for edge in edges:
    cost, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result = result + cost
        max_value = cost
print(result - max_value)
👉🏽 8

---

⚡️ [ 문제 3 ] 백준 9372 - 상근이의 여행

문제

훌륭한 낚시문제 😅 😅
최소 신장트리를 완벽하게 이해하지 못해 어렵게 풀려고만 했다. (혼자서 끙끙대다 2시간 넘은건 비밀)

최소신장트리 방법으로 풀면 되고, 간선에 비용이 없기때문에 단순히 사이클이 없는 그래프를 구하면 되는 문제였다.

사이클이 없으려면 방향성이 없는 무방향그래프에서만 적용 가능한데 이 문제가 그러한 조건을 충족시켰다.

그리고 입력조건에 비행 스케쥴은 항상 연결 그래프를 이룬다고 했는데, 이는 노드마다 간선을 하나씩만 가지게 끔 설정해주면 최소신장트리는 노드가 N개 일 때 항상 간선의 개수가 N-1개므로 입력받은 노드(N)의 개수에서 N-1을 해주자.

'''
2
3 3
1 2
2 3
1 3
5 4
2 1
2 3
4 3
4 5
'''
import sys
input = sys.stdin.readline
T = int(input())

for i in range(T):
    n, m = map(int, input().split())
    for j in range(m):
        a, b = map(int, input().split())
    print(n-1)

👉🏽
2
4 

---

✏️ 결론

지금까지 part 2. 주요 알고리즘 이론과 실전 문제를 모두 풀어봤고, 내일부터는 part 3. 알고리즘 유형별 기출문제를 풀어 볼 계획이다.

알고리즘을 마음잡고 공부한지 30일이 되었는데,
30일전의 알고리즘에 대해 아무것도 모르는 나와 지금의 나를 선택하라면 한치의 망설임 없이 지금의 나를 선택하고 싶다.

30일을 기념하며 wakatime 사진을 가져와봤다.

wakatime - leaderboards에 들어가면 하루에 공부하는 시간이 얼마나 되는지 전 세계 사람들과 비교를 할 수 있는 페이지가 있다.

총 5,000등 중 267등을 찍었는데, 꾸준히 하루에 최소 시간을 정해가며 공부를 해서 그런지 생각보다 등수가 높게나와서 당황했다. (OBC시절의 번호도 267번이었는데 우연의 일치인가)

실력은 공부시간에 비례하는것은 아니지만 내가 어떤 한 가지 일에 집중하기로 마음을 먹고 그것을 꾸준히 실천하는 내 모습이 대견하다고 생각해서 사진을 가져왔다. (자랑하는것은 아닙니다!)

공부시간을 모두 알고리즘에 투자한것은 아니다.
React, CS 등등을 공부했는데 알고리즘이 비중이 높은것 뿐이다.

앞으로의 얇은 목표가 있다면

1. 기업 알고리즘 테스트를 안정적으로 통과하는 것
2. wakatime - leaderboard 100등안으로 진입하는것

이다. 그보다는 얼른 프론트엔드로 취직하는것이겠지.

아무튼 내일부터 또 열심히 공부를 해보자.
화이팅!